链表通常是由大于等于零个具有相同属性的节点连接而成的一串数据，每个节点一般都会包含数据域跟指针域两部分。
比较常用的链表有三种，分别是单(向)链表，双(向)链表和循环链表。
单链表
单链表的特点是其中的每个节点的指针域仅指向它的直接后继节点。
所谓直接后继节点，也就是紧挨着当前节点的下一个节点；对应的还有一个直接前驱节点的概念，指的是该节点紧挨着的前一个节点。单链表的每个节点除头节点外，都有且仅有一个直接前驱，除最后一个节点外的所有节点都有且仅有一个直接后继。
由单链表的结构可以知道，单链表的每个节点仅知道下一个节点的位置，却不知道上一个节点的情况。
单链表中 p 点之后添加新节点的操作：
- 先遍历链表到 p 节点
- 将 p 的指向直接后继存储到另一个变量 t 当中
- 将 p.Next 指向新的节点，将新节点的 Next 指向 t
单链表删除索引为 i 的节点：
- 遍历链表到 i-1 所在的节点 p
- 将 p.Next 指向 p.Next.Next
下面来使用 go 创建一个简单的单链表：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| type LList struct{
Data int
Next *LList
}
func InitList() *LList{
return &LList{
Data: 0,
Next: nil,
}
}
func (l *LList)Append(e, index int){
if l.Len() < index{
return
}
if index == 0 {
l = &LList{
Data: e,
Next: l,
}
return
}
p := l.Next
for i := 0; i < index; i++ {
p = p.Next
}
p.Next = &LList{
Data: e,
Next: p.Next,
}
}
func (l *LList)Delete(index int)int{
if l.Len() < index{
return -1
}
e := 0
if index == 0{
e = l.Data
l = l.Next
return e
}
p := l.Next
for i:=0; i<index; i++{
p = p.Next
}
e = p.Next.Data
p.Next = p.Next.Next
return e
}
func (l *LList)Len()int{
i := 0
p := l
for p != nil{
i+=1
p = p.Next
}
return i
}
|
go 会在声明一个变量的同时对其进行初始化，结构体的零值为 nil。如果你在声明一个节点的时候使用的是 var p *LList，那么在下面任何对 p 结构体内单个条目的操作都会引发空指针的引用错误。
双链表
双链表跟单链表的区别是，双链表比单链表的节点多了一个指针域，指向它的直接前驱。
双链表的每个节点除头节点外，都有且仅有一个直接前驱，除最后一个节点外的所有节点都有且仅有一个直接后继。
双链表的节点结构：
1
2
3
4
| type DList struct{
Data ElemenType
Pre, Next *DList
}
|
因为双链表相较单链表多了一个指针，所以在进行添加删除等操作时需要同时考虑到两个指针的变化。
在双链表的 p 节点后添加新的节点操作：
- 遍历链表到 p 节点
- 先将新节点的 Pre 指针指向 p，并将新节点的 Next 指针指向 p 的直接后继
- 将 p 直接后继的 Pre 指针指向新的节点，并将 p 的 Next 指针指向新的节点
删除索引为 i 的节点：
- 遍历链表至 i-1
- 将索引为 i+1 的节点的 Pre 指针指向 索引为 i-1 的节点
- 将索引为 i-1 的节点的 Next 指针指向索引为 i+1 的节点
双向链表在 go 标准库的 container/list 包中已经实现，可以直接导入使用，此处就不重复说明：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| type Element
func (e *Element) Next() *Element
func (e *Element) Prev() *Element
type List
func New() *List
func (l *List) Back() *Element
func (l *List) Front() *Element
func (l *List) Init() *List
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) Len() int
func (l *List) MoveAfter(e, mark *Element)
func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveToBack(e *Element)
func (l *List) MoveToFront(e *Element)
func (l *List) PushBack(v interface{}) *Element
func (l *List) PushBackList(other *List)
func (l *List) PushFront(v interface{}) *Element
func (l *List) PushFrontList(other *List)
func (l *List) Remove(e *Element) interface{}
|
循环链表
循环链表又分为循环单链表或者循环双链表，它们与上面两种链表的区别在于：循环链表将头节点与最后一个节点以单双链表各自的形式形成了直接前驱后继的关系。
所以在循环链表中的每个节点都有一个直接前驱与直接后继。
因为首尾相接的缘故，循环链表其实可以不必严格区分头节点跟尾节点，因为无论从哪个节点开始都可以遍历整个链表。
除这些区别外，其他的操作与单双链表也基本相同。