建站
咨詢
售后
建站咨詢
新聞中心
鏈表是一種物理存儲單元上非連續(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é)點，但是不允許隨機存取。鏈表有三種類型：單向鏈表、雙向鏈表以及循環(huán)鏈表。
單向鏈表
單向鏈表中每個結(jié)點包含兩部分，分別是數(shù)據(jù)域和指針域，上一個結(jié)點的指針指向下一結(jié)點，依次相連，形成鏈表。
這里介紹三個概念：首元結(jié)點、頭結(jié)點和頭指針。
- 首元結(jié)點：就是鏈表中存儲第一個元素的結(jié)點，如下圖中 a1 的位置。
- 頭結(jié)點：它是在首元結(jié)點之前附設(shè)的一個結(jié)點，其指針域指向首元結(jié)點。頭結(jié)點的數(shù)據(jù)域可以存儲鏈表的長度或者其它的信息，也可以為空不存儲任何信息。
- 頭指針：它是指向鏈表中第一個結(jié)點的指針。若鏈表中有頭結(jié)點，則頭指針指向頭結(jié)點；若鏈表中沒有頭結(jié)點，則頭指針指向首元結(jié)點。
圖：單向鏈表
頭結(jié)點在鏈表中不是必須的，但增加頭結(jié)點有以下幾點好處：
- 增加了頭結(jié)點后，首元結(jié)點的地址保存在頭結(jié)點的指針域中，對鏈表的第一個數(shù)據(jù)元素的操作與其他數(shù)據(jù)元素相同，無需進行特殊處理。
- 增加頭結(jié)點后，無論鏈表是否為空，頭指針都是指向頭結(jié)點的非空指針，若鏈表為空的話，那么頭結(jié)點的指針域為空。
使用 Struct 定義單鏈表
利用 Struct 可以包容多種數(shù)據(jù)類型的特性，使用它作為鏈表的結(jié)點是最合適不過了。一個結(jié)構(gòu)體內(nèi)可以包含若干成員，這些成員可以是基本類型、自定義類型、數(shù)組類型，也可以是指針類型。這里可以使用指針類型成員來存放下一個結(jié)點的地址。
【示例 1】使用 Struct 定義一個單向鏈表。
type Node struct {
Data int
Next *node
}其中成員 Data 用來存放結(jié)點中的有用數(shù)據(jù)，Next 是指針類型的成員，它指向 Node struct 類型數(shù)據(jù)，也就是下一個結(jié)點的數(shù)據(jù)類型。
【示例 2】為鏈表賦值，并遍歷鏈表中的每個結(jié)點。
package main
import "fmt"
type Node struct {
data int
next *Node
}
func Shownode(p *Node) { //遍歷
for p != nil {
fmt.Println(*p)
p = p.next //移動指針
}
}
func main() {
var head = new(Node)
head.data = 1
var node1 = new(Node)
node1.data = 2
head.next = node1
var node2 = new(Node)
node2.data = 3
node1.next = node2
Shownode(head)
}運行結(jié)果如下：
{1 0xc00004c1e0}
{2 0xc00004c1f0}
{3
插入結(jié)點
單鏈表的結(jié)點插入方法一般使用頭插法或者尾插法。
1) 頭插法
每次插入在鏈表的頭部插入結(jié)點，代碼如下所示：
package main
import "fmt"
type Node struct {
data int
next *Node
}
func Shownode(p *Node){ //遍歷
for p != nil{
fmt.Println(*p)
p=p.next //移動指針
}
}
func main() {
var head = new(Node)
head.data = 0
var tail *Node
tail = head //tail用于記錄頭結(jié)點的地址，剛開始tail的的指針指向頭結(jié)點
for i :=1 ;i<10;i++{
var node = Node{data:i}
node.next = tail //將新插入的node的next指向頭結(jié)點
tail = &node //重新賦值頭結(jié)點
}
Shownode(tail) //遍歷結(jié)果
}運行結(jié)果如下:
{9 0xc000036270}
{8 0xc000036260}
{7 0xc000036250}
{6 0xc000036240}
{5 0xc000036230}
{4 0xc000036220}
{3 0xc000036210}
{2 0xc000036200}
{1 0xc0000361f0}
{0
2) 尾插法
每次插入結(jié)點在尾部，這也是我們較為習慣的方法。
package main
import "fmt"
type Node struct {
data int
next *Node
}
func Shownode(p *Node){ //遍歷
for p != nil{
fmt.Println(*p)
p=p.next //移動指針
}
}
func main() {
var head = new(Node)
head.data = 0
var tail *Node
tail = head //tail用于記錄最末尾的結(jié)點的地址，剛開始tail的的指針指向頭結(jié)點
for i :=1 ;i<10;i++{
var node = Node{data:i}
(*tail).next = &node
tail = &node
}
Shownode(head) //遍歷結(jié)果
}運行結(jié)果如下：
{0 0xc0000361f0}
{1 0xc000036200}
{2 0xc000036210}
{3 0xc000036220}
{4 0xc000036230}
{5 0xc000036240}
{6 0xc000036250}
{7 0xc000036260}
{8 0xc000036270}
{9
在進行數(shù)組的插入、刪除操作時，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，需要做大量的數(shù)據(jù)搬移，所以速度較慢。而在鏈表中插入或者刪除一個數(shù)據(jù)，我們并不需要為了保持內(nèi)存的連續(xù)性而搬移結(jié)點，因為鏈表的存儲空間本身就不是連續(xù)的。所以，在鏈表中插入和刪除一個數(shù)據(jù)是非?？焖俚摹?/p>
但是，有利就有弊。鏈表要想隨機訪問第 k 個元素，就沒有數(shù)組那么高效了。因為鏈表中的數(shù)據(jù)并非連續(xù)存儲的，所以無法像數(shù)組那樣，根據(jù)首地址和下標，通過尋址公式就能直接計算出對應(yīng)的內(nèi)存地址，而是需要根據(jù)指針一個結(jié)點一個結(jié)點地依次遍歷，直到找到相應(yīng)的結(jié)點。
循環(huán)鏈表
循環(huán)鏈表是一種特殊的單鏈表。
循環(huán)鏈表跟單鏈表唯一的區(qū)別就在尾結(jié)點。單向鏈表的尾結(jié)點指針指向空地址，表示這就是最后的結(jié)點了，而循環(huán)鏈表的尾結(jié)點指針是指向鏈表的頭結(jié)點，它像一個環(huán)一樣首尾相連，所以叫作“循環(huán)”鏈表，如下圖所示。
圖：循環(huán)鏈表
和單鏈表相比，循環(huán)鏈表的優(yōu)點是從鏈尾到鏈頭比較方便。當要處理的數(shù)據(jù)具有環(huán)型結(jié)構(gòu)特點時，就特別適合采用循環(huán)鏈表。比如著名的約瑟夫問題，盡管用單鏈表也可以實現(xiàn)，但是用循環(huán)鏈表實現(xiàn)的話，代碼就會簡潔很多。
雙向鏈表
單向鏈表只有一個方向，結(jié)點只有一個后繼指針 next 指向后面的結(jié)點。而雙向鏈表，顧名思義它支持兩個方向，每個結(jié)點不止有一個后繼指針 next 指向后面的結(jié)點，還有一個前驅(qū)指針 prev 指向前面的結(jié)點。
圖：雙向鏈表
雙向鏈表需要額外的兩個空間來存儲后繼結(jié)點和前驅(qū)結(jié)點的地址。所以，如果存儲同樣多的數(shù)據(jù)，雙向鏈表要比單鏈表占用更多的內(nèi)存空間。雖然兩個指針比較浪費存儲空間，但可以支持雙向遍歷，這樣也帶來了雙向鏈表操作的靈活性。
文章名稱：創(chuàng)新互聯(lián)GO教程:Go語言鏈表操作
分享URL：http://fisionsoft.com.cn/article/cdshiod.html
