golang链表底层实现

一、链表简介

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

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