链表定义
是一种线性表，非顺序存储数据，而是在每一个节点里存到下一个节点的指针。
链表特性
- 非顺序存储数据：可以快速实现动态扩容，缩容。
- 非顺序存储数据：频繁的malloc，free 容易造成内存碎片,参照Slab,伙伴算法。
- 查找特性时间复杂度:O(n), 删除，添加时间复杂度 O(1).
链表延伸
- LRU，Queue，Stack 等多种高级数据结构基于链表实现。
链表种类
- 单链表
type Node struct {
Next *Node
}
https://github.com/xc8801/Data-Structures/tree/master/LinkedList
- 双向链表
type Node struct{
Pre *Node
Next *Node
}
https://github.com/xc8801/Data-Structures/tree/master/DoublyLinkedList
- 循环链表
type Node struct {
Next *Node
}
type CircleLinkedList struct {
Head *Node
Tail *Node
}
网友评论