Go语言的list包（列表）链表

淩亂°似流年 2023-10-08 18:27 31阅读 0赞

#### 阅读目录 ####

*  Go语言的list包（列表）链表
 *   *  1 创建链表
     *  2 list 插入元素
     *   *  2.1 在列表头部插入元素
         *  2.2 在列表尾部插入元素
         *  2.3 在指定元素前插入元素
         *  2.4 在指定元素后插入元素
         *  2.5 列表 list 插入列表
     *  3 列表 list 删除元素
     *  4 列表 list 遍历
     *   *  4.1 列表正序遍历
         *  4.2 列表倒叙遍历
     *  5 列表 list 元素移动
     *   *  5.1 移到元素前

## Go语言的list包（列表）链表 ##

1.  创建链表：可以使用list包中的List结构体来创建一个链表，并使用Node结构体来添加节点。
2.  遍历链表：可以使用for循环来遍历链表，从而获取每个节点的值。
3.  查找链表：可以使用for循环来查找链表中指定的节点，从而获取该节点的值。
4.  删除链表：可以使用for循环来删除链表中指定的节点，从而删除该节点。

在 Go 语言中，列表使用 container/list 包来实现，内部的实现原理是双链表，列表能够高效地进行任意位置的元素插入和删除操作。

### 1 创建链表 ###

使用 list.New 初始化列表：`listName := list.New()`

说明  
通过 list.New 初始化了一个名为 listName 的列表。

使用 `var` 初始化列表：`var listName = list.List`

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	//通过 list.New 创建列表
    	listHaiCoder := list.New()
    	listHaiCoder.PushBack("Hello")
    	listHaiCoder.PushBack("HaiCoder")
    	
    	for i := listHaiCoder.Front(); i != nil; i = i.Next() {
        
    		fmt.Println("Element =", i.Value)
    	}
    }

PS E:\TEXT\test_go\test> go run .\main.go
    Element = Hello
    Element = HaiCoder
    PS E:\TEXT\test_go\test>

### 2 list 插入元素 ###

Golang 的列表元素的插入有四种情景，分别为：

*  在指定元素前插入
 *  在指定元素后插入
 *  在列表头部插入
 *  在列表尾部插入

指定位置插入元素语法

`InsertBefore(v interface {}, mark * Element) *Element`

参数

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><em>v</em></td> 
   <td>要插入的元素。</td> 
  </tr> 
  <tr> 
   <td><em>mark</em></td> 
   <td>列表的节点。</td> 
  </tr> 
 </tbody> 
</table>

返回值

<table> 
 <thead> 
  <tr> 
   <th>返回值</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><em>Element</em></td> 
   <td>元素节点。</td> 
  </tr> 
 </tbody> 
</table>

在列表指定元素后插入：  
`InsertAfter(v interface {}, mark * Element) *Element`

在列表头部插入  
`PushFront(v interface{}) *Element`

在列表尾部插入  
`PushBack(v interface{}) *Element`

#### 2.1 在列表头部插入元素 ####

使用 `PushFront` 在列表头部插入元素。

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	//使用 PushFront 在列表头部插入元素
    	listHaiCoder := list.New()
    	listHaiCoder.PushFront("Hello")
    	listHaiCoder.PushFront("HaiCoder")
    
    	for i := listHaiCoder.Front(); i != nil; i = i.Next() {
        
    		fmt.Println("Element =", i.Value)
    	}
    }

PS E:\TEXT\test_go\test> go run .\main.go
    Element = HaiCoder
    Element = Hello
    PS E:\TEXT\test_go\test>

#### 2.2 在列表尾部插入元素 ####

使用 PushBack 在列表尾部插入元素

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	//使用 PushFront 在列表头部插入元素
    	listHaiCoder := list.New()
    	listHaiCoder.PushBack("Hello")
    	listHaiCoder.PushBack("HaiCoder")
    
    	for i := listHaiCoder.Front(); i != nil; i = i.Next() {
        
    		fmt.Println("Element =", i.Value)
    	}
    }

PS E:\TEXT\test_go\test> go run .\main.go
    Element = Hello
    Element = HaiCoder
    PS E:\TEXT\test_go\test>

#### 2.3 在指定元素前插入元素 ####

使用 `InsertBefore` 在列表的指定元素前插入元素

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	//使用 InsertBefore 在列表的指定元素前插入元素
    	listHaiCoder := list.New()
    	element := listHaiCoder.PushBack("Hello")
    	element = listHaiCoder.InsertBefore("HaiCoder", element)
    	listHaiCoder.InsertBefore("wgchen", element)
    
    	for i := listHaiCoder.Front(); i != nil; i = i.Next() {
        
    		fmt.Println("Element =", i.Value)
    	}
    }

PS E:\TEXT\test_go\test> go run .\main.go
    Element = wgchen
    Element = HaiCoder
    Element = Hello   
    PS E:\TEXT\test_go\test>

#### 2.4 在指定元素后插入元素 ####

使用 `InsertAfter` 在列表的指定元素后插入元素

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	//使用 InsertAfter 在列表的指定元素后插入元素
    	listHaiCoder := list.New()
    	element := listHaiCoder.PushBack("Hello")
    	element = listHaiCoder.InsertAfter("HaiCoder", element)
    	listHaiCoder.InsertAfter("wgchen", element)
    
    	for i := listHaiCoder.Front(); i != nil; i = i.Next() {
        
    		fmt.Println("Element =", i.Value)
    	}
    }

PS E:\TEXT\test_go\test> go run .\main.go
    Element = Hello
    Element = HaiCoder
    Element = wgchen  
    PS E:\TEXT\test_go\test>

#### 2.5 列表 list 插入列表 ####

Golang 的列表除了支持 插入元素外，还可以将整个列表插入到另一个列表中。在一个列表中插入另一个列表，只支持两种情况，分别为：

*  头部插入列表：`PushFrontList(other *List)`
 *  尾部插入列表：`PushBackList(other *List)`

在头部插入列表

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	//使用 PushFrontList 在列表头部插入一个列表
    	listHaiCoder := list.New()
    	listHaiCoder.PushFront("hello")
    	listHaiCoder.PushFront("haicode")
    
    	listInsert := list.New()
    	listInsert.PushBack("wgchen")
    	listInsert.PushBack("willem")
    
    	listHaiCoder.PushFrontList(listInsert)
    	for i := listHaiCoder.Front(); i != nil; i = i.Next() {
        
    		fmt.Println("Element = ", i.Value)
    	}
    }

PS E:\TEXT\test_go\test> go run .\main.go
    Element =  wgchen
    Element =  willem 
    Element =  haicode
    Element =  hello  
    PS E:\TEXT\test_go\test>

在尾部插入列表

使用 PushBackList 在列表尾部插入一个列表

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	//使用 PushFrontList 在列表头部插入一个列表
    	listHaiCoder := list.New()
    	listHaiCoder.PushFront("hello")
    	listHaiCoder.PushFront("haicode")
    
    	listInsert := list.New()
    	listInsert.PushBack("wgchen")
    	listInsert.PushBack("willem")
    
    	listHaiCoder.PushBackList(listInsert)
    	for i := listHaiCoder.Front(); i != nil; i = i.Next() {
        
    		fmt.Println("Element = ", i.Value)
    	}
    }

PS E:\TEXT\test_go\test> go run .\main.go
    Element =  haicode
    Element =  hello 
    Element =  wgchen
    Element =  willem
    PS E:\TEXT\test_go\test>

### 3 列表 list 删除元素 ###

Golang 的列表的删除元素使用 remove 函数，删除的元素不能为空，如果为空，会报异常。

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	//使用 Remove 在列表中删除元素
    	listHaiCoder := list.New()
    	listHaiCoder.PushFront("hello")
    	haicode := listHaiCoder.PushFront("haicode")
    
    	listInsert := list.New()
    	listInsert.PushBack("wgchen")
    	listInsert.PushBack("willem")
    
    	listHaiCoder.PushBackList(listInsert)
    	removeEle := listHaiCoder.Remove(haicode)
    	fmt.Println("RemoveElement =", removeEle)
    
    	for i := listHaiCoder.Front(); i != nil; i = i.Next() {
        
    		fmt.Println("Element = ", i.Value)
    	}
    }

PS E:\TEXT\test_go\test> go run .\main.go
    RemoveElement = haicode
    Element =  hello 
    Element =  wgchen
    Element =  willem
    PS E:\TEXT\test_go\test>

删除空元素  
使用 Remove 在列表中删除空元素，报错。

### 4 列表 list 遍历 ###

列表的 Front 函数返回的是列表的头元素，  
Next 是实现列表的指针后移，  
for 循环的结束条件是列表的节点为 nil。

链表的倒序遍历是使用 for 循环加上 list 内置的 Back 函数和 Prev 函数来实现。

列表的 Back 函数返回的是列表的尾元素，  
Prev 是实现列表的指针前移。

#### 4.1 列表正序遍历 ####

正序遍历列表，并打印列表的每一个元素。

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	listHaiCoder := list.New()
    	listHaiCoder.PushFront("hello")
    	listHaiCoder.PushFront("haicode")
    
    	for i := listHaiCoder.Front(); i != nil; i = i.Next() {
        
    		fmt.Println("Element = ", i.Value)
    	}
    }

#### 4.2 列表倒叙遍历 ####

倒叙遍历列表，并打印列表的每一个元素。

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	listHaiCoder := list.New()
    	listHaiCoder.PushFront("hello")
    	listHaiCoder.PushFront("haicode")
    
    	for i := listHaiCoder.Back(); i != nil; i = i.Prev() {
        
    		fmt.Println("Element = ", i.Value)
    	}
    }

### 5 列表 list 元素移动 ###

Golang 的列表元素的移动有两种情景，分别为：

*  将指定元素移动到另一元素的前面
 *  将指定元素移动到另一元素的后面

#### 5.1 移到元素前 ####

将元素 e 移动到元素 mark 的前面。

package main
    
    import (
    	"container/list"
    	"fmt"
    )
    
    func main() {
        
    	//将元素 e 移动到元素 mark 的前面
    	listHaiCoder := list.New()
    	listHaiCoder.PushFront("hello")
    	listHaiCoder.PushFront("haicode")
    
    	el1 := listHaiCoder.PushFront("aa")
    	el2 := listHaiCoder.PushFront("cc")
    
    	for i := listHaiCoder.Back(); i != nil; i = i.Prev() {
        
    		fmt.Printf("%s ", i.Value)
    	}
    
    	fmt.Println("=========================================")
    	listHaiCoder.MoveBefore(el1, el2)
    
    	for i := listHaiCoder.Back(); i != nil; i = i.Prev() {
        
    		fmt.Printf("%s ", i.Value)
    	}
    }

PS E:\TEXT\test_go\test> go run .\main.go
    hello haicode aa cc =========================================
    hello haicode cc aa
    PS E:\TEXT\test_go\test>