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

語言: CN / TW / HK

介紹

我們知道 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

單鏈表

雙鏈表

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

雙鏈表

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

環形連結串列

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

環形連結串列

  1. Head:Head 是一個引用,儲存著連結串列中第一個節點的地址。

  2. 節點:連結串列中的專案稱為節點。

  3. 值:連結串列的每個節點中儲存的資料。

  4. 引用:節點的連結部分用於儲存其他節點的引用。我們將使用“next”和“prev”來儲存下一個或上一個節點的地址。

單鏈表的操作

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

  1. 遍歷:像資料那樣隨機檢索在單鏈表中是不可能的,因為需要遍歷節點來尋找一個定位的節點。

  2. 增加:插入單鏈表可以在列表的開頭或結尾,以及指定節點之後。(頭插、尾插、指定位置插入)

  3. 刪除:刪除可以發生在列表的開始或結束處,以及在一個指定的節點之後。

  4. 判空:判斷一個連結串列是否為空

  5. 獲取連結串列長度

  6. 查詢是否包含指定值

  7. 反轉:面試高頻題

建立單鏈表

定義連結串列的結構體:

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

通常的做法是把資料域定義為介面 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}

複製程式碼

插入元素

  1. 頭插

函式實現:

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}

複製程式碼

  1. 中間插入

圖解:

函式實現:

// 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++}

複製程式碼

  1. 尾插

圖解:

函式如下:

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()}

複製程式碼

刪除元素

  1. 頭部刪除

圖解

函式如下:

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}

複製程式碼

  1. 中間刪除

圖解:

函式如下:

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}

複製程式碼

  1. 尾部刪除

圖解:

函式如下:

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>

複製程式碼

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

劃線

評論

複製