Golang单链表完整实现：从结构定义到常用操作详解

1. 定义链表节点与结构

在Golang中实现单链表，首先需要定义节点的结构体。每个节点包含存储数据的字段和指向下一个节点的指针。链表结构体则维护一个头指针，用于标识链表的起始位置。

// Node 定义节点
type Node struct {
	Data any
	Next *Node
}

type LinkedList struct {
	headNode *Node // 头指针
}

这里使用 any 类型作为数据容器，使其能够存储任意类型的数据，提高了链表的通用性。

2. 判断链表状态与获取长度

第1步：判断链表是否为空

通过检查头指针 headNode 是否为 nil 来判断链表是否为空。这是大多数其他操作的前置条件检查。

// IsEmpty 判断链表是否为空
func (l *LinkedList) IsEmpty() bool {
    if l.headNode == nil {
        return true
    }
    return false
}

第2步：计算链表长度

从头节点开始遍历链表，直到当前节点为 nil，每经过一个节点计数加一。若链表为空，直接返回0。

// Length 向链表尾部添加结点
func (l *LinkedList) Length() int {
    currentNode := l.headNode
    if currentNode == nil {
        return 0
    }
    length := 0
    for currentNode != nil {
        length++
        currentNode = currentNode.Next
    }
    return length
}

3. 节点添加操作

第3步：从头部添加节点

目的：实现入栈功能，新节点成为新的头节点。
动作：创建新节点，若链表为空则直接设为头节点；否则将新节点的 Next 指向原头节点，并更新 headNode。

// AddFromHead 向链表尾部添加结点
func (l *LinkedList) AddFromHead(data any) {
    node := &Node{data, nil}
    if l.IsEmpty() { // 如果链表为空，设置该node为头结点即可
        l.headNode = node
        return
    }
    // 将头指针指向的头结点设置为该节点的next，并将头指针指向该节点
    node.Next = l.headNode
    l.headNode = node
}

第4步：从尾部添加节点

目的：保持数据追加顺序。
动作：创建新节点，若为空则直接赋值。否则遍历至最后一个节点（即 Next 为 nil 的节点），将其 Next 指向新节点。

// AddFromTail 向链表尾部添加结点
func (l *LinkedList) AddFromTail(data any) {
    node := &Node{data, nil}
    if l.IsEmpty() == true {
        l.headNode = node
        return
    }
    currentNode := l.headNode
    for currentNode.Next != nil { // 直接遍历到最后一个节点
        currentNode = currentNode.Next
    }
    currentNode.Next = node
}

第5步：指定位置插入节点

目的：在中间位置插入数据。
参数：position（下标，从0开始）、data。
动作：处理边界情况（位置<=0时调用 AddFromHead，位置>=长度时调用 AddFromTail）。在有效范围内，找到前驱节点，调整指针连接新节点。

// Insert 向链表中指定位置添加结点，下标0开始
func (l *LinkedList) Insert(position int, data any) {
    if position <= 0 { // 如果位置<=0，就直接在从头部添加
        l.AddFromHead(data)
    } else if position >= l.Length() { // 如果位置>=l.Length()，就直接在从尾部添加
        l.AddFromTail(data)
    } else { // 否则
        node := &Node{data, nil}
        preNode := l.headNode
        count := 0
        for count != position-1 { // 循环退出以后pre刚好在position-1的位置
            preNode = preNode.Next
            count++
        }
        node.Next = preNode.Next
        preNode.Next = node
    }
}

4. 节点删除操作

第6步：删除头部节点

风险提醒：删除操作会改变链表结构，请确保已备份或确认业务逻辑允许。
动作：若为空则提示。否则保存原头节点，将 headNode 移至下一节点，返回被删除节点的数据。

// DeleteHead 删除头部
func (l *LinkedList) DeleteHead() any {
    if l.IsEmpty() {
        fmt.Println("LinkedList is empty")
        return nil
    }
    head := l.headNode
    l.headNode = l.headNode.Next
    return head
}

第7步：删除尾部节点

动作：遍历至倒数第二个节点。记录最后一个节点的数据，将倒数第二个节点的 Next 设为 nil，从而切断对尾节点的引用，实现删除。

// DeleteTail 删除尾部节点
func (l *LinkedList) DeleteTail() any {
    if l.IsEmpty() {
        fmt.Println("LinkedList is empty")
        return nil
    }
    currentNode := l.headNode
    for currentNode.Next.Next != nil { //如果下下个节点为nil，说明下个节点是最后一个节点
        currentNode = currentNode.Next
    }
    data := currentNode.Next.Data
    currentNode.Next = nil // 删除最后一个节点
    return data
}

第8步：按值删除节点

动作：先检查头节点是否匹配，若匹配则执行头删逻辑。否则遍历链表，检查 currentNode.Next 的数据是否等于目标值。若匹配，跳过该节点（CurrentNode.Next = CurrentNode.Next.Next）；若不匹配，继续向后遍历。

// Remove 删除指定节点
func (l *LinkedList) Remove(data any) {
    if l.IsEmpty() {
        return
    }
    currentNode := l.headNode
    if currentNode.Data == data {
        l.headNode = currentNode.Next
    } else {
        for currentNode.Next != nil { // 遍历到倒数第二个节点
            if currentNode.Next.Data == data { // 用下一个节点去比较（保证尾结点不被漏掉），头结点在上面已经比较过了
                currentNode.Next = currentNode.Next.Next
            } else {
                currentNode = currentNode.Next
            }
        }
    }
}

5. 查询与遍历操作

第9步：判断节点是否存在

动作：遍历链表，比对每个节点的数据。若找到匹配值返回 true，遍历结束未找到则返回 false。

// Contain 链表中是否包含某个值的节点
func (l *LinkedList) Contain(data any) bool {
    if l.IsEmpty() {
        return false
    }
    currentNode := l.headNode
    if currentNode.Data == data {
        return true
    }
    for currentNode != nil {
        if currentNode.Data == data {
            return true
n        }
        currentNode = currentNode.Next
    }
    return false
}

第10步：遍历链表输出

动作：从头节点开始，依次打印节点数据并以箭头分隔，直观展示链表连接关系。

// Traverse 遍历单链表
func (l *LinkedList) Traverse() {
    if l.IsEmpty() {
        fmt.Println("LinkedList is empty")
        return
    }
    currentNode := l.headNode
    for currentNode != nil {
        fmt.Printf("%v -> ", currentNode.Data)
        currentNode = currentNode.Next
    }
}

以上就是Golang实现单链表的详细内容，更多关于Golang 数据结构单链表实现优化的资料请关注本站其它相关文章！