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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
package list
//结构体
//双向链表中的元素抽象
type Element struct {
next, prev *Element
//该元素属于哪个list，相当于链表的头指针
list *List
//具体记录数据
Value interface{}
}
//返回后继元素
func (e *Element) Next() *Element {
//只有list的root会存在next等于自己
if p := e.next; e.list != nil && p != &e.list.root {
return p
}
return nil
}
//返回前驱元素
func (e *Element) Prev() *Element {
//只有list的root会存在prev等于自己
if p := e.prev; e.list != nil && p != &e.list.root {
return p
}
return nil
}
//双向链表List的定义
type List struct {
//list的头结点，是没有值的，见Init函数的构建过程
root Element
//定义长度
len int
}
func (l *List) Init() *List {
l.root.next = &l.root
l.root.prev = &l.root
l.len = 0
return l
}
//初始化
func New() *List { return new(List).Init() }
//返回list的长度
func (l *List) Len() int { return l.len }
//返回list的下一个元素
func (l *List) Front() *Element {
if l.len == 0 {
return nil
}
return l.root.next
}
//返回list的上一个元素
func (l *List) Back() *Element {
if l.len == 0 {
return nil
}
return l.root.prev
}
//懒加载
func (l *List) lazyInit() {
if l.root.next == nil {
l.Init()
}
}
//at元素后面加一个元素e
//经典双向链表的插入，只是e需要把list指向当前list
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 (l *List) insertValue(v interface{}, at *Element) *Element {
return l.insert(&Element{Value: v}, at)
}
//移除元素e
//经典的双链表删除元素
func (l *List) remove(e *Element) *Element {
e.prev.next = e.next
e.next.prev = e.prev
e.next = nil //避免内存泄漏
e.prev = nil
e.list = nil
l.len--
return e
}
//移除list的元素e
func (l *List) Remove(e *Element) interface{} {
if e.list == l {
l.remove(e)
}
return e.Value
}
//list的头部插入值为v的元素
func (l *List) PushFront(v interface{}) *Element {
l.lazyInit()
return l.insertValue(v, &l.root)
}
//list的末尾插入值为v的元素
func (l *List) PushBack(v interface{}) *Element {
l.lazyInit()
return l.insertValue(v, l.root.prev)
}
//mark前面插入值为v的节点
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {
if mark.list != l {
return nil
}
return l.insertValue(v, mark.prev)
}
//mark后门插入值为v的节点
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {
if mark.list != l {
return nil
}
return l.insertValue(v, mark)
}
//将节点e移动到root的后门，可视为前置
func (l *List) MoveToFront(e *Element) {
//e的list不是l或者e已经是单节点了
if e.list != l || l.root.next == e {
return
}
//打一套组合拳
//先删除然后移动到root的后门
l.insert(l.remove(e), &l.root)
}
//将节点e移动到root的前面，可视为后置
func (l *List) MoveToBack(e *Element) {
if e.list != l || l.root.prev == e {
return
}
l.insert(l.remove(e), l.root.prev)
}
func (l *List) MoveBefore(e, mark *Element) {
if e.list != l || e == mark || mark.list != l {
return
}
l.insert(l.remove(e), mark.prev)
}
func (l *List) MoveAfter(e, mark *Element) {
if e.list != l || e == mark || mark.list != l {
return
}
l.insert(l.remove(e), mark)
}
//合并其他list到l的最后
func (l *List) PushBackList(other *List) {
l.lazyInit()
for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
l.insertValue(e.Value, l.root.prev)
}
}
//合并其他list到l的前面
func (l *List) PushFrontList(other *List) {
l.lazyInit()
for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
l.insertValue(e.Value, &l.root)
}
}
|