前言

閑來(lái)無(wú)事，自己實(shí)現(xiàn)一個(gè) Go提供的list包

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

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

文章源碼

list是個(gè)啥

在開(kāi)始做之前，還是要先了解一下鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu) ，長(zhǎng)話(huà)短說(shuō)：

• 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為鏈表，如:

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

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

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

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

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

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

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

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

Init & New

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

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

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

InsertAfter & InsertBefore & PushBack & PushFront

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

這里我們先看一個(gè)圖：

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

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

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

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

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

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

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

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

Back & Front

這兩個(gè)方式抽象上說(shuō)，也是一樣的功能，一個(gè)是返回鏈表最后一個(gè)，另一個(gè)是返回鏈表第一個(gè)，因?yàn)檫@里提供了頭結(jié)點(diǎn)，所以特別簡(jiǎn)單

最后一個(gè)節(jié)點(diǎn) = 頭結(jié)點(diǎn).prev

第一個(gè)節(jié)點(diǎn) = 頭結(jié)點(diǎn).next

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

Remove

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

• 將要?jiǎng)h除的元素 e.next.prev = e.prev
• 將要?jiǎng)h除的元素 e.prev.next = e.next

// Remove 刪除某個(gè)元素
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")
}

總結(jié)

• 鏈表可以實(shí)現(xiàn)存儲(chǔ)空間動(dòng)態(tài)管理，它是一個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
• 封裝的代碼更具靈活性

以上就是Go 語(yǔ)言數(shù)據(jù)結(jié)構(gòu)如何實(shí)現(xiàn)抄一個(gè)list示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go 語(yǔ)言數(shù)據(jù)結(jié)構(gòu)list的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論