搜索
首页后端开发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
Golang vs. Python:利弊Golang vs. Python:利弊Apr 21, 2025 am 12:17 AM

Golangisidealforbuildingscalablesystemsduetoitsefficiencyandconcurrency,whilePythonexcelsinquickscriptinganddataanalysisduetoitssimplicityandvastecosystem.Golang'sdesignencouragesclean,readablecodeanditsgoroutinesenableefficientconcurrentoperations,t

Golang和C:并发与原始速度Golang和C:并发与原始速度Apr 21, 2025 am 12:16 AM

Golang在并发性上优于C ,而C 在原始速度上优于Golang。1)Golang通过goroutine和channel实现高效并发,适合处理大量并发任务。2)C 通过编译器优化和标准库,提供接近硬件的高性能,适合需要极致优化的应用。

为什么要使用Golang?解释的好处和优势为什么要使用Golang?解释的好处和优势Apr 21, 2025 am 12:15 AM

选择Golang的原因包括:1)高并发性能,2)静态类型系统,3)垃圾回收机制,4)丰富的标准库和生态系统,这些特性使其成为开发高效、可靠软件的理想选择。

Golang vs.C:性能和速度比较Golang vs.C:性能和速度比较Apr 21, 2025 am 12:13 AM

Golang适合快速开发和并发场景,C 适用于需要极致性能和低级控制的场景。1)Golang通过垃圾回收和并发机制提升性能,适合高并发Web服务开发。2)C 通过手动内存管理和编译器优化达到极致性能,适用于嵌入式系统开发。

golang比C快吗?探索极限golang比C快吗?探索极限Apr 20, 2025 am 12:19 AM

Golang在编译时间和并发处理上表现更好,而C 在运行速度和内存管理上更具优势。1.Golang编译速度快,适合快速开发。2.C 运行速度快,适合性能关键应用。3.Golang并发处理简单高效,适用于并发编程。4.C 手动内存管理提供更高性能,但增加开发复杂度。

Golang:从Web服务到系统编程Golang:从Web服务到系统编程Apr 20, 2025 am 12:18 AM

Golang在Web服务和系统编程中的应用主要体现在其简洁、高效和并发性上。1)在Web服务中,Golang通过强大的HTTP库和并发处理能力,支持创建高性能的Web应用和API。2)在系统编程中,Golang利用接近硬件的特性和对C语言的兼容性,适用于操作系统开发和嵌入式系统。

Golang vs.C:基准和现实世界的表演Golang vs.C:基准和现实世界的表演Apr 20, 2025 am 12:18 AM

Golang和C 在性能对比中各有优劣:1.Golang适合高并发和快速开发,但垃圾回收可能影响性能;2.C 提供更高性能和硬件控制,但开发复杂度高。选择时需综合考虑项目需求和团队技能。

Golang vs. Python:比较分析Golang vs. Python:比较分析Apr 20, 2025 am 12:17 AM

Golang适合高性能和并发编程场景,Python适合快速开发和数据处理。 1.Golang强调简洁和高效,适用于后端服务和微服务。 2.Python以简洁语法和丰富库着称,适用于数据科学和机器学习。

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脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

VSCode Windows 64位 下载

VSCode Windows 64位 下载

微软推出的免费、功能强大的一款IDE编辑器

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

EditPlus 中文破解版

EditPlus 中文破解版

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

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 英文版

SublimeText3 英文版

推荐:为Win版本,支持代码提示!