第詳解Go語言中單鏈表的使用目錄鏈表單鏈表結(jié)構(gòu)創(chuàng)建節(jié)點遍歷鏈表頭插法尾插法遍歷方法鏈表長度鏈表轉(zhuǎn)數(shù)組數(shù)組轉(zhuǎn)鏈表

鏈表

一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。使用鏈表結(jié)構(gòu)可以避免在使用數(shù)組時需要預(yù)先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機讀取的優(yōu)點，同時鏈表由于增加了結(jié)點的指針域，空間開銷比較大。

單鏈表結(jié)構(gòu)

利用struct可以包容多種數(shù)據(jù)類型，結(jié)構(gòu)體內(nèi)也可以包含多個成員，這些成員可以是基本類型、自定義類型、數(shù)組類型，也可以是指針類型。這里可以使用指針類型成員來存放下一個結(jié)點的地址。如以下定義，成員data用來存放結(jié)點中的數(shù)據(jù)(整數(shù)類型)，next是指針類型的成員，它指向ListNodestruct類型數(shù)據(jù)，也就是下一個結(jié)點的數(shù)據(jù)類型。

typeListNodestruct{

dataint

next*ListNode

創(chuàng)建節(jié)點

節(jié)點聲明和賦值有以下幾種格式：

packagemain

import"fmt"

typeListNodestruct{

dataint

next*ListNode

funcmain(){

varhead*ListNode

head=new(ListNode)

head.data=1

varnode1=new(ListNode)

node1.data=2

varnode2=ListNode{3,nil}

varnode3=ListNode{data:4}

fmt.Println(*head)

fmt.Println(*node1)

fmt.Println(*node2)

fmt.Println(*node3)

/*輸出：

{1nil}

{2nil}

{3nil}

{4nil}

*/

遍歷鏈表

一個for循環(huán)即可，結(jié)構(gòu)描述的鏈表沒有空鏈表的，不論data是何種類型，一旦聲明即使不馬上賦值也會有類型默認值，比如new(ListNode)即賦值了ListNode{0,nil}。

funcshowNode(p*ListNode){

fmt.Print(*p)

forp.next!=nil{

p=p.next

fmt.Print("-",*p)

fmt.Println()

頭插法

新結(jié)點放在鏈表的最前面

packagemain

import"fmt"

typeListNodestruct{

dataint

next*ListNode

funcshowNode(p*ListNode){

fmt.Print(*p)

forp.next!=nil{

p=p.next

fmt.Print("-",*p)

fmt.Println()

funcmain(){

varhead=ListNode{0,nil}

fori:=1;ii++{

varnode=ListNode{data:i}

node.next=head

head=node

showNode(head)

/*輸出：

{40xc000084250}-{30xc000084240}-{20xc000084230}-{10xc000084220}-{0nil}

*/

尾插法

新結(jié)點追加到鏈表的最后面

packagemain

import"fmt"

typeListNodestruct{

dataint

next*ListNode

funcshowNode(p*ListNode){

fmt.Print(*p)

forp.next!=nil{

p=p.next

fmt.Print("-",*p)

fmt.Println()

funcmain(){

varhead,tail*ListNode

head=ListNode{0,nil}

tail=head

fori:=1;ii++{

varnode=ListNode{data:i}

(*tail).next=node

tail=node

showNode(head)

/*輸出：

{00xc000084220}-{10xc000084230}-{20xc000084240}-{30xc000084250}-{4nil}

*/

遍歷方法

方法的定義：參數(shù)表放在函數(shù)名前

packagemain

import"fmt"

typeListNodestruct{

dataint

next*ListNode

func(p*ListNode)travel(){

fmt.Print(p.data)

forp.next!=nil{

p=p.next

fmt.Print("-",p.data)

fmt.Println("nil")

funcmain(){

varhead=ListNode{0,nil}

()

fori:=1;ii++{

varnode=ListNode{data:i}

node.next=head

head=node

()

varroot*ListNode

root=new(ListNode)

()

/*輸出：

0nil

9-8-7-6-5-4-3-2-1-0nil

0nil

*/

鏈表長度

注意：函數(shù)與方法的區(qū)別

packagemain

import"fmt"

typeListNodestruct{

dataint

next*ListNode

func(head*ListNode)size()int{

size:=1

forhead=head.next;head!=nil;size++{

head=head.next

returnsize

funcLen(head*ListNode)int{

size:=1

forhead=head.next;head!=nil;size++{

head=head.next

returnsize

funcmain(){

varhead=ListNode{0,nil}

fmt.Println(Len(head))

fmt.Println(head.size())

fori:=1;ii++{

varnode=ListNode{data:i}

node.next=head

head=node

fmt.Println(Len(head))

fmt.Println(head.size())

/*輸出：

*/

鏈表轉(zhuǎn)數(shù)組

packagemain

import(

"fmt"

typeListNodestruct{

dataint

next*ListNode

func(head*ListNode)size()int{

size:=1

forhead=head.next;head!=nil;size++{

head=head.next

returnsize

func(head*ListNode)tolist()[]int{

varres[]int

res=make([]int,0,head.size())

forhead.next!=nil{

res=append(res,head.data)

head=head.next

res=append(res,head.data)

returnres

func(head*ListNode)tolist2()[]int{

varres[]int

res=make([]int,0,head.size())

res=append(res,head.data)

head=head.next

forhead!=nil{

res=append(res,head.data)

head=head.next

returnres

funcmain(){

varhead=ListNode{0,nil}

fori:=1;ii++{

varnode=ListNode{data:i}

node.next=head

head=node

fmt.Println(head.tolist())

varroot,tail*ListNode

root=ListNode{0,nil}

tail=root

fori:=1;ii++{

varnode=ListNode{data:i}

(*tail).next=node

tail=node

fmt.Println(root.tolist2())

/*輸出：

[9876543210]

[0123456789]

*/

數(shù)組轉(zhuǎn)鏈表

packagemain

import"fmt"

typeListNodestruct{

dataint

next*ListNode

func(p*ListNode)travel(){

fmt.Print(p.data)

forp.next!=nil{

p=p.next

fmt.Print("-",p.data)

fmt.Println("nil")

functoNode(list[]int)*ListNode{

varhead,tail*ListNode

head=ListNode{list[0],nil}

tail=head