当前位置：首页 > news >正文

go语言实现无头单向链表

news 2025/8/21 17:26:37

什么是无头单向链表

无头单向链表是一种线性数据结构，它的每个元素都是一个节点，每个节点都有一个指向下一个节点的指针。"无头"意味着这个链表没有一个特殊的头节点，链表的第一个节点就是链表的头。

优点：

动态大小：链表的大小是动态的，可以在运行时添加或删除节点，这使得它在处理不确定数量的数据时非常有用。
插入和删除效率高：在链表中插入或删除一个节点只需要改变一些指针，而不需要移动节点。如果你有一个指向要插入或删除位置的指针，这个操作可以在常数时间内完成。
可以用于实现许多高级数据结构：链表可以用于实现许多其他高级数据结构，如堆栈、队列、图等。

缺点：

访问效率低：访问链表中的元素需要从头节点开始遍历，这在链表很长时可能会很慢。链表不支持随机访问，每次查找都需要从头开始。
额外的存储空间：链表的每个节点都需要额外的存储空间来存储指向下一个节点的指针，这在存储空间有限的情况下可能是一个问题。
复杂性：链表的操作比数组复杂，特别是在插入和删除节点时，需要处理一些边界条件，如空链表、只有一个节点的链表等。

代码


// 无头单向链表
type LinkNode struct {Val  intNext *LinkNode
}type LinkedList struct {Head *LinkNode
}func NewLinkedList() *LinkedList {return &LinkedList{Head: nil,}
}func (l *LinkedList) Add(val int) {newNode := &LinkNode{Val: val}if l.Head == nil {l.Head = newNode} else {cur := l.Headfor cur.Next != nil {cur = cur.Next}cur.Next = newNode}
}func (l *LinkedList) Get() {cur := l.Headfor cur != nil {println(cur.Val)cur = cur.Next}
}func main() {linkedList := NewLinkedList()linkedList.Add(1)linkedList.Add(2)linkedList.Add(3)linkedList.Get()
}