Go語言數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)例詳解
更新時(shí)間：2022年08月26日 09:12:25 作者：Hann Yang
鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。本文將通過五個(gè)例題帶大家深入了解Go語言中單鏈表的用法，感興趣的可以了解一下
任意類型的數(shù)據(jù)域
之前的鏈表定義數(shù)據(jù)域都是整型int，如果需要不同類型的數(shù)據(jù)就要用到 interface{}。
空接口 interface{}
對(duì)于描述起不到任何的作用(因?yàn)樗话魏蔚膍ethod），但interface{}在需要存儲(chǔ)任意類型的數(shù)值的時(shí)候相當(dāng)有用，因?yàn)樗梢源鎯?chǔ)任意類型的數(shù)值。
一個(gè)函數(shù)把interface{}作為參數(shù)，那么它可以接受任意類型的值作為參數(shù)；如果一個(gè)函數(shù)返回interface{}，那么也就可以返回任意類型的值，類似于C語言的void*類型。
package main
import "fmt"
type Node struct {
data interface{}
next *Node
}
type List struct {
head *Node
}
func (list *List) push(value interface{}) {
node := &Node{data: value}
p := list.head
if p != nil {
for p.next != nil {
p = p.next
}
p.next = node
} else {
list.head = node
}
}
func (list *List) travel() {
p := list.head
for p != nil {
fmt.Print(p.data)
p = p.next
if p != nil {
fmt.Print("->")
}
}
fmt.Println("<nil>")
}
func main() {
node := new(List)
node.push("abc")
node.push(3.142)
node.push('a')
node.push(3 + 4i)
node.push([]int{1, 2, 3})
node.push([8]byte{'a', 3: 'd'})
node.push(Node{1, &Node{2, nil}}.data)
node.push(Node{1, &Node{2, nil}}.next)
node.travel()
}
/*輸出：
abc->3.142->97->(3+4i)->[1 2 3]->[97 0 0 100 0 0 0 0]->1->&{2 <nil>}<nil>
*/實(shí)例01
把字串中漢字除外的所有字符逐個(gè)存入鏈表，且數(shù)字以整型保存。
package main
import "fmt"
type Node struct {
data interface{}
next *Node
}
type List struct {
head *Node
}
func (list *List) push(value interface{}) {
node := &Node{data: value}
p := list.head
if p != nil {
for p.next != nil {
p = p.next
}
p.next = node
} else {
list.head = node
}
}
func (list *List) travel() {
p := list.head
for p != nil {
fmt.Print(p.data)
p = p.next
if p != nil {
fmt.Print("->")
}
}
fmt.Println("<nil>")
}
func main() {
node := new(List)
str := "Golang數(shù)據(jù)結(jié)構(gòu)123:單鏈表0789"
for _, s := range str {
if s >= 48 && s < 58 {
node.push(s - 48)
} else if s < 128 {
node.push(string(s))
}
}
node.travel()
}
/*輸出：
G->o->l->a->n->g->1->2->3->:->0->7->8->9<nil>
*/快慢指針
給單鏈表設(shè)置2個(gè)指針，其中一個(gè)指針先移動(dòng)n個(gè)節(jié)點(diǎn)，然后同時(shí)移動(dòng)這2個(gè)指針，那么當(dāng)先移動(dòng)的指針到達(dá)尾部時(shí)，后移動(dòng)的那個(gè)指針就是倒數(shù)第 n 個(gè)節(jié)點(diǎn)。先移動(dòng)的指針稱“快指針”，后出發(fā)的指針稱“慢指針”，其實(shí)一樣“快”只是出發(fā)有先后。
實(shí)例02
刪除鏈表中倒數(shù)第 n 個(gè)結(jié)點(diǎn)
package main
import "fmt"
type Node struct {
data interface{}
next *Node
}
type List struct {
head *Node
}
func (list *List) removNthBack(n int) {
if n > list.size() {
panic("range error: n <= List's size")
}
var fast, slow *Node
head := list.head
fast = head
slow = head
for i := 0; i < n; i++ {
fast = fast.next
}
if fast == nil {
list.head = head.next
return
}
for fast.next != nil {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
}
func removNthBack(list *List, n int) *List {
if n > list.size() {
panic("range error: n <= List's size")
}
var fast, slow *Node
head := list.head
fast = head
slow = head
for i := 0; i < n; i++ {
fast = fast.next
}
if fast == nil {
list.head = head.next
return list
}
for fast.next != nil {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return list
}
func (list *List) push(value interface{}) {
node := &Node{data: value}
p := list.head
if p != nil {
for p.next != nil {
p = p.next
}
p.next = node
} else {
list.head = node
}
}
func (list *List) size() int {
length := 0
for p := list.head; p != nil; p = p.next {
length++
}
return length
}
func (list *List) travel() {
p := list.head
for p != nil {
fmt.Print(p.data)
p = p.next
if p != nil {
fmt.Print("->")
}
}
fmt.Println("<nil>")
}
func main() {
lst := new(List)
str := "12309"
for _, s := range str {
lst.push(s - 48)
}
lst.travel()
lst.removNthBack(3)
lst.travel()
lst = removNthBack(lst, 3)
lst.travel()
lst.removNthBack(2)
lst.travel()
//lst.removNthBack(10) //panic error
lst.removNthBack(2)
lst.travel()
lst.removNthBack(1)
lst.travel()
//lst.removNthBack(1) //panic error
}
/*輸出：
1->2->3->0->9<nil>
1->2->0->9<nil>
1->0->9<nil>
1->9<nil>
9<nil>
<nil>
*/反轉(zhuǎn)鏈表
遍歷一個(gè)鏈表，每個(gè)結(jié)點(diǎn)用頭插法相接的新鏈表就是原鏈表的反轉(zhuǎn)結(jié)果。
實(shí)例03
反轉(zhuǎn)整個(gè)鏈表
package main
import "fmt"
type Node struct {
data interface{}
next *Node
}
type List struct {
head *Node
}
func (list *List) reverse() {
res := &List{}
for p := list.head; p != nil; p = p.next {
node := &Node{p.data, nil}
node.next = res.head
res.head = node
}
list.head = res.head
}
func (list *List) pushHead(value interface{}) {
node := &Node{data: value}
node.next = list.head
list.head = node
}
func (list *List) build(lst []interface{}) {
for i := len(lst) - 1; i >= 0; i-- {
node := &Node{data: lst[i]}
node.next = list.head
list.head = node
}
}
func (list *List) clear() {
list.head = nil
}
func (list *List) travel() {
p := list.head
for p != nil {
fmt.Print(p.data)
p = p.next
if p != nil {
fmt.Print("->")
}
}
fmt.Println("<nil>")
}
func main() {
lst := new(List)
for n := 5; n > 0; n-- {
lst.pushHead(n)
}
lst.travel()
lst.reverse()
lst.travel()
lst.clear()
lst.build([]interface{}{6.13, "/", 100000, "Hann", 1.0e-5})
lst.travel()
lst.reverse()
lst.travel()
}
/*輸出：
1->2->3->4->5<nil>
5->4->3->2->1<nil>
6.13->/->100000->Hann->1e-05<nil>
1e-05->Hann->100000->/->6.13<nil>
*/實(shí)例04
反轉(zhuǎn)鏈表的其中一段，反轉(zhuǎn)從第m個(gè)結(jié)點(diǎn)到n個(gè)結(jié)點(diǎn)(其中0<m<=n<=length of List)
Input: 1->2->3->4->5->nil, m = 2, n = 4
Output: 1->4->3->2->5->nil
package main
import "fmt"
type Node struct {
data interface{}
next *Node
}
type List struct {
head *Node
}
func reverseBetween(list *List, m int, n int) *List {
list = list.Copy()
head := list.head
if head == nil || m >= n {
return list
}
if m < 1 { //防止范圍左端超限
m = 1
}
node := &Node{0, head}
p := node
for i := 0; p.next != nil && i < m-1; i++ {
p = p.next
}
if p.next == nil {
return list
}
cur := p.next
for i := 0; i < n-m && cur.next != nil; i++ {
//由cur.next != nil防止范圍右端超限
tmp := p.next
p.next = cur.next
cur.next = cur.next.next
p.next.next = tmp
}
list.head = node.next
return list
}
func (list *List) reverseBetween(m int, n int) {
head := list.head
if head == nil || m >= n {
return
}
if m < 1 { //防止范圍左端超限
m = 1
}
node := &Node{0, head}
p := node
for i := 0; p.next != nil && i < m-1; i++ {
p = p.next
}
if p.next == nil {
return
}
cur := p.next
for i := 0; i < n-m && cur.next != nil; i++ {
//由cur.next != nil防止范圍右端超限
tmp := p.next
p.next = cur.next
cur.next = cur.next.next
p.next.next = tmp
}
list.head = node.next
}
func (list *List) pushHead(value interface{}) {
node := &Node{data: value}
node.next = list.head
list.head = node
}
func (list *List) build(lst []interface{}) {
for i := len(lst) - 1; i >= 0; i-- {
node := &Node{data: lst[i]}
node.next = list.head
list.head = node
}
}
func (list *List) Copy() *List {
p := list.head
res := &List{}
if p != nil {
node := &Node{p.data, nil}
q := node
for p = p.next; p != nil; p = p.next {
q.next = &Node{p.data, nil}
q = q.next
}
res.head = node
}
return res
}
func (list *List) travel() {
p := list.head
for p != nil {
fmt.Print(p.data)
p = p.next
if p != nil {
fmt.Print("->")
}
}
fmt.Println("<nil>")
}
func main() {
list1 := new(List)
list2 := new(List)
for n := 5; n > 0; n-- {
list1.pushHead(n)
}
list1.travel()
list2 = reverseBetween(list1, 2, 4)
list2.travel()
list2 = reverseBetween(list1, 2, 3)
list2.travel()
list2 = reverseBetween(list1, 2, 5)
list2.travel()
list2 = reverseBetween(list1, 2, 6)
list2.travel()
list2 = reverseBetween(list1, 1, 6)
list2.travel()
list2 = reverseBetween(list1, 0, 3)
list2.travel()
list1.reverseBetween(1, 3)
list1.travel()
}
/*輸出：
1->2->3->4->5<nil>
1->4->3->2->5<nil>
1->3->2->4->5<nil>
1->5->4->3->2<nil>
1->5->4->3->2<nil>
5->4->3->2->1<nil>
3->2->1->4->5<nil>
3->2->1->4->5<nil>
*/交換節(jié)點(diǎn)
實(shí)例05
鏈表的相鄰節(jié)點(diǎn)兩兩交換位置
Given 1->2->3->4, you should return the list as 2->1->4->3.
package main
import "fmt"
type Node struct {
data interface{}
next *Node
}
type List struct {
head *Node
}
func (list *List) swapPairs() {
p := list.head
if p == nil || p.next == nil {
return
}
head := p.next
var node, node2 *Node
for p.next != nil {
cur := p.next
if node != nil && node.next != nil {
node.next = cur
}
if p.next.next != nil {
node2 = p.next.next
}
if p.next.next != nil {
p.next = node2
} else {
p.next = nil
}
cur.next = p
node = p
if p.next != nil {
p = node2
}
}
list.head = head
}
func swapPairs(list *List) *List {
list = list.Copy()
p := list.head
if p == nil || p.next == nil {
return list
}
head := p.next
var node, node2 *Node
for p.next != nil {
cur := p.next
if node != nil && node.next != nil {
node.next = cur
}
if p.next.next != nil {
node2 = p.next.next
}
if p.next.next != nil {
p.next = node2
} else {
p.next = nil
}
cur.next = p
node = p
if p.next != nil {
p = node2
}
}
list.head = head
return list
}
func (list *List) Copy() *List {
p := list.head
res := &List{}
if p != nil {
node := &Node{p.data, nil}
q := node
for p = p.next; p != nil; p = p.next {
q.next = &Node{p.data, nil}
q = q.next
}
res.head = node
}
return res
}
func (list *List) build(lst []interface{}) {
for i := len(lst) - 1; i >= 0; i-- {
node := &Node{data: lst[i]}
node.next = list.head
list.head = node
}
}
func (list *List) travel() {
p := list.head
for p != nil {
fmt.Print(p.data)
p = p.next
if p != nil {
fmt.Print("->")
}
}
fmt.Println("<nil>")
}
func main() {
list1 := new(List)
list2 := new(List)
list1.build([]interface{}{1, 2, 3, 4, 5, 6})
list1.travel()
list2 = swapPairs(list1)
list2.travel()
list2 = &List{&Node{0, nil}}
list2.head.next = list1.Copy().head
list2.travel()
list2.swapPairs()
list2.travel()
}
/*輸出：
1->2->3->4->5->6<nil>
2->1->4->3->6->5<nil>
0->1->2->3->4->5->6<nil>
1->0->3->2->5->4->6<nil>
*/
以上就是Go語言數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go語言單鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Go存儲(chǔ)基礎(chǔ)使用direct io方法實(shí)例
這篇文章主要介紹了Go存儲(chǔ)基礎(chǔ)之如何使用direct io方法實(shí)例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-12-12
golang 實(shí)現(xiàn)一個(gè)負(fù)載均衡案例(隨機(jī),輪訓(xùn))
這篇文章主要介紹了golang 實(shí)現(xiàn)一個(gè)負(fù)載均衡案例(隨機(jī)、輪訓(xùn))，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-04-04
這篇文章主要給大家介紹Go中的內(nèi)存逃逸問題，文中通過代碼示例講解的非常詳細(xì)，對(duì)我們的學(xué)習(xí)或工作有一定的參考價(jià)值，感興趣的同學(xué)可以跟著小編一起來學(xué)習(xí)2023-06-06
RabbitMQ延時(shí)消息隊(duì)列在golang中的使用詳解
延時(shí)隊(duì)列常使用在某些業(yè)務(wù)場景,使用延時(shí)隊(duì)列可以簡化系統(tǒng)的設(shè)計(jì)和開發(fā)、提高系統(tǒng)的可靠性和可用性、提高系統(tǒng)的性能,下面我們就來看看如何在golang中使用RabbitMQ的延時(shí)消息隊(duì)列吧2023-11-11
本文詳細(xì)講解了Go語言中并發(fā)的工作原理，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
Go 1.21新增的slices包中切片函數(shù)用法詳解
Go 1.21新增的 slices 包提供了很多和切片相關(guān)的函數(shù),可以用于任何類型的切片,本文通過代碼示例為大家介紹了部分切片函數(shù)的具體用法,感興趣的小伙伴可以了解一下2023-08-08
golang 中string和int類型相互轉(zhuǎn)換
這篇文章主要介紹了golang 中string和int類型相互轉(zhuǎn)換，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
有限狀態(tài)機(jī)（Finite?State?Machine，F(xiàn)SM）是一種數(shù)學(xué)模型，用于描述系統(tǒng)在不同狀態(tài)下的行為和轉(zhuǎn)移條件。本文主要來和大家簡單講講Go語言中的有限狀態(tài)機(jī)FSM的使用，需要的可以參考一下2023-04-04
golang從語言級(jí)別上對(duì)并發(fā)提供了支持,而且在啟動(dòng)并發(fā)的方式上直接添加了語言級(jí)的關(guān)鍵字。下面這篇文章主要給大家介紹了關(guān)于golang高并發(fā)的相關(guān)資料，需要的朋友可以參考下2019-03-03
go-micro集成RabbitMQ實(shí)戰(zhàn)和原理詳解
本文主要介紹go-micro使用RabbitMQ收發(fā)數(shù)據(jù)的方法和原理，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05