Go?語言數(shù)據(jù)結(jié)構(gòu)如何實現(xiàn)抄一個list示例詳解

更新時間：2023年04月16日 11:54:44 作者：陪我去看海

這篇文章主要為大家介紹了Go?語言數(shù)據(jù)結(jié)構(gòu)如何實現(xiàn)抄一個list示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

前言

閑來無事，自己實現(xiàn)一個 Go提供的list包

list是Go提供的一個內(nèi)置的包
內(nèi)部就是實現(xiàn)了一個雙向循環(huán)鏈表以及各種API

目標(biāo)明確：就是實現(xiàn)一個雙向循環(huán)鏈表

文章源碼

list是個啥

在開始做之前，還是要先了解一下鏈表這個數(shù)據(jù)結(jié)構(gòu) ，長話短說：

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈表，如:

a.next = b
a.prev = c
b.next = c
b.prev = a
c.next = a
c.prev = b

這就是一個雙向循環(huán)鏈表

鏈表可以提升存儲空間的利用率，實現(xiàn)了存儲空間動態(tài)管理的鏈?zhǔn)酱鎯Y(jié)構(gòu)

接下來，我們來看看Go官方都為這個list提供了哪些操作，我們逐一實現(xiàn)

New：創(chuàng)建一個鏈表
Init：初始化一個鏈表
Back：返回鏈表中的最后一個元素
Front：返回鏈表中的第一個元素
InsertAfter(e,at)：將e加入at元素后
InsertBefore(e,at)：將e加入at元素前
Len：返回list的長度
PushBack(e)：將e成為鏈表的最后一個元素
PushFront(e)：將e成為鏈表的第一個元素
Remove(e)：將list上的e刪除

list結(jié)構(gòu)

定義list結(jié)構(gòu)，以及l(fā)ist內(nèi)部node節(jié)點的結(jié)構(gòu)，這里采用struct實現(xiàn)

type Element struct {
	prev, next *Element
	Value      any
}
type List struct {
	root Element
	len  int
}

Init & New

Init就是提供初始化一個環(huán)鏈表的方法，并返回這個環(huán)形鏈表

之所以把 Init 和 New 放在一起，是因為在 New 函數(shù)中其實就是對 Init 的一層包裝，這樣就可以實現(xiàn)Go中的包名.New方法，比如：errors.New()

// 初始化一個 環(huán)list
func (list *List) Init() *List {
	// 形成環(huán)
	list.root.next = &amp;list.root
	list.root.prev = &amp;list.root
	list.len = 0
	return list
}
func NewList() *List {
	return new(List).Init()
}

InsertAfter & InsertBefore & PushBack & PushFront

這兩個方法的作用類似，就是將 e 插入到 at 的后/前位置

這里我們先看一個圖：

這個圖片就是一個雙向環(huán)形鏈表，我們要在這個里面進(jìn)行插入元素操作，比如，我們要插入 e 到 e1 前面我們應(yīng)該怎么做？

將e的下一個變?yōu)閑1：e.next = e1
將e的上一個變?yōu)閑1的上一個：e.prev = e1.prev
將e的上一個的下一個變?yōu)樽约海篹.prev.next = e
將e的下一個的上一個變?yōu)樽约海篹.next.prev = e

這樣就完成了插入，回到方法實現(xiàn)上，一個是插入之后，一個插入之前，那么我們是不是可以看作是相同操作，其實都已插入操作，只是位置的變化。

這時候想象一下，比如讓你 e 插入 at 之前，但是只提供了，參數(shù)1插入?yún)?shù)2后面的操作，如何辦到呢？

將 e 插入到 at 的前一個的后面，是不是就ok了，就相當(dāng)于自己讓別人插個隊，你在我前面的后面站就行了

// Insert 插入：將 currentElement 插入至 originElement 后
func (list *List) Insert(currentElement, originElement *Element) *Element {
	currentElement.next = originElement.next
	currentElement.prev = originElement
	currentElement.prev.next = currentElement
	currentElement.next.prev = currentElement
	list.len++
	return currentElement
}
// InsertAfter 插入在之后
func (list *List) InsertAfter(currentElement, originElement *Element) *Element {
	return list.Insert(currentElement, originElement)
}
// InsertBefore 插入在之前
func (list *List) InsertBefore(currentElement, originElement *Element) *Element {
	return list.Insert(currentElement, originElement.prev)
}

這樣一來，好像把 PushBack 和 PushFront都實現(xiàn)了，這就是封裝的好處

// PushBack 插入一個元素在最后
func (list *List) PushBack(originElement *Element) *Element {
	list.InsertBefore(originElement, &list.root)
	return originElement
}
// PushFront 插入一個元素在最前
func (list *List) PushFront(originElement *Element) *Element {
	list.InsertAfter(originElement, &list.root)
	return originElement
}

Back & Front

這兩個方式抽象上說，也是一樣的功能，一個是返回鏈表最后一個，另一個是返回鏈表第一個，因為這里提供了頭結(jié)點，所以特別簡單

最后一個節(jié)點 = 頭結(jié)點.prev

第一個節(jié)點 = 頭結(jié)點.next

// Back 返回最后一個元素
func (list *List) Back() *Element {
	if list.len == 0 {
		return nil
	}
	// 頭結(jié)點的上一個就是最后一個
	return list.root.prev
}
// Front 返回第一個元素
func (list *List) Front() *Element {
	if list.len == 0 {
		return nil
	}
	// 頭結(jié)點的下一個就是第一個元素
	return list.root.next
}

Remove

Remove方法就是提供了，刪除鏈表上的某個元素，怎么樣才能刪除某個節(jié)點呢，本質(zhì)也就是讓前后的節(jié)點相互鏈表，我就被排擠出來了，這樣就可以實現(xiàn)刪除

將要刪除的元素 e.next.prev = e.prev
將要刪除的元素 e.prev.next = e.next

// Remove 刪除某個元素
func (list *List) Remove(originElement *Element) (any,error) {
	if originElement == &list.root {
		return nil, errors.New("the origin Element can not be list.root")
	}
	for e := list.root.next; e != &list.root; e = e.next {
		if e == originElement {
			e.prev.next = e.next
			e.next.prev = e.prev
			return e.Value, nil
		} else {
			continue
		}
	}
	return nil, errors.New("the origin Element dose not belong to the list")
}