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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package list implements a doubly linked list.
//
// To iterate over a list (where l is a *List):
// for e := l.Front(); e != nil; e = e.Next() {
// // do something with e.Value
// }
//
package list
// Element is an element in the linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// The front of the list has prev = nil, and the back has next = nil.
next, prev *Element
// The list to which this element belongs.
list *List
// The contents of this list element.
Value interface{}
}
// Next returns the next list element or nil.
func (e *Element) Next() *Element { return e.next }
// Prev returns the previous list element or nil.
func (e *Element) Prev() *Element { return e.prev }
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
front, back *Element
len int
}
// Init initializes or clears a List.
func (l *List) Init() *List {
l.front = nil
l.back = nil
l.len = 0
return l
}
// New returns an initialized list.
func New() *List { return new(List) }
// Front returns the first element in the list.
func (l *List) Front() *Element { return l.front }
// Back returns the last element in the list.
func (l *List) Back() *Element { return l.back }
// Remove removes the element from the list
// and returns its Value.
func (l *List) Remove(e *Element) interface{} {
l.remove(e)
e.list = nil // do what remove does not
return e.Value
}
// remove the element from the list, but do not clear the Element's list field.
// This is so that other List methods may use remove when relocating Elements
// without needing to restore the list field.
func (l *List) remove(e *Element) {
if e.list != l {
return
}
if e.prev == nil {
l.front = e.next
} else {
e.prev.next = e.next
}
if e.next == nil {
l.back = e.prev
} else {
e.next.prev = e.prev
}
e.prev = nil
e.next = nil
l.len--
}
func (l *List) insertBefore(e *Element, mark *Element) {
if mark.prev == nil {
// new front of the list
l.front = e
} else {
mark.prev.next = e
}
e.prev = mark.prev
mark.prev = e
e.next = mark
l.len++
}
func (l *List) insertAfter(e *Element, mark *Element) {
if mark.next == nil {
// new back of the list
l.back = e
} else {
mark.next.prev = e
}
e.next = mark.next
mark.next = e
e.prev = mark
l.len++
}
func (l *List) insertFront(e *Element) {
if l.front == nil {
// empty list
l.front, l.back = e, e
e.prev, e.next = nil, nil
l.len = 1
return
}
l.insertBefore(e, l.front)
}
func (l *List) insertBack(e *Element) {
if l.back == nil {
// empty list
l.front, l.back = e, e
e.prev, e.next = nil, nil
l.len = 1
return
}
l.insertAfter(e, l.back)
}
// PushFront inserts the value at the front of the list and returns a new Element containing the value.
func (l *List) PushFront(value interface{}) *Element {
e := &Element{nil, nil, l, value}
l.insertFront(e)
return e
}
// PushBack inserts the value at the back of the list and returns a new Element containing the value.
func (l *List) PushBack(value interface{}) *Element {
e := &Element{nil, nil, l, value}
l.insertBack(e)
return e
}
// InsertBefore inserts the value immediately before mark and returns a new Element containing the value.
func (l *List) InsertBefore(value interface{}, mark *Element) *Element {
if mark.list != l {
return nil
}
e := &Element{nil, nil, l, value}
l.insertBefore(e, mark)
return e
}
// InsertAfter inserts the value immediately after mark and returns a new Element containing the value.
func (l *List) InsertAfter(value interface{}, mark *Element) *Element {
if mark.list != l {
return nil
}
e := &Element{nil, nil, l, value}
l.insertAfter(e, mark)
return e
}
// MoveToFront moves the element to the front of the list.
func (l *List) MoveToFront(e *Element) {
if e.list != l || l.front == e {
return
}
l.remove(e)
l.insertFront(e)
}
// MoveToBack moves the element to the back of the list.
func (l *List) MoveToBack(e *Element) {
if e.list != l || l.back == e {
return
}
l.remove(e)
l.insertBack(e)
}
// Len returns the number of elements in the list.
func (l *List) Len() int { return l.len }
// PushBackList inserts each element of ol at the back of the list.
func (l *List) PushBackList(ol *List) {
last := ol.Back()
for e := ol.Front(); e != nil; e = e.Next() {
l.PushBack(e.Value)
if e == last {
break
}
}
}
// PushFrontList inserts each element of ol at the front of the list. The ordering of the passed list is preserved.
func (l *List) PushFrontList(ol *List) {
first := ol.Front()
for e := ol.Back(); e != nil; e = e.Prev() {
l.PushFront(e.Value)
if e == first {
break
}
}
}
|
