Wghdr's Blog!

go

golang链表

wghdr

介绍

链表（Linked List）是一种常见的数据结构，用于存储和组织数据。与数组不同，链表的元素在内存中不必是连续的，而是通过每个节点中的指针链接在一起。

链表由一个个节点组成，每个节点包含两部分：数据（可以是任意类型的值）和指向下一个节点的指针（或引用）。最后一个节点的指针指向空（NULL）。

类型

  • 单向链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。
  • 双向链表（Doubly Linked List）：每个节点有两个指针，一个指向上一个节点，一个指向下一个节点。
  • 循环链表（Circular Linked List）：尾节点的指针指向头节点，形成一个循环。

优点

  • 动态性：链表可以根据需要动态地分配和释放内存，而数组的长度是固定的。
  • 插入和删除：在链表中插入或删除节点的操作比数组高效，因为它只涉及节点之间的指针改变，而不需要移动大量的元素。

缺点

  • 随机访问效率低：链表中的元素并不是连续存储的，因此无法像数组那样通过索引直接访问特定位置的元素，需要从头节点开始遍历链表。
  • 额外的内存开销：由于每个节点都需要存储指针，链表的存储空间开销比数组大。

常用操作

  • 在链表头部插入节点（头插法）
  • 在链表尾部插入节点（尾插法）
  • 删除指定节点
  • 在指定位置插入节点
  • 遍历链表

代码示例

单向链表

package main

import "fmt"

type Object interface{}

type Node struct {
    Data Object // 定义数据域
    Next *Node  // 定义指针域(指向下一个表的地址)
}

type List struct {
    Head *Node // 头节点
}

// 判断列表是否为空，如果头节点为空，则列表为空
func (l *List) IsEmpty() bool {
    if l.Head == nil {
        return true
    } else {
        return false
    }
}

// 获取列表长度
func (l *List) GetLength() int {
    count := 0
    // 设置当前节点为头节点
    currentNode := l.Head
    // 不断遍历链表直到链表的末尾
    for currentNode != nil {
        count++
        // 将当前节点指针移动到下一个节点
        currentNode = currentNode.Next
    }
    return count
}

// 从链表头部添加元素
func (l *List) AddHead(data Object) {
    node := &Node{Data: data}
    node.Next = l.Head
    l.Head = node
}

// 从链表尾部添加元素
func (l *List) AddTail(data Object) {
    node := &Node{Data: data}
    //node := new(Node)
    if l.IsEmpty() {
        l.Head = node
    } else {
        // 从头节点开始遍历链表
        current := l.Head
        // 找到链表的最后一个节点
        for current.Next != nil {
            current = current.Next
        }
        // 将新节点连接到最后一个节点的Next上
        current.Next = node
    }
}

// 从链表指定位置添加元素
func (l *List) Insert(index int, data Object) {
    if index <= 0 {
        l.AddHead(data)
        return
    } else if index > l.GetLength() {
        l.AddTail(data)
    } else {
        // 设置current为头节点
        current := l.Head
        // 在链表中找到要插入位置的前一个节点
        for i := 0; i < index-1; i++ {
            current = current.Next
        }
        // 创建新节点
        node := &Node{Data: data}
        // 将新节点的 Next 指向当前节点的 Next
        node.Next = current.Next
        // 将当前节点的 Next 指向新节点
        current.Next = node
    }
}

// 从链表指定位置删除元素
func (l *List) DeleteIndex(index int) {
    current := l.Head
    // 如果 index 小于等于 0，将头节点设置为下一个节点，即删除头节点
    if index <= 0 {
        l.Head = current.Next
    } else if index > l.GetLength() {
        // 如果 index 超出链表范围，打印错误信息并返回
        fmt.Println("index out of range")
        return
    } else {
        //for i := 0; i < index-1; i++ {
        //  if current.Next == nil {
        //      fmt.Println("index out of range")
        //      return
        //  }
        //  current = current.Next
        i := 0
        // 将 current 移动到要删除节点的前一个节点，或者已经到达了链表的末尾
        for i != index-1 && current.Next != nil {
            current = current.Next
            i++
        }
        // 删除节点：将前一个节点的 Next 指向要删除节点的下一个节点
        current.Next = current.Next.Next
    }
}

// 丛链表删除指定值的元素
func (l *List) Delete(data Object) {
    current := l.Head
    // 如果头节点的数据与指定数据相等，将头节点设置为下一个节点，即删除头节点
    if current.Data == data {
        l.Head = current.Next
    } else {
        for current.Next != nil {
            // 如果下一个节点的数据与指定数据相等，将当前节点的 Next 指向下一个节点的下一个节点，即删除下一个节点
            if current.Next.Data == data {
                current.Next = current.Next.Next
            } else {
                // 否则，将 current 移动到下一个节点，继续遍历链表
                current = current.Next
            }
        }
    }
}

// 查看链表是否包含某个元素
func (l *List) Contains(data Object) bool {
    current := l.Head
    for current != nil {
        if current.Data == data {
            return true
        }
        current = current.Next
    }
    return false
}

// 遍历链表
func (l *List) Loop() {
    if !l.IsEmpty() {
        current := l.Head
        for {
            fmt.Println("current data:", current.Data)
            if current.Next != nil {
                current = current.Next
                // 如果已经到达链表的末尾，则退出循环
            } else {
                break
            }
        }
    }
}

func main() {
    list := List{}
    list.AddTail("a")
    list.AddTail("b")
    list.AddTail("c")

    fmt.Printf("length:%d\n", list.GetLength())
    fmt.Println("---------")
    list.Loop()

    list.AddHead("A")
    fmt.Println("---------")
    list.Loop()

    list.Delete("b")
    fmt.Println("---------")
    list.Loop()

    list.DeleteIndex(1)
    fmt.Println("---------")
    list.Loop()
}

length:3
---------
current data: a
current data: b
current data: c
---------
current data: A
current data: a
current data: b
current data: c
---------
current data: A
current data: a
current data: c
---------
current data: A
current data: c

双向链表

package main

import "fmt"

type Node struct {
    Data interface{}
    Prev *Node
    Next *Node
}

type DoubleLinkedList struct {
    Head *Node
    Tail *Node
}

// Length 获取链表的长度
func (list *DoubleLinkedList) Length() int {
    length := 0
    current := list.Head
    for current != nil {
        length++
        current = current.Next
    }
    return length
}

// AddHead 在链表头部添加元素
func (list *DoubleLinkedList) AddHead(data interface{}) {
    node := &Node{Data: data, Prev: nil, Next: nil}
    if list.Head == nil {
        list.Head = node
        list.Tail = node
    } else {
        node.Next = list.Head
        list.Head.Prev = node
        list.Head = node
    }
}

// AddTail 在链表尾部添加元素
func (list *DoubleLinkedList) AddTail(data interface{}) {
    node := &Node{Data: data, Prev: nil, Next: nil}
    if list.Head == nil {
        list.Head = node
        list.Tail = node
    } else {
        node.Prev = list.Tail
        list.Tail.Next = node
        list.Tail = node
    }
}

// InsertData 在指定位置插入元素
func (list *DoubleLinkedList) InsertData(index int, data interface{}) {
    node := &Node{Data: data, Prev: nil, Next: nil}
    if index <= 0 {
        list.AddHead(data)
    } else if index >= list.Length() {
        list.AddTail(data)
    } else {
        current := list.Head
        for i := 0; i < index-1; i++ {
            current = current.Next
        }
        node.Prev = current
        node.Next = current.Next
        current.Next.Prev = node
        current.Next = node
    }
}

// DeleteIndex 删除指定位置的元素
func (list *DoubleLinkedList) DeleteIndex(index int) {
    if index < 0 || index > list.Length() {
        return
    }
    if index == 0 {
        list.Head = list.Head.Next
        if list.Head != nil {
            list.Head.Prev = nil
        } else {
            list.Tail = nil
        }
    } else if index == list.Length()-1 {
        list.Tail = list.Tail.Prev
        if list.Tail != nil {
            list.Tail.Next = nil
        } else {
            list.Head = nil
        }
    } else {
        current := list.Head
        for i := 0; i < index-1; i++ {
            current = current.Next
        }
        current.Next = current.Next.Next
        current.Next.Prev = current
    }
}

// DeleteData 删除指定数据的元素
func (list *DoubleLinkedList) DeleteData(data interface{}) {
    current := list.Head
    for current != nil {
        if current.Data == data {
            if current == list.Head {
                list.Head = list.Head.Next
                if list.Head != nil {
                    list.Head.Prev = nil
                } else {
                    list.Tail = nil
                }
            } else if current == list.Tail {
                list.Tail = list.Tail.Prev
                if list.Tail != nil {
                    list.Tail.Next = nil
                } else {
                    list.Head = nil
                }
            } else {
                current.Prev.Next = current.Next
                current.Next.Prev = current.Prev
            }
            break
        }
        current = current.Next
    }
}

// Contains 判断链表中是否包含指定数据
func (list *DoubleLinkedList) Contains(data interface{}) bool {
    current := list.Head
    for current != nil {
        if current.Data == data {
            return true
        }
        current = current.Next
    }
    return false
}

// Print 遍历链表
func (list *DoubleLinkedList) Print() {
    current := list.Head
    for current != nil {
        fmt.Println(current.Data)
        current = current.Next
    }
}

func main() {
    list := &DoubleLinkedList{}
    // 在链表尾部添加元素
    list.AddTail(1)
    list.AddTail(2)
    list.AddTail(3)
    list.Print()
    fmt.Println("----------------")
    // 在链表头部添加元素
    list.AddHead(0)
    list.Print()
    fmt.Println("----------------")
    // 在指定位置插入元素
    list.InsertData(4, 4)
    list.Print()
    fmt.Println("----------------")
    // 删除指定位置的元素
    list.DeleteIndex(1)
    list.Print()
    fmt.Println("----------------")
    // 删除指定数据的元素
    list.DeleteData(4)
    list.Print()
    fmt.Println("----------------")
    // 检查链表是否包含某个元素
    fmt.Println(list.Contains(2))
    fmt.Println(list.Contains(5))
    // 获取链表长度
    fmt.Println(list.Length())
}

1
2
3
----------------
0
1
2
3
----------------
0
1
2
3
4
----------------
0
2
3
4
----------------
0
2
3
----------------
true
false
3

循环链表

通过将链表的尾节点的 Next 指针指向头节点，形成循环的连接。

package main

import "fmt"

type Node struct {
    Data interface{}
    Next *Node
}

type LoopLinkedList struct {
    Head *Node
    Tail *Node
}

// Length 获取链表的长度
func (list *LoopLinkedList) Length() int {
    if list.Head == nil {
        return 0
    }
    // 将 length 初始化为 1，因为头节点已经被计算在内了
    length := 1
    // 将 current 初始化为 cll.Head.Next，表示从头节点的下一个节点开始遍历
    current := list.Head.Next
    // 检查 current 是否等于 cll.Head，如果不是，则将长度加1，并将 current 移动到下一个节点。
    // 重复这个过程直到 current 等于 cll.Head，即回到了头节点，循环结束。
    for current != list.Head {
        length++
        current = current.Next
    }
    return length
}

// AddHead 在链表头部添加元素
func (list *LoopLinkedList) AddHead(data interface{}) {
    node := &Node{Data: data}
    if list.Head == nil {
        list.Head = node
        list.Tail = node
        node.Next = node
    } else {
        node.Next = list.Head
        list.Head = node
        list.Tail.Next = node
    }
}

// AddTail 在链表尾部添加元素
func (list *LoopLinkedList) AddTail(data interface{}) {
    node := &Node{Data: data}
    if list.Head == nil {
        list.Head = node
        list.Tail = node
        node.Next = node
    } else {
        node.Next = list.Head
        list.Tail.Next = node
        list.Tail = node
    }
}

// Insert 在指定位置插入元素
func (list *LoopLinkedList) Insert(index int, data interface{}) {
    if index <= 0 {
        list.AddHead(data)
    } else if index >= list.Length() {
        list.AddTail(data)
    } else {
        node := &Node{Data: data}
        current := list.Head
        for i := 0; i < index; i++ {
            current = current.Next
        }
        node.Next = current.Next
        current.Next = node
    }
}

// DeleteIndex 删除指定位置的元素
func (list *LoopLinkedList) DeleteIndex(index int) {
    // 如果索引小于0或大于等于链表的长度或链表为空，则直接返回
    if index < 0 || index >= list.Length() || list.Head == nil {
        return
    }
    // 要删除的节点是头节点
    if index == 0 {
        // 链表只有一个节点，将头节点和尾节点都设置为 nil，表示链表为空
        if list.Head == list.Tail {
            list.Head = nil
            list.Tail = nil
        } else {
            // 将头节点 list.Head 更新为头节点的下一个节点
            list.Head = list.Head.Next
            // 将尾节点 list.Tail 的 Next 指针指向新的头节点
            list.Tail.Next = list.Head
        }
        // 如果索引 index 不等于 0
    } else {
        current := list.Head
        // 循环的次数为 index-1，将当前节点 current 移动到要删除节点的前一个节点
        for i := 0; i < index-1; i++ {
            current = current.Next
        }
        // 将当前节点 current 的 Next 指针指向要删除节点的下一个节点
        current.Next = current.Next.Next
        // 检查当前节点的下一个节点是否等于头节点，如果成立，说明要删除的节点是循环链表的最后一个节点，也就是尾节点
        if current.Next == list.Head {
            // 将 list.Tail 更新为当前节点 current，以保持循环链表的完整性
            list.Tail = current
        }
    }
}

// DeleteData 删除指定数据的元素
func (list *LoopLinkedList) DeleteData(data interface{}) {
    // 如果链表为空，则直接返回
    if list.Head == nil {
        return
    }
    // 如果链表只有一个元素，直接删除
    if list.Head.Data == data {
        list.DeleteIndex(0)
    } else {
        current := list.Head
        // 循环的终止条件是当前节点的下一个节点等于头节点 current.Next == list.Head
        // 这是因为循环链表的最后一个节点的下一个节点指向头节点。
        for current.Next != list.Head {
            // 检查当前节点的下一个节点的数据是否等于要删除的数据
            if current.Next.Data == data {
                // 将当前节点的 Next 指针指向要删除节点的下一个节点，即 current.Next = current.Next.Next
                current.Next = current.Next.Next
                // 检查当前节点的下一个节点是否等于头节点
                if current.Next == list.Head {
                    // 说明要删除的节点是循环链表的最后一个节点，也就是尾节点
                    // 这时需要更新尾节点的位置，以保持循环链表的完整性
                    list.Tail = current
                }
                break
            }
            current = current.Next
        }
    }
}

// Contains 判断链表中是否包含指定数据
func (list *LoopLinkedList) Contains(data interface{}) bool {
    current := list.Head
    for current != list.Tail {
        if current.Data == data {
            return true
        }
        current = current.Next
    }
    return false
}

// Print 遍历链表
func (list *LoopLinkedList) Print() {
    if list.Head == nil {
        return
    }
    current := list.Head
    for current != list.Tail {
        fmt.Println(current.Data)
        current = current.Next
    }
    fmt.Println(current.Data)
}

func main() {
    list := &LoopLinkedList{}

    // 在链表尾部添加元素
    list.AddTail(1)
    list.AddTail(2)
    list.AddTail(3)
    list.Print()
    fmt.Println("----------------")
    // 在链表头部添加元素
    list.AddHead(0)
    list.Print()
    fmt.Println("----------------")
    // 在指定位置插入元素
    list.Insert(4, 4)
    list.Print()
    fmt.Println("----------------")
    // 删除指定位置的元素
    list.DeleteIndex(1)
    list.Print()
    fmt.Println("----------------")
    // 删除指定数据的元素
    list.DeleteData(4)
    list.Print()
    fmt.Println("----------------")
    // 检查链表是否包含某个元素
    fmt.Println(list.Contains(2))
    fmt.Println(list.Contains(5))
    // 获取链表长度
    fmt.Println(list.Length())
}

1
2
3
----------------
0
1
2
3
----------------
0
1
2
3
4
----------------
0
2
3
4
----------------
0
2
3
----------------
true
false
3

链表的用途

单向链表：

用途：单向链表是最简单的链表形式，每个节点只包含一个指向下一个节点的指针。它适用于需要按顺序访问数据，并且需要频繁进行插入和删除操作的场景。常见的应用包括实现栈（Stack）和队列（Queue），以及在需要动态管理数据集合时，例如在内存有限的情况下。

双向链表：

用途：双向链表在单向链表的基础上，每个节点还包含一个指向前一个节点的指针。它的优点是可以在常量时间内进行向前和向后的遍历，以及在常量时间内进行插入和删除操作。双向链表适用于需要双向遍历的场景，例如在某些算法中需要在前后两个方向上同时进行操作，或者需要在某个节点之前或之后插入或删除节点的情况，实现LRU缓存策略。

循环链表：

用途：循环链表是一种特殊的链表，其尾节点指向头节点，形成一个闭环。循环链表可以无限地循环遍历，可以从任意节点开始遍历整个链表。循环链表常用于需要循环访问的场景，例如在轮播图、循环队列等应用中。

双向链表和循环链表的区别

结构特点

  • 双向链表中的每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点，因此可以从任意方向遍历链表。
  • 循环链表中的最后一个节点的指针指向头节点，形成一个循环连接，可以通过任何节点开始遍历整个链表。

遍历方式

  • 在双向链表中，可以从头节点或尾节点开始遍历，也可以根据需要选择正向或反向遍历链表。
  • 而循环链表可以从任意节点开始遍历，且会无限循环下去，直到遍历完整个链表或满足退出条件。

插入和删除操作

  • 双向链表在插入和删除节点时，可以更高效地操作前后两个节点的指针，因为每个节点都有前后指针，所以不需要像单向链表那样查找前一个节点。
  • 而循环链表在插入和删除节点时，需要特别注意处理头尾节点以保持循环连接的完整性。

内存占用

  • 双向链表相对于单向链表需要更多的空间来存储额外的指针信息，因为每个节点都有两个指针。
  • 循环链表通常比双向链表占用更少的内存空间。这是因为循环链表中不需要额外的指针来存储前一个节点的引用，只需要一个指向下一个节点的指针，因此在存储上更加紧凑。
分类： go
0 0 投票数
文章评分
订阅评论
提醒
guest

0 评论
最旧
最新 最多投票
内联反馈
查看所有评论

相关文章

开始在上面输入您的搜索词，然后按回车进行搜索。按ESC取消。

返回顶部
0
希望看到您的想法，请您发表评论x