教程集 > Golang编程 > golang教程 > 正文 Golang学习日志 ━━ 单向链表

Golang学习日志 ━━ 单向链表

发布时间：2022-01-15 编辑：jiaochengji.com

教程集为您提供Golang学习日志 ━━ 单向链表等资源，欢迎您收藏本站，我们将为您提供最新的Golang学习日志 ━━ 单向链表资源

因为转载必须指明原文网址，而本文内容整合了网上多篇技术文章，无法明确其中一条，所以选择了原创。
已在最后的参考目录里列出本文所有涉及的文章。

单向链表（单链表）是链表的一种，是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。

<ul><li>链表是使用指针进行构造的列表；</li><li>又称为结点列表，因为链表是由一个个结点组装起来的；</li><li>其中每个结点都有指针成员变量指向列表中的下一个结点；</li></ul>

链表中的数据是以结点来表示的，每个结点的构成：

元素(数据元素的映象) 指针(指示后继元素存储位置)，

</blockquote> <ul><li>元素就是存储数据的存储单元，</li><li>指针就是连接每个结点的地址数据。</li></ul><h2>优点</h2> <ul><li>单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小</li><li>结点的删除非常方便，不需要像线性结构那样移动剩下的数据</li><li>结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表。</li></ul><h2>实现</h2> <blockquote>

简单说来，目的就是实现至少一个头指针记录开始的内存地址，此后每个元素都包含一个值和下一个元素的内存地址

</blockquote> <ol><li>相关结构体
首先需要先定义一下链表相关的结果，SingleObject用于每个节点的数据，为interface{}结构，SingleNode为链表中的节点，SingleList单链表，为了多协程读写安全，所以在链表中加了读写锁。</li></ol>

具体定义如下：

<pre><code class="lang-go hljs">// 节点数据 type SingleObject interface{} // 单链表节点 type SingleNode struct { Data SingleObject Next *SingleNode } // 单链表 type SingleList struct{ mutex *sync.RWMutex Head *SingleNode Tail *SingleNode Size uint } </code></pre> <ol start="2"><li>链表初始化
定义完结构，接下来就需要对单链表进行初始化了。代码如下：</li></ol><pre><code class="lang-go hljs">// 初始化 func (list *SingleList) Init() { list.Size = 0 list.Head = nil list.Tail = nil list.mutex = new(sync.RWMutex) } </code></pre> <ol start="3"><li>新增节点
链表节点的新增分为两种，
a. append：在链表后面追加节点；
b. insert：在指定位置插入节点。</li></ol>

另外新增时，若为第一个节点需特殊处理一下。下面请看代码：

<pre><code class="lang-go hljs">// 添加节点到链表尾部 func (list *SingleList)Append(node *SingleNode) bool { if node == nil{ return false } list.mutex.Lock() defer list.mutex.Unlock() if list.Size == 0{ list.Head = node list.Tail = node list.Size = 1 return true } tail := list.Tail tail.Next = node list.Tail = node list.Size = 1 return true } // 插入节点到指定位置 func (list *SingleList)Insert(index uint, node *SingleNode) bool { if node == nil { return false } if index > list.Size{ return false } list.mutex.Lock() defer list.mutex.Unlock() if index == 0{ node.Next = list.Head list.Head = node list.Size = 1 return true } var i uint ptr := list.Head for i = 1; i < index; i { ptr = ptr.Next } next := ptr.Next ptr.Next = node node.Next = next list.Size = 1 return true } </code></pre> <ol start="4"><li>删除节点
有了新增功能自然就少不了删除，此外，删除节点时，如果指定的位置是链表的头部或尾部，都需要特殊处理下。</li></ol>

看代码：

<pre><code class="lang-go hljs">// 删除指定位置的节点 func (list *SingleList)Delete(index uint) bool { if list == nil || list.Size == 0 || index > list.Size - 1 { return false } list.mutex.Lock() defer list.mutex.Unlock() if index == 0 { head := list.Head.Next list.Head = head if list.Size == 1{ list.Tail = nil } list.Size -= 1 return true } ptr := list.Head var i uint for i = 1; i < index; i { ptr = ptr.Next } next := ptr.Next ptr.Next = next.Next if index == list.Size - 1 { list.Tail = ptr } list.Size -= 1 return true } </code></pre> <ol start="5"><li>查询节点
根据指定的位置索引，查询出节点内容。</li></ol><pre><code class="lang-go hljs">// 获取指定位置的节点，不存在则返回nil func (list *SingleList)Get(index uint) *SingleNode{ if list == nil || list.Size == 0 || index > list.Size - 1 { return nil } list.mutex.RLock() defer list.mutex.RUnlock() if index == 0{ return list.Head } node := list.Head var i uint for i = 0; i < index; i { node = node.Next } return node } </code></pre> <ol start="6"><li>打印链表
最后，我们增加一个打印链表的功能，方便我们看整个链表的内容：</li></ol><pre><code class="lang-go hljs">// 输出链表 func (list *SingleList)Display(){ if list == nil { fmt.Println("this single list is nil") return } list.mutex.RLock() defer list.mutex.RUnlock() fmt.Printf("this single list size is %d \n", list.Size) ptr := list.Head var i uint for i = 0; i < list.Size; i { fmt.Printf("No= data is %v\n", i 1, ptr.Data) ptr = ptr.Next } } </code></pre> <h2>完整实例</h2> <pre><code class="lang-go hljs">package main import "fmt" type Object interface{} type Node struct { Data Object next *Node } type List struct { size uint64 head *Node tail *Node } func (list *List) Init() { (*list).size = 0 (*list).head = nil (*list).tail = nil } // 向链表追加节点 func (list *List) Append(node *Node) bool { if node == nil { return false } (*node).next = nil // 新加节点在末尾，没有next if (*list).size == 0 { (*list).head = node } else { oldTail := (*list).tail // 取尾结点 (*oldTail).next = node // 尾结点的next指向新加节点 } (*list).tail = node // 新节点是尾结点 (*list).size return true } // 向第i个节点处插入节点 func (list *List) Insert(i uint64, node *Node) bool { if node == nil || i > (*list).size || (*list).size == 0 { return false } if i == 0 { (*node).next = (*list).head (*list).head = node } else { preNode := (*list).head for j := uint64(1); j < i; j { preNode = (*preNode).next } (*node).next = (*preNode).next // 新节点指向旧节点原来所指的next (*preNode).next = node // 原节点的next指向新节点 } (*list).size return true } // 移除指定位置的节点 func (list *List) Remove(i uint64) bool { if i >= (*list).size { return false } if i == 0 { preHead := (*list).head // 取出旧的链表头 (*list).head = preHead.next // 旧链表头的next变为新的头 // 如果仅有一个节点，则头尾节点清空 if (*list).size == 1 { (*list).head = nil (*list).tail = nil } } else { preNode := (*list).head for j := uint64(1); j < i; j { preNode = (*preNode).next } node := (*preNode).next // 找到当前要删除的节点 (*preNode).next = node.next // 把当前要删除节点的next赋给其父节点的next,完成后代转移 // 若删除的尾部，尾部指针需要调整 if i == ((*list).size - 1) { (*list).tail = preNode } } (*list).size-- return true } // 移除所有节点 func (list *List) RemoveAll() bool { (*list).Init() return true } // 获取指定位置的节点 func (list *List) Get(i uint64) *Node { if i >= (*list).size { return nil } node := (*list).head for j := uint64(0); j < i; j { node = (*node).next } return node } // 搜索某个数据的节点位置 func (list *List) IndexOf(data Object) int64 { pos := int64(-1) node := (*list).head if node.Data == data { return 0 } for j := uint64(1); j < (*list).size; j { if node != nil { node = (*node).next if node != nil && node.Data == data { pos = int64(j) break } } } return pos } // 取得链表长度 func (list *List) GetSize() uint64 { return (*list).size } // 取得链表头 func (list *List) GetHead() *Node { return (*list).head } // 取得链表尾 func (list *List) GetTail() *Node { return (*list).tail } func main() { var l List l.Init() node1 := &Node{Data: 11111} l.Append(node1) node2 := &Node{Data: 22222} l.Append(node2) node3 := &Node{Data: 33333} l.Append(node3) node4 := &Node{Data: "insert"} l.Insert(1, node4) node5 := &Node{Data: "head"} l.Insert(0, node5) node6 := &Node{Data: "tail"} l.Append(node6) l.Remove(0) l.Remove(1) l.Remove(3) pos1 := l.IndexOf(22222) pos2 := l.IndexOf(44444) fmt.Println(pos1, pos2) fmt.Println(l.GetHead(), l.GetTail(), l.GetSize()) fmt.Println() //l.RemoveAll() for i := uint64(0); i < l.size; i { fmt.Println(l.Get(i)) } } </code></pre>

Golang学习手册之：带你21周搞定Go语言

《Golang学习手册之：带你21周搞定Go语言 - P128 128今日分享面试题》
《数据结构——Golang实现单链表》
《golang 实现单链表》
《用golang实现的单向链表》
《golang 实现单链表》
《Golang之单链表实现》

<blockquote class="layui-elem-quote" style="width: 100%;overflow:hidden"> 作者： snans
链接： https://blog.csdn.net/snans/article/details/105464855
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
</blockquote>

到此这篇关于“Golang学习日志 ━━ 单向链表”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
golang日志服务器_深扒GO日志 | （一）从Go语言的日志包说起
 golang 日志分析_每日一库之 logrus 日志使用教程
 学习golang开始前的准备工作
 GO语言-文件版日志系统
 从零入门 Serverless | 函数计算的可观测性
 从零入门Serverless|函数计算的可观测性
 mysql 优化innodb_flush_log_at_trx_commit的案例介绍
 mysql删除binlog日志及使用日志恢复数据的方法
 零基础学习Go语言
 golang url拆分出domain_回顾腾讯面试经历——golang后端开发岗位

上一篇：【GoLang】GoLang 微服务、开源库等参考资料下一篇：golang学习笔记[4] 网络编程

[关闭]

Golang学习日志 ━━ 单向链表

最近更新

浏览排行