Go-如何优雅的实现单链表？（含全部代码）

桃扇骨 2022-10-21 01:14 33阅读 0赞

**目录**

简介

思路

节点结构体

属性

方法

单链表结构体

属性

方法

Init

New

Clear

Len

Front

Back

insert

InsertAfter

PushBack

PushFront

remove

RemoveAfter

RemoveFront

测试

常见问题

怎么遍历呀？

全部代码

--------------------

# 简介 #

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成是元素加指针。

# 思路 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][]

为了能够兼容所有类型，采用空接口。为了更好的封装，用"私有"的next和insert、remove等，看下方详细解释。

# 节点结构体 #

## 属性 ##

type ListNode struct {
        Val interface{}
        next *ListNode
        lst *SingleList
    }

*  Val：节点的值
 *  next：下一节点指针
 *  lst：所属单链表

Val采用空接口，接收任意数据类型，可通过类型断言再赋给对应类型。

## 方法 ##

返回下一个节点，O(1)

func (node *ListNode)Next() *ListNode {
    	return node.next
    }

主要用于遍历，我在其他方法中也有调用。

# 单链表结构体 #

## 属性 ##

type SingleList struct {
    	head *ListNode
    	len int
    }

*  head：头结点
 *  len：单链表长度

这里其实可以将head的Val用来存储长度，可以稍微节省一点内存，由于还需要类型断言，比较麻烦，就算了

## 方法 ##

### Init ###

func (lst *SingleList)Init(){
    	lst.head = new(ListNode)
    	lst.head.lst = lst
    	lst.len = 0
    }

创建头结点，长度为0，O(1)

### New ###

func New() *SingleList {
    	lst := new(SingleList)
    	lst.Init()
    	return lst
    }

返回创建的单链表，调用了Init，O(1)

### Clear ###

func (lst *SingleList)Clear(){
    	lst.Init()
    }

调用Init，利用Go自己的垃圾回收，O(1)

### Len ###

func (lst *SingleList)Len() int {
    	return lst.len
    }

返回单链表长度，O(1)

### Front ###

func (lst *SingleList)Front() *ListNode {
    	return lst.head.Next()
    }

返回第一个节点，就是头结点的下一个节点，空链表情况下为nil，O(1)

### Back ###

func (lst *SingleList)Back() *ListNode {
    	if lst.len == 0{
    		return nil
    	}
    	cur := lst.head.Next()
    	for{
    		if cur.Next() == nil{
    			return cur
    		}
    		cur = cur.Next()
    	}
    }

返回最后一个节点，空链表的情况下为nil，O(n)

### insert ###

func (lst *SingleList)insert(e, at *ListNode) *ListNode{
    	lst.len++
    	e.next = at.next
    	at.next = e
    	e.lst = lst
    	return e
    }

返回指向插入的节点e的指针。

*  e：待插入节点
 *  at：链表

仅在此函数进行长度增加，其他插入函数调用此函数，O(1)。

### InsertAfter ###

func (lst *SingleList)InsertAfter(val interface{}, mark *ListNode) *ListNode {
    	if mark == nil{
    		return nil
    	}
    	if mark.lst == lst{
    		return lst.insert(&ListNode{Val:val},mark)
    	}
    	return nil
    }

生成值为val的节点，并插入链表节点mark后，返回插入的节点，mark为nil或不属于单链表的情况下，返回nil。调用了insert，O(1)

*  val：待插节点值
 *  mark：在此节点后插入，如果此节点属于单链表lst

### PushBack ###

func (lst *SingleList)PushBack(val interface{}) *ListNode{
    	end := lst.Back()
    	if end == nil{
    		return lst.InsertAfter(val,lst.head)
    	}else {
    		return lst.InsertAfter(val,end)
    	}
    }

生成值为val的节点，并插入链表尾节点后，调用Back和InsertAfter。返回指向生成节点的指针，O(n)。

*  val:待插节点值

### PushFront ###

func (lst *SingleList)PushFront(val interface{}) *ListNode {
    	return lst.InsertAfter(val,lst.head)
    }

生成值为val的节点，并插入链表头节点后，调用InsertAfter。返回指向生成节点的指针，O(1)。

*  val:待插节点值

### remove ###

func (lst *SingleList)remove(e *ListNode) *ListNode{
    	nextOne := e.next
    	if nextOne == nil{
    		return nil
    	}
    	lst.len--
    	e.next = e.next.next
    	nextOne.lst = nil
    	return nextOne
    }

删除e的下一个节点，返回删除的节点，仅在此函数进行长度减少，其他删除函数调用此函数。e是尾节点时返回nil，O(1)。

*  e：单链表上的节点，需删除它后面的一个节点

### RemoveAfter ###

func (lst *SingleList)RemoveAfter(e *ListNode) *ListNode{
    	if e == nil{
    		return nil
    	}
    	if e.lst == lst{
    		return lst.remove(e)
    	}
    	return nil
    }

删除指定节点的后一个节点，返回删除的节点，指定元素为尾节点或nil时，返回nil，O(1)

### RemoveFront ###

func (lst *SingleList)RemoveFront() *ListNode {
    	return lst.remove(lst.head)
    }

前删，删除第一个节点，返回删除的节点，可能为nil，O(1)

# 测试 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][]

# 常见问题 #

## 怎么遍历呀？ ##

像下面这样就可以了呦

for e := lst.Front(); e != nil; e = e.Next() {
       do something with e.Val
    }

# 全部代码 #

具体代码和测试代码在：[https://gitee.com/frankyu365/datastructure][https_gitee.com_frankyu365_datastructure]

# 参考 #

[Go标准库-container/list][Go_-container_list]

更多Go相关内容：[Go-Golang学习总结笔记][Go-Golang]

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221021/c72906fa444e48388ee7c80192c4cc07.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1]: /images/20221021/d2044194a2e0438691b2cf05220c868d.png
[https_gitee.com_frankyu365_datastructure]: https://gitee.com/frankyu365/datastructure
[Go_-container_list]: https://studygolang.com/static/pkgdoc/pkg/container_list.htm
[Go-Golang]: https://blog.csdn.net/lady_killer9/article/details/115491317