golang基础（基础包链表使用）

我会带着你远行 2022-06-04 05:27 199阅读 0赞

## 前言 ##

golang版本包中提供了三种数据结构：list、heap和ring。已经golang的基本数据类型map。这4中数据结构算是日常开发中最常用的数据结构了。最常用的应该是map所以，golang才会将其作为基本类型。golang提供的这些数据结构，并没有保证并发安全的情况。所以最好在开发的过程中操作的时候要加锁，避免造成不必要的麻烦。也不用吐槽为什么map抛出一个不能同时读写的error。

## list包介绍 ##

golang中的list和C++的STL中的list有些类似，都有一个迭代器Element。迭代器的定义如下：

type Element struct { // Next and previous pointers in the doubly-linked list of elements. // To simplify the implementation, internally a list l is implemented // as a ring, such that &l.root is both the next element of the last // list element (l.Back()) and the previous element of the first list // element (l.Front()). next, prev *Element // The list to which this element belongs. list *List // The value stored with this element. Value interface{}
    }

可以看出golang系统包中的list是一个双向链表，element中存储一个空接口、一个其附属的链表和前后两个元素。空接口可以接收任意golang数据类型。  
Element提供的方法只有两个：  
1、`func (e *Element) Next() *Element`  
返回链表中下一个元素，如果当前元素已经是最后一个元素了，返回nil  
2、`func (e *Element) Prev() *Element`  
返回链表中前一个元素，如果当前元素是第一个元素，那么返回nil

接下来介绍一下List，在golang中List的定义如下：

type List struct {
        root Element // sentinel list element, only &root, root.prev, and root.next are used
        len  int     // current list length excluding (this) sentinel element
    }

其中root.prev指向链表第一个Element，root.next指向链表最后一个Element。  
记录了第一个元素及链表的长度。  
List提供的操作方法如下：  
1、`func New() *List`  
新建一个链表，并初始化链表（调用Init方法初始化）  
2、`func (l *List) Back() *Element`  
返回链表中最后一个元素，如果链表长度为0，则返回nil  
3、`func (l *List) Front() *Element`  
返回链表的第一个元素，如果链表长度为0，则返回nil  
4、`func (l *List) Init() *List`  
初始化链表，或者清理链表。把链表的长度置为0。并将root的prev和next都指向自己。  
5、`func (l *List) InsertAfter(v interface{}, mark *Element) *Element`  
先判断mark对应的的链表是不是l，不是的话返回nil，然后新建一个Element，存储的Value为v。然后插入到mark前面。  
6、`func (l *List) InsertBefore(v interface{}, mark *Element) *Element`  
先判断mark对应的的链表是不是l，然后新建一个Element，存储的Value为v。然后插入到mark后面。  
7、`func (l *List) Len() int`  
返回链表的长度，其实就是直接返回其len属性，所以时间复杂度为O(1）  
8、`func (l *List) MoveAfter(e, mark *Element)`  
先判断mark和e对应的的链表是不是l，不是的话返回nil。是的话把e移动到mark前面。  
9、`func (l *List) MoveToBack(e *Element)`  
先判断mark和e对应的的链表是不是l，不是的话返回nil。是的话把e移动到mark后面。  
10、`func (l *List) MoveToFront(e *Element)`  
先判断mark对应的的链表是不是l，不是的话返回nil。是的话把e移动到链表的首部。  
11、`func (l *List) PushBackList(other *List)`  
先判断mark对应的的链表是不是l，不是的话返回nil。是的话把e移动到链表的尾部。  
12、`func (l *List) PushFrontList(other *List)`  
把链表other拼接到l前面  
13、`func (l *List) Remove(e *Element) interface{}`  
如果e对于的链表是l，删除l中的元素e。返回的结果一定是e中的Value

## 例子 ##

链表的操作相对比较简单和这个，这边直接贴上list目录下对应的example\_test.go

package list_test
    
    import (
        "container/list"
        "fmt"
    )
    
    func Example() {
        // Create a new list and put some numbers in it.
        l := list.New()
        e4 := l.PushBack(4)
        e1 := l.PushFront(1)
        l.InsertBefore(3, e4)
        l.InsertAfter(2, e1)
    
        // Iterate through list and print its contents.
        for e := l.Front(); e != nil; e = e.Next() {
            fmt.Println(e.Value)
        }
    
        // Output:
        // 1
        // 2
        // 3
        // 4
    }