跟著動畫學習 GO 資料結構之 Go 連結串列

語言: CN / TW / HK

時間 2022-05-22 16:49:38 InfoQ

主題: 連結串列 Go語言

介紹

我們知道 Go 的陣列和切片非常方便對資料進行訪問，但是假如我們有一個長度為 5 的陣列 [1, 2, 3, 4, 5] ，想要往其中 3 和 4 之間插入一個元素 6，就往往不是非常容易了。為啥呢？

一般解決的方法是首先建立一個長度大於 5 的新陣列，因為這個陣列的長度首先要能儲存舊陣列的陣列，同時能有多餘的位置儲存新增加的元素 6。

這其中有個操作會很費時，就是複製操作：需要把原來陣列中的資料複製到新的記憶體空間。

因此，我們有一個更合適的資料結構叫做 連結串列 。

連結串列

連結串列由一系列節點構成，每個節點就是一個記錄。連結串列是一種遞迴的資料結構，它要麼為空（null），或者是指向一個節點的引用，英文叫 Linked List。通常由許多的元素構成，這些元素也叫節點（node），節點由兩部分構成： 資料域 和 指標域 。

資料域：資料域用來儲存資料，可以儲存基本資料型別如整型，也可以儲存其他複雜資料型別。
指標域：指標域部分用來儲存連結串列中下一個元素的地址。

節點結構

節點的 UML 圖如下：

節點的程式碼表示：

type Node struct {  data int  next *Node}

複製程式碼

連結串列的型別

連結串列有很多種型別，其主要的區別是節點引用方式的區別：單向、雙向、首尾連線。

單鏈表

單鏈表就是單向的，

每一個節點都有一個指向下一個節點的引用，除了最後一個節點。節點的引用部分包含下一個節點的地址。最後一個節點的引用部分包含值 null 。

單鏈表

雙鏈表

雙鏈表是雙向的，雙鏈表中的節點同時引用了連結串列中的上一個和下一個節點。

雙鏈表

現實生活中一個雙鏈表的地址就是我們的地鐵的某條線路，每條線路都有一個來回，而每一個站點就是一個節點：

環形連結串列

這種型別類似於單向連結串列，只是最後一個元素引用了連結串列的第一個節點。最後一個節點的連結部分包含第一個節點的地址。

環形連結串列

Head：Head 是一個引用，儲存著連結串列中第一個節點的地址。
節點：連結串列中的專案稱為節點。
值：連結串列的每個節點中儲存的資料。
引用：節點的連結部分用於儲存其他節點的引用。我們將使用“next”和“prev”來儲存下一個或上一個節點的地址。

單鏈表的操作

連結串列的操作也不外乎於增刪改查，再加上一些特定的操作。連結串列是一種動態的資料結構，資料結構棧和佇列都可以用連結串列實現的。連結串列的建立、新增和刪除操作很容易；當元素被動態新增時，會消耗更多的記憶體，因為動態資料結構並不固定。

遍歷：像資料那樣隨機檢索在單鏈表中是不可能的，因為需要遍歷節點來尋找一個定位的節點。
增加：插入單鏈表可以在列表的開頭或結尾，以及指定節點之後。（頭插、尾插、指定位置插入）
刪除：刪除可以發生在列表的開始或結束處，以及在一個指定的節點之後。
判空：判斷一個連結串列是否為空
獲取連結串列長度
查詢是否包含指定值
反轉：面試高頻題

建立單鏈表

定義連結串列的結構體：

連結串列的節點包含一個指向下一個節點的指標，每一個節點都儲存一個數據域。

通常的做法是把資料域定義為介面 interface{} ：

type Node struct {  data interface{} // 資料域: 連結串列不要求全為相同的型別，所以利用一個介面在儲存資料  next *Node // 指標域：指向下一個節點}

複製程式碼

連結串列通常由頭節點（指向第一個節點的指標）和它的長度組成。長度域 size 儲存了連結串列的長度，頭結點 headNode 儲存了連結串列頭結點或者第一個節點（首元節點）的記憶體地址：

// define a ListNode in a singly linked listtype LinkedList struct {  headNode *Node // 頭節點  size int // 儲存連結串列的長度}

複製程式碼

建立一個單鏈表：

func CreateLinkList() *LinkedList {	// 建立一個空的頭節點	node := new(Node)	l := new(LinkedList)	l.headNode = node	return l}

複製程式碼

連結串列的長度

// 返回連結串列的長度func (linkedList *LinkedList) Length() int {	return linkedList.Count()}
func (linkedList *LinkedList) Count() int {	size := 0	currNode := linkedList.headNode	for currNode != nil {		size++		currNode = currNode.next	}	return size}

複製程式碼

連結串列判空

func (linkedList *LinkedList) isNull() bool {	return linkedList.size == 0}

複製程式碼

插入元素

頭插

函式實現：

func (linkedList *LinkedList) InsertHead(v interface{}) {	node := &Node{data: v}	if linkedList.isNull() {		linkedList.headNode = node		linkedList.size++		return	} else {		node.next = linkedList.headNode		linkedList.headNode = node	}	linkedList.size++	return}

複製程式碼

中間插入

圖解：

函式實現：

// Insert adds an item at position ifunc (linkedList *LinkedList) Insert(pos int, v interface{}) {	// 先檢查待插入的位置是否正確	if pos < 1 || pos > linkedList.size+1 {		fmt.Println("Index out of bounds")	}	newNode := &Node{data: v}	var prev, current *Node	prev = nil	current = linkedList.headNode	for pos > 1 {		prev = current		current = current.next		pos = pos - 1	}	if prev != nil {		prev.next = newNode		newNode.next = current	} else {		newNode.next = current		linkedList.headNode = newNode	}	linkedList.size++}

複製程式碼

尾插

圖解：

函式如下：

func (linkedList *LinkedList) Append(v interface{}) {	node := &Node{data: v}	if linkedList.isNull() {		linkedList.headNode = node	} else {		currNode := linkedList.headNode		for currNode.next != nil {			currNode = currNode.next		}		currNode.next = node	}	linkedList.size++}

複製程式碼

遍歷元素

假設 head 指標指向連結串列的第一個節點，為了遍歷整個連結串列，我們需要進行如下幾步操作：

跟隨每個指標
隨著每次遍歷，記錄下每個節點的資料（或者 count 計數）
當最後一個指標為空 nil 時，停止遍歷

圖解如下：

函式如下：

func (linkedList *LinkedList) Traverse() {	if linkedList.isNull() {		fmt.Println("The LinkedList is empty")	}	currNode := linkedList.headNode	for currNode != nil {		fmt.Printf("%v -> ", currNode.data)		currNode = currNode.next	}	fmt.Println()}

複製程式碼

刪除元素

頭部刪除

圖解

函式如下：

func (linkedList *LinkedList) DeleteFirst() interface{} {	if linkedList.isNull() {		fmt.Println("deleteFirst: List is empty")	}	data := linkedList.headNode.data	linkedList.headNode = linkedList.headNode.next	linkedList.size--	return data}

複製程式碼

中間刪除

圖解：

函式如下：

func (linkedList *LinkedList) Delete(pos int) interface{} {
	if pos < 1 || pos > linkedList.size+1 {		fmt.Println("delete: Index out of bounds")	}	var prev, current *Node	prev = nil	current = linkedList.headNode	p := 0	if pos == 1 {		linkedList.headNode = linkedList.headNode.next	} else {		for p != pos-1 {			p = p + 1			prev = current			current = current.next		}		if current != nil {			prev.next = current.next		}	}	linkedList.size--	return current.data}

複製程式碼

尾部刪除

圖解：

函式如下：

func (linkedList *LinkedList) DeleteLast() interface{} {	if linkedList.isNull() {		fmt.Println("deleteLast: List is empty")	}
	var prev *Node	current := linkedList.headNode	for current.next != nil {		prev = current		current = current.next	}	if prev != nil {		prev.next = nil	} else {		linkedList.headNode = nil	}	linkedList.size--	return current.data}

複製程式碼

總結

好了有了上述函式，我們可以彙總到一起來檢驗我們的函式是否正確，建立一個 main.go 檔案：

package main
import "fmt"
type Node struct {	data interface{}	next *Node}
type LinkedList struct {	headNode *Node // 頭節點	size     int   // 儲存連結串列的長度}
func CreateLinkList() *LinkedList {	// 建立一個空的頭節點	node := new(Node)	l := new(LinkedList)	l.headNode = node	return l}
// 返回連結串列的長度func (linkedList *LinkedList) Length() int {	return linkedList.Count()}
func (linkedList *LinkedList) Count() int {	size := 0	currNode := linkedList.headNode	for currNode != nil {		size++		currNode = currNode.next	}	return size}
func (linkedList *LinkedList) isNull() bool {	return linkedList.size == 0}
func (linkedList *LinkedList) Traverse() {	if linkedList.isNull() {		fmt.Println("The LinkedList is empty")	}	currNode := linkedList.headNode	for currNode != nil {		fmt.Printf("%v -> ", currNode.data)		currNode = currNode.next	}	fmt.Println()	return}
func (linkedList *LinkedList) InsertHead(v interface{}) {	node := &Node{data: v}	if linkedList.isNull() {		linkedList.headNode = node		linkedList.size++		return	} else {		node.next = linkedList.headNode		linkedList.headNode = node	}	linkedList.size++	return}
func (linkedList *LinkedList) Append(v interface{}) {	node := &Node{data: v}	if linkedList.isNull() {		linkedList.headNode = node	} else {		currNode := linkedList.headNode		for currNode.next != nil {			currNode = currNode.next		}		currNode.next = node	}	linkedList.size++}
// Insert adds an item at position ifunc (linkedList *LinkedList) Insert(pos int, v interface{}) {	// 先檢查待插入的位置是否正確	if pos < 1 || pos > linkedList.size+1 {		fmt.Println("Index out of bounds")	}	newNode := &Node{data: v}	var prev, current *Node	prev = nil	current = linkedList.headNode	for pos > 1 {		prev = current		current = current.next		pos = pos - 1	}	if prev != nil {		prev.next = newNode		newNode.next = current	} else {		newNode.next = current		linkedList.headNode = newNode	}	linkedList.size++}
func (linkedList *LinkedList) DeleteFirst() interface{} {	if linkedList.isNull() {		fmt.Println("deleteFirst: List is empty")	}	data := linkedList.headNode.data	linkedList.headNode = linkedList.headNode.next	linkedList.size--	return data}
func (linkedList *LinkedList) DeleteLast() interface{} {	if linkedList.isNull() {		fmt.Println("deleteLast: List is empty")	}
	var prev *Node	current := linkedList.headNode	for current.next != nil {		prev = current		current = current.next	}	if prev != nil {		prev.next = nil	} else {		linkedList.headNode = nil	}	linkedList.size--	return current.data}
func (linkedList *LinkedList) Delete(pos int) interface{} {
	if pos < 1 || pos > linkedList.size+1 {		fmt.Println("delete: Index out of bounds")	}	var prev, current *Node	prev = nil	current = linkedList.headNode	p := 0	if pos == 1 {		linkedList.headNode = linkedList.headNode.next	} else {		for p != pos-1 {			p = p + 1			prev = current			current = current.next		}		if current != nil {			prev.next = current.next		}	}	linkedList.size--	return current.data}
func main() {	linkedList := CreateLinkList()	fmt.Println("初始化建立一個連結串列，是否為空：", linkedList.isNull())	nums := []int{1, 2, 3, 4, 5}	for i := range nums {		linkedList.Append(nums[i])	}
	fmt.Println("****************尾部插入[1,2,3,4,5]****************")	linkedList.Traverse()
	fmt.Print("連結串列的長度為：")	fmt.Println(linkedList.Length())
	fmt.Println("****************往頭部插入6****************")	linkedList.InsertHead(6)	linkedList.Traverse()
	fmt.Println("****************第二個位置插入2022****************")	linkedList.Insert(2, 2022)	linkedList.Traverse()
	fmt.Println("****************刪除最後一個元素****************")	last := linkedList.DeleteLast()	fmt.Println("刪除最後一個元素為：", last)
	fmt.Println("****************刪除第一個元素****************")	first := linkedList.DeleteFirst()	fmt.Println("刪除第一個元素為：", first)
	fmt.Println("****************刪除位置1的元素****************")	deleteData := linkedList.Delete(1)	fmt.Println("刪除位置1的元素為:", deleteData)
	fmt.Println("****************最後的連結串列為：")	linkedList.Traverse()}

複製程式碼

執行這個方法的結果為：

<code data-type="codeline">初始化建立一個連結串列，是否為空： true</code><code data-type="codeline">****************尾部插入[1,2,3,4,5]****************</code><code data-type="codeline">1 -> 2 -> 3 -> 4 -> 5 -> </code><code data-type="codeline">連結串列的長度為：5</code><code data-type="codeline">****************往頭部插入6****************</code><code data-type="codeline">6 -> 1 -> 2 -> 3 -> 4 -> 5 -> </code><code data-type="codeline">****************第二個位置插入2022****************</code><code data-type="codeline">6 -> 2022 -> 1 -> 2 -> 3 -> 4 -> 5 -> </code><code data-type="codeline">****************刪除最後一個元素****************</code><code data-type="codeline">刪除最後一個元素為： 5</code><code data-type="codeline">****************刪除第一個元素****************</code><code data-type="codeline">刪除第一個元素為： 6</code><code data-type="codeline">****************刪除位置1的元素****************</code><code data-type="codeline">刪除位置1的元素為: 2022</code><code data-type="codeline">****************最後的連結串列為：</code><code data-type="codeline">1 -> 2 -> 3 -> 4 -> </code>

複製程式碼

至此，我們把基本操作做完成了，為了避免文章過於繁瑣，決定把查詢的操作放到連結串列的相關演算法問題中再作說明。下一篇文章見！

 劃線

 評論

 複製

「其他文章」