算法：golang标准库中实现的有头双向循环链表

约定不等于承诺〃 2022-12-01 11:41 113阅读 0赞

## 有头双向循环链表 ##

golang中的标准库中`container/list`实现了一个有头双向循环链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

### 构建 ###

// Element is an element of a linked list.
    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{
        }
    }

// List 表示 一个双向链表
    // The zero value for List is an empty list ready to use.
    type List struct {
        
    	root Element // sentinel list element, only &root, root.prev, and root.next are used
    	len  int     // 当前列表长度不包括 头节点
    }
    
    // 初始化哨兵节点或者清空l.
    func (l *List) Init() *List {
        
    	l.root.next = &l.root
    	l.root.prev = &l.root
    	l.len = 0
    	return l
    }
    
    //初始化链表的哨兵节点
    func New() *List {
         return new(List).Init() }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]

### 前插v–》 新节点插入到root之后 ###

func (l *List) PushFront(v interface{
        }) *Element {
        
    	l.lazyInit()  // 初始化哨兵节点
    
        // &l.root==》哨兵节点[的内存地址]，然后在哨兵节点后面插入 新节点
    	return l.insertValue(v, &l.root)
    }
    
    // 如果没有哨兵节点，则初始化一个哨兵节点
    func (l *List) lazyInit() {
        
    	if l.root.next == nil {
        
    		l.Init()
    	}
    }
    
    // 初始化哨兵节点或者清空l.
    func (l *List) Init() *List {
        
    	l.root.next = &l.root
    	l.root.prev = &l.root
    	l.len = 0
    	return l
    }
    
    
    
    
    func (l *List) insertValue(v interface{
        }, at *Element) *Element {
        
    // 先使用v构建一个节点，然后在插入
    	return l.insert(&Element{
        Value: v}, at)
    }
    
    func (l *List) insert(e, at *Element) *Element {
        
    	n := at.next
    	at.next = e
    	e.prev = at
    	e.next = n
    	n.prev = e
    	e.list = l
    	l.len++
    	return e
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 3]  
看起来好像有点累，没关系我们直接看个大的  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 5]

### 尾插v==》新节点插入到root之前 ###

func (l *List) PushBack(v interface{
        }) *Element {
        
    	l.lazyInit()
    	return l.insertValue(v, l.root.prev) // 找到哨兵节点的前一个节点的内存地址【也就是当前链表的最后一个节点】
    }
    
    // 初始化可能的哨兵节点
    func (l *List) lazyInit() {
        
    	if l.root.next == nil {
        
    		l.Init()
    	}
    }
    
    // 空链表： 哨兵节点的前后节点都是它自己
    func (l *List) Init() *List {
        
    	l.root.next = &l.root
    	l.root.prev = &l.root
    	l.len = 0
    	return l
    }
    
    func (l *List) insertValue(v interface{
        }, at *Element) *Element {
        
    	return l.insert(&Element{
        Value: v}, at)
    }
    
    func (l *List) insert(e, at *Element) *Element {
        
    	n := at.next
    	at.next = e
    	e.prev = at
    	e.next = n
    	n.prev = e
    	e.list = l
    	l.len++
    	return e
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 7]

看起来好像有点累，没关系我们直接看个大的

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 9]

总结：无论是头插还是尾插，都是**先找到基准节点at，然后将新节点插入到基准节点at的后面**， 也就是at的next指向新节点【对应新节点的prev指向at】，新节点的next指向at节点的原来的next节点【对应原来的next节点的prev指向新节点】。区别在于，**头插的基准节点是哨兵节点root，尾插的基准节点是哨兵节点root的prev节点**

### 链表的头节点&&尾节点 ###

从尾插法和头插法可以总结出：

*  链表的头节点就是哨兵节点的下一个节点
 *  链表的为节点就是哨兵节点的上一个节点

func (l *List) Front() *Element {
        
       // 先判断链表是否为空
    	if l.len == 0 {
        
    		return nil
    	}
    	return l.root.next
    }
    
    func (l *List) Back() *Element {
        
       // 先判断链表是否为空
    	if l.len == 0 {
        
    		return nil
    	}
    	return l.root.prev
    }

### 头部插入一个链表，尾部插入一个链表 ###

当前链表l： 1，2，3，4  
被插入的链表o： a, b, c, d

*  在当前链表的头部插入一个链表：【PushFrontList】
    
     *  获取d的内存地址【o的最后一个节点】，插入l.root后面【1的前面】，当前链表变成 d, 1, 2, 3, 4
     *  获取c的内存地址【d的前一个节点】，插入l.root后面【d的前面】，当前链表变成c，d, 1, 2, 3, 4
     *  获取b的内存地址【c的前一个节点】，插入l.root后面【c的前面】，当前链表变成b，c，d, 1, 2, 3, 4
     *  获取a的内存地址【a的前一个节点】，插入l.root后面【b的前面】，当前链表变成a、b，c，d, 1, 2, 3, 4
 *  在当前链表的尾部插入一个链表：【PushBackList】
    
     *  获取a的内存地址【o的第一个节点】，插入l.root.prev后面【5的后面】，当前链表变成1, 2, 3, 4，a
     *  获取b的内存地址【a的后一个节点】，插入l.root.prev后面【a的后面】，当前链表变成1, 2, 3, 4，a，b
     *  获取c的内存地址【b的后一个节点】，插入l.root.prev后面【b的后面】，当前链表变成1, 2, 3, 4，a，b，c
     *  获取d的内存地址【c的后一个节点】，插入l.root.prev后面【c的后面】，当前链表变成1, 2, 3, 4，a，b，d

// PushBackList inserts a copy of an other list at the back of list l.
    // The lists l and other may be the same. They must not be nil.
    func (l *List) PushBackList(other *List) {
        
    	l.lazyInit()
    	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
        
    		l.insertValue(e.Value, l.root.prev)
    	}
    }
    
    // PushFrontList inserts a copy of an other list at the front of list l.
    // The lists l and other may be the same. They must not be nil.
    func (l *List) PushFrontList(other *List) {
        
    	l.lazyInit()
    	for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
        
    		l.insertValue(e.Value, &l.root)
    	}
    }

### 插队：在某一个节点的前面/后面插入一个新节点 ###

*  先判断mark节点是否属于这个链表
 *  如果属于：
    
     *  mark之前插入节点：拿到mark.prev的地址，然后在mark.prev后面插入新节点
     *  mark之后插入节点：拿到mark的地址，然后再mark后面插入新节点

// InsertBefore inserts a new element e with value v immediately before mark and returns e.
    // If mark is not an element of l, the list is not modified.
    // The mark must not be nil.
    func (l *List) InsertBefore(v interface{
        }, mark *Element) *Element {
        
    	if mark.list != l {
        
    		return nil
    	}
    	// see comment in List.Remove about initialization of l
    	return l.insertValue(v, mark.prev)
    }
    
    // InsertAfter inserts a new element e with value v immediately after mark and returns e.
    // If mark is not an element of l, the list is not modified.
    // The mark must not be nil.
    func (l *List) InsertAfter(v interface{
        }, mark *Element) *Element {
        
    	if mark.list != l {
        
    		return nil
    	}
    	// see comment in List.Remove about initialization of l
    	return l.insertValue(v, mark)
    }
    
    // insert inserts e after at, increments l.len, and returns e.
    func (l *List) insert(e, at *Element) *Element {
        
    	n := at.next
    	at.next = e
    	e.prev = at
    	e.next = n
    	n.prev = e
    	e.list = l
    	l.len++
    	return e
    }
    
    // insertValue is a convenience wrapper for insert(&Element{Value: v}, at).
    func (l *List) insertValue(v interface{
        }, at *Element) *Element {
        
    	return l.insert(&Element{
        Value: v}, at)
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1b9e234a714e4c8b88dc632d0a348e34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/a8718dfa0d47454fb46a77b8d7420c64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/584384d75e934c80bce262472d57f4c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/34f0acc4b476440ba8dad34be9226a96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/1c2c101012f249a1bc384536e5642cfb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/83c7064165e84dd68033f00b06ebcb42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/c76a3bc447c44768b6f36f00dc082b6f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/025388322a1e4d4f961df60ff00a7065.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/2e8ae0fa179e4fa98994ee3c943855c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/59ce93187e06466a907ba416b06b3501.png