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