原文:全栈笔记
谈到链表之前,先说一下线性表。线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表有两种存储方式,一种是顺序存储结构,另一种是链式存储结构。
顺序存储结构就是两个相邻的元素在内存中也是相邻的。这种存储方式的优点是查询的时间复杂度为O(1),通过首地址和偏移量就可以直接访问到某元素,关于查找的适配算法很多,最快可以达到O(logn)。缺点是插入和删除的时间复杂度最坏能达到O(n),如果你在第一个位置插入一个元素,你需要把数组的每一个元素向后移动一位,如果你在第一个位置删除一个元素,你需要把数组的每一个元素向前移动一位。还有一个缺点,就是当你不确定元素的数量时,你开的数组必须保证能够放下元素最大数量,遗憾的是如果实际数量比最大数量少很多时,你开的数组没有用到的内存就只能浪费掉了。
链式存储结构就是两个相邻的元素在内存中可能不是相邻的,每一个元素都有一个指针域,指针域一般是存储着到下一个元素的指针。这种存储方式的优点是插入和删除的时间复杂度为O(1),不会浪费太多内存,添加元素的时候才会申请内存,删除元素会释放内存。缺点是访问的时间复杂度最坏为O(n),关于查找的算法很少,一般只能遍历,这样时间复杂度也是线性(O(n))的了,频繁的申请和释放内存也会消耗时间。
顺序表的特性是随机读取,也就是访问一个元素的时间复杂度是O(1),链式表的特性是插入和删除的时间复杂度为O(1)。要根据实际情况去选取适合自己的存储结构。
链表就是链式存储的线性表。根据指针域的不同,链表分为单向链表、双向链表、循环链表等等。
一、 单向链表(slist)
链表中最简单的一种是单向链表,每个元素包含两个域,值域和指针域,我们把这样的元素称之为节点。每个节点的指针域内有一个指针,指向下一个节点,而最后一个节点则指向一个空值。一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
二、 双向链表
双向链表的指针域有两个指针,每个数据结点分别指向直接后继和直接前驱。单向链表只能从表头开始向后遍历,而双向链表不但可以从前向后遍历,也可以从后向前遍历。除了双向遍历的优点,双向链表的删除的时间复杂度会降为O(1),因为直接通过目的指针就可以找到前驱节点,单向链表得从表头开始遍历寻找前驱节点。双向链表的缺点是每个节点多了一个指针的空间开销。
三、 循环链表
循环链表就是让链表的最后一个节点指向第一个节点,这样就形成了一个圆环,可以循环遍历。单向循环链表可以单向循环遍历,双向循环链表的头节点的指针也要指向最后一个节点,这样的可以双向循环遍历。
下面是用GO实现双向循环链表的核心代码:
package list
//list结构体
type List struct {
root Element //首地址
len int //list 长度
}
//list 节点结构体
type Element struct {
next, prev *Element //指向上一个,下一个节点
//当前节点所属的list
list *List
//当前节点所存值
Value interface{}
}
//初始化空list
func (l *List) Init() *List {
l.root.next = &l.root
l.root.prev = &l.root
l.len = 0
return l
}
//插入一个节点到链表 e 为插入的节点,at 为要插入的位置后面
func (l *List) insert(e, at *Element) *Element {
n := at.next
at.next = e
e.prev = at
e.next = n
n.prev = e
e.list = l
l.len++
return e
}
//获取当前节点下一个节点
func (e *Element) Next() *Element {
if p := e.next; e.list != nil && p != &e.list.root {
return p
}
return nil
}
//获取当前节点上一个节点
func (e *Element) Prev() *Element {
if p := e.prev; e.list != nil && p != &e.list.root {
return p
}
return nil
}
// 返回链表第一个节点
func (l *List) Front() *Element {
if l.len == 0 {
return nil
}
return l.root.next
}
//返回链表最后一个节点
func (l *List) Back() *Element {
if l.len == 0 {
return nil
}
return l.root.prev
}
// 删除节点
func (l *List) remove(e *Element) *Element {
e.prev.next = e.next
e.next.prev = e.prev
e.next = nil // avoid memory leaks
e.prev = nil // avoid memory leaks
e.list = nil
l.len--
return e
}