搜索
首页后端开发Golanggolang链表底层实现
golang链表底层实现May 13, 2023 am 10:21 AM

一、链表简介

链表是一种数据结构,它由节点组成,每个节点包含数据和指向下一个节点的指针。相对于数组,链表具有动态扩展的优势,因为它不需要一开始就分配一块连续的内存空间。链表分为单向链表、双向链表和循环链表等多种类型。

在本文中,我们将讨论 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中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
您如何使用PPROF工具分析GO性能?您如何使用PPROF工具分析GO性能?Mar 21, 2025 pm 06:37 PM

本文解释了如何使用PPROF工具来分析GO性能,包括启用分析,收集数据并识别CPU和内存问题等常见的瓶颈。

Debian OpenSSL有哪些漏洞Debian OpenSSL有哪些漏洞Apr 02, 2025 am 07:30 AM

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

您如何在GO中编写单元测试?您如何在GO中编写单元测试?Mar 21, 2025 pm 06:34 PM

本文讨论了GO中的编写单元测试,涵盖了最佳实践,模拟技术和有效测试管理的工具。

如何编写模拟对象和存根以进行测试?如何编写模拟对象和存根以进行测试?Mar 10, 2025 pm 05:38 PM

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

如何定义GO中仿制药的自定义类型约束?如何定义GO中仿制药的自定义类型约束?Mar 10, 2025 pm 03:20 PM

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

解释GO反射软件包的目的。您什么时候使用反射?绩效有什么影响?解释GO反射软件包的目的。您什么时候使用反射?绩效有什么影响?Mar 25, 2025 am 11:17 AM

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

如何使用跟踪工具了解GO应用程序的执行流?如何使用跟踪工具了解GO应用程序的执行流?Mar 10, 2025 pm 05:36 PM

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

您如何在GO中使用表驱动测试?您如何在GO中使用表驱动测试?Mar 21, 2025 pm 06:35 PM

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

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

mPDF

mPDF

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

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

安全考试浏览器

安全考试浏览器

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