一、链表简介
链表是一种数据结构,它由节点组成,每个节点包含数据和指向下一个节点的指针。相对于数组,链表具有动态扩展的优势,因为它不需要一开始就分配一块连续的内存空间。链表分为单向链表、双向链表和循环链表等多种类型。
在本文中,我们将讨论 golang 中单向链表的底层实现。
二、单向链表的实现
在 golang 中,单向链表的底层实现采用指针来构建节点之间的关系。每个节点定义如下:
type Node struct { val interface{} next *Node }
其中 val
表示节点的值,next
表示指向下一个节点的指针。单向链表定义如下:
type SinglyLinkedList struct { head *Node }
其中 head
表示链表的头节点,即第一个节点。
接下来,我们将实现链表的常见操作,包括插入、删除、查找和遍历。
1、插入操作
我们先介绍两种插入操作:在链表头插入和在链表末尾插入。
在链表头插入操作如下:
func (l *SinglyLinkedList) InsertAtHead(val interface{}) { node := &Node{val: val} node.next = l.head l.head = node }
创建一个新节点 node
,将节点的值设置为 val
,然后将其指向原头节点 l.head
,最后更新 l.head
指向新节点即可。
在链表末尾插入操作如下:
func (l *SinglyLinkedList) InsertAtTail(val interface{}) { node := &Node{val: val} if l.head == nil { l.head = node } else { curr := l.head for curr.next != nil { curr = curr.next } curr.next = node } }
先创建一个新节点 node
,如果链表为空,则将新节点设置为头节点。否则,从头节点开始遍历链表,直到找到最后一个节点 curr.next == nil
,将其 next
指向新节点即可。
2、删除操作
删除操作包括删除一个指定节点和删除链表中的所有指定节点(相同节点值)。
删除指定节点操作如下:
func (l *SinglyLinkedList) DeleteNode(node *Node) { curr := l.head if curr == node { l.head = curr.next return } for curr.next != nil { if curr.next == node { curr.next = curr.next.next return } curr = curr.next } }
若要删除的节点是头节点,则直接将 l.head
指向其下一个节点即可。否则从头节点开始遍历链表,找到要删除的节点(curr.next == node
),将其 next
指向其下一个节点即可。
删除链表中的所有指定节点操作如下:
func (l *SinglyLinkedList) DeleteNodes(val interface{}) { for l.head != nil && l.head.val == val { l.head = l.head.next } curr := l.head for curr != nil { for curr.next != nil && curr.next.val == val { curr.next = curr.next.next } curr = curr.next } }
若头节点的值为 val
,则依次删除指定节点。接着从头节点开始遍历链表,依次删除相同值的节点即可。
3、查找操作
查找操作主要有两种方式:通过指定节点值查找节点和查找该节点在链表中的索引。
通过指定节点值查找节点操作如下:
func (l *SinglyLinkedList) FindNode(val interface{}) *Node { curr := l.head for curr != nil { if curr.val == val { return curr } curr = curr.next } return nil }
从头节点开始遍历链表,依次比较节点的值与指定值 val
,一旦匹配则返回该节点,否则返回 nil
。
查找该节点在链表中的索引操作如下:
func (l *SinglyLinkedList) FindIndex(node *Node) int { curr := l.head index := 0 for curr != nil { if curr == node { return index } curr = curr.next index++ } return -1 }
从头节点开始遍历链表,依次比较节点是否与指定节点 node
相同,如果相同,则返回该节点所在的索引,否则返回 -1
。
4、遍历操作
遍历操作主要有两种方式:遍历所有节点和遍历所有节点的值。
遍历所有节点操作如下:
func (l *SinglyLinkedList) Traverse() []*Node { nodes := make([]*Node, 0) curr := l.head for curr != nil { nodes = append(nodes, curr) curr = curr.next } return nodes }
从头节点开始遍历链表,将所有节点按顺序加入 nodes
切片中,并返回该切片。
遍历所有节点的值操作如下:
func (l *SinglyLinkedList) TraverseValues() []interface{} { values := make([]interface{}, 0) curr := l.head for curr != nil { values = append(values, curr.val) curr = curr.next } return values }
从头节点开始遍历链表,将所有节点的值按顺序加入 values
切片中,并返回该切片。
三、总结
在 golang 中,单向链表的底层实现采用指针来构建节点之间的关系。通过实现插入、删除、查找和遍历等常见操作,我们更好地理解了链表的本质和优势,也更好地理解 golang 在底层如何实现链表的。在实际开发中,可以将链表应用于很多场景,比如 LRU 缓存、反转链表等。
以上是golang链表底层实现的详细内容。更多信息请关注PHP中文网其他相关文章!

OpenSSL,作为广泛应用于安全通信的开源库,提供了加密算法、密钥和证书管理等功能。然而,其历史版本中存在一些已知安全漏洞,其中一些危害极大。本文将重点介绍Debian系统中OpenSSL的常见漏洞及应对措施。DebianOpenSSL已知漏洞:OpenSSL曾出现过多个严重漏洞,例如:心脏出血漏洞(CVE-2014-0160):该漏洞影响OpenSSL1.0.1至1.0.1f以及1.0.2至1.0.2beta版本。攻击者可利用此漏洞未经授权读取服务器上的敏感信息,包括加密密钥等。

本文演示了创建模拟和存根进行单元测试。 它强调使用接口,提供模拟实现的示例,并讨论最佳实践,例如保持模拟集中并使用断言库。 文章

本文探讨了GO的仿制药自定义类型约束。 它详细介绍了界面如何定义通用功能的最低类型要求,从而改善了类型的安全性和代码可重复使用性。 本文还讨论了局限性和最佳实践

本文讨论了GO的反思软件包,用于运行时操作代码,对序列化,通用编程等有益。它警告性能成本,例如较慢的执行和更高的内存使用,建议明智的使用和最佳

本文使用跟踪工具探讨了GO应用程序执行流。 它讨论了手册和自动仪器技术,比较诸如Jaeger,Zipkin和Opentelemetry之类的工具,并突出显示有效的数据可视化

本文讨论了GO中使用表驱动的测试,该方法使用测试用例表来测试具有多个输入和结果的功能。它突出了诸如提高的可读性,降低重复,可伸缩性,一致性和A


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

mPDF
mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

SublimeText3汉化版
中文版,非常好用

Dreamweaver Mac版
视觉化网页开发工具

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能

安全考试浏览器
Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。