怎么在Golang中實現一個List

這期內容當中小編將會給大家帶來有關怎么在Golang中實現一個List，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

實現方式：

type Node struct {
 Value interface{} 
 next, prev *Node 
}

下面就是定義List結構體了，有了上面的分析，List結構體的定義就很好實現了：

type List struct {
 root Node // 頭節點
 length int // list長度
}

那么在構建好基本的數據結構之后，如何去獲取一個List對象呢。先不著急實現，想想在Java語言中怎么實現的：

Person p = new Man();

如上所示，首先獲取一個Man類的實例，然后p中有對象的地址/引用。從這些分析我們大概知道如何去創建一個list對象了，最終需要的結果就是獲取一個List的引用/地址，并且該List的長度為0。除此之外，需要處理好空List的情況：

// 返回List的指針
func New() *List {
 l := &List{}// 獲取List{}的地址
 l.length = 0// list初始長度為0
 l.root.next = &l.root
 l.root.prev = &l.root
 return l
}

判空和長度

List的判空和獲取長度也是非常基礎和重要的，判斷是否為空，返回的數據類型是布爾類型的。什么情況下List是為空呢？根據前面的定義，頭節點的next指針域指向是頭結點本身的地址即為空。另外，判空函數寫好了，總不能什么類型的數據都去調用這個函數，我們需要指定調用的數據類型，在本例中當然是 List類型的了，為了方便操作，傳入一個List的地址即可。

func (l *List) IsEmpty() bool {
 return l.root.next == &l.root
}

分析完畢之后，獲取list的長度就簡單很多了：

func (l *List) Length() int {
 return l.length
}

頭插和尾插

因為在定義List數據結構的時候，就定義了一個root頭節點。所以此時，可以很方便的實現頭插入和尾插入。考慮能夠同時插入多個/一個Node節點，利用Go中的變長參數實現該特性。對插入的Node節點進行循環處理，新節點的指針域和root節點的指針域做相應改變，具體實現方式以及說明在代碼中說明：

func (l *List) PushFront(elements ...interface{}) {
 for _, element := range elements {
 n := &Node{Value: element} // 注釋一
 n.next = l.root.next // 新節點的next是root節點的next
 n.prev = &l.root // 新節點的prev存儲的是root的地址
 l.root.next.prev = n // 原來root節點的next的prev是新節點
 l.root.next = n // 頭插法 root 之后始終是新節點
 l.length++ // list 長度加1
 }
}

注釋1處拿出來分析：結構體初始化方式 Node{Value：element} ，& 是獲取結構體地址的方式。此時需要一個地址類型的變量來存儲結構體的地址，此時看看聲明方式為 :n這里就學習到了Go中臨時變量的聲明方式啦。并且該臨時變量不需要指明數據類型。尾插法就很簡單了，參見如下所示代碼：

func (l *List) PushBack(elements ...interface{}) {
 for _, element := range elements {
 n := &Node{Value: element}
 n.next = &l.root // since n is the last element, its next should be the head
 n.prev = l.root.prev // n's prev should be the tail
 l.root.prev.next = n // tail's next should be n
 l.root.prev = n // head's prev should be n
 l.length++
 }
}

查找

查找最終的效果是返回指定數值的索引，如果不存在的話返回-1即可。對于鏈表的查找是一個遍歷的過程，在此時就需要考慮遍歷的起始和終止區間了，不能越界出錯。因為是循環鏈表，終止節點也很好辦。具體代碼如下所示：

func (l *List) Find(element interface{}) int {
 index := 0
 p := l.root.next
 for p != &l.root && p.Value != element {
 p = p.next
 index++
 }
 // p不是root
 if p != &l.root {
 return index
 }

 return -1
}

刪除

鏈表的刪除操作邏輯很清晰，將一個Node的節點與前后節點斷開即可，同時前后節點和Node節點本身指針域也要做相應修改，最后別忘記將鏈表的長度減少相應長度。

func (l *List) remove(n *Node) {
 n.prev.next = n.next
 n.next.prev = n.prev
 n.next = nil
 n.prev = nil
 l.length--
}

刪除并返回List中的第一個數據：

func (l *List) Lpop() interface{} {
 if l.length == 0 {
 // null的表現形式nil
 return nil
 }
 n := l.root.next
 l.remove(n)
 return n.Value
}

遍歷

下面normalIndex函數的作用返回一個正常邏輯的Index，例如處理好一些越界問題：

func (l *List) normalIndex(index int) int {
 if index > l.length-1 {
 index = l.length - 1
 }

 if index < -l.length {
 index = 0
 }
 // 將給定的index與length做取余處理
 index = (l.length + index) % l.length
 return index
}

如下的函數為獲取指定范圍內的數據，根據傳入的參數需要指定start和end，最后返回的應該是一個切片或者數組，具體類型未知：

func (l *List) Range(start, end int) []interface{} {
 // 獲取正常的start和end
 start = l.normalIndex(start)
 end = l.normalIndex(end)
 // 聲明一個interface類型的數組
 res := []interface{}{}
 // 如果上下界不符合邏輯，返回空res
 if start > end {
 return res
 }
 
 sNode := l.index(start)
 eNode := l.index(end)
 // 起始點和重點遍歷
 for n := sNode; n != eNode; {
 // res的append方式
 res = append(res, n.Value)
 n = n.next
 }
 res = append(res, eNode.Value)
 return res
}

上述就是小編為大家分享的怎么在Golang中實現一個List了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。