Go语言数据结构之单链表的实例详解

简介

单链表是一个常见的数据结构，它由一系列节点组成，每个节点包含一个值和指向下一个节点的引用。单链表的插入和删除操作比较容易，但是访问操作的效率相对较低。

在Go语言中，可以使用结构体配合指针来实现单链表。

实现思路

为了实现单链表，需要先定义一个节点结构体Node，包含一个value值和一个next指针。通过next指针将所有节点串联起来，实现链表的功能。

type Node struct {
    value interface{} // 节点的值
    next  *Node        // 指向下一个节点的指针
}

func NewNode(v interface{}) *Node {
    return &Node{v, nil}
}

type LinkedList struct {
    head *Node // 单链表头节点
    tail *Node // 单链表尾节点
    size int   // 单链表大小
}

添加节点

向单链表添加节点的方法分两种情况，一种是头插法，另一种是尾插法。其中头插法的时间复杂度为O(1)，尾插法的时间复杂度为O(n)，因为需要遍历整个链表。

头插法

实现头插法可以将新节点插入链表头部。

func (list *LinkedList) AddHead(v interface{}) {
    newNode := NewNode(v)
    if list.head == nil {
        list.head = newNode
        list.tail = newNode
    } else {
        newNode.next = list.head
        list.head = newNode
    }
    list.size++
}

尾插法

实现尾插法可以将新节点插入链表尾部。

func (list *LinkedList) AddTail(v interface{}) {
    newNode := NewNode(v)
    if list.head == nil {
        list.head = newNode
        list.tail = newNode
    } else {
        list.tail.next = newNode
        list.tail = newNode
    }
    list.size++
}

删除节点

删除节点的方法也分两种情况，一种是根据值来删除节点，另一种是根据位置来删除节点。

根据值来删除节点

根据值来删除节点需要在链表中查找该值所对应的节点，并删除它。

func (list *LinkedList) Remove(v interface{}) {
    if list.head == nil {
        return
    }
    if list.head.value == v {
        list.head = list.head.next
        list.size--
        return
    }
    node := list.head
    for node.next != nil {
        if node.next.value == v {
            node.next = node.next.next
            list.size--
            return
        }
        node = node.next
    }
}

根据位置来删除节点

根据位置来删除节点需要遍历链表，找到指定位置的节点。

func (list *LinkedList) RemoveAtIndex(index int) {
    if index < 0 || index >= list.size || list.head == nil {
        return
    }
    if index == 0 {
        list.head = list.head.next
        list.size--
        return
    }
    node := list.head
    for i := 0; i < index-1; i++ {
        node = node.next
    }
    node.next = node.next.next
    if index == list.size-1 {
        list.tail = node
    }
    list.size--
}

示例说明

示例1

list := LinkedList{}
list.AddTail(1)
list.AddTail(2)
list.AddTail(3)
list.AddTail(4)
list.AddTail(5)
list.Remove(3)
fmt.Println(list) // {1 2 4 5}

在这个示例中，我们创建了一个单链表，然后向其中添加5个节点，最后删除了一个值为3的节点，输出链表的内容为{1 2 4 5}。

示例2

list := LinkedList{}
list.AddHead(1)
list.AddHead(2)
list.AddHead(3)
list.AddHead(4)
list.AddHead(5)
list.RemoveAtIndex(2)
fmt.Println(list) // {5 4 2 1}

在这个示例中，我们创建了一个单链表，然后向其中添加5个节点，最后删除了第3个节点，输出链表的内容为{5 4 2 1}。