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
|
// Package xlist contains extensions to the standard library package container/list.
package xlist
// List is a doubly-linked list.
type List[T any] struct {
front *Node[T]
back *Node[T]
size int
}
// Len returns the number of items in the list.
func (l *List[T]) Len() int { return l.size }
// Front returns the node at the front of the list.
func (l *List[T]) Front() *Node[T] { return l.front }
// Back returns the node at the back of the list.
func (l *List[T]) Back() *Node[T] { return l.back }
// Clear removes all nodes from the list.
func (l *List[T]) Clear() { l.front = nil; l.back = nil; l.size = 0 }
// PushFront adds a new node with the given value to the front of the list.
func (l *List[T]) PushFront(value T) *Node[T] {
node := &Node[T]{
next: l.front,
Value: value,
}
if l.front != nil {
l.front.prev = node
}
l.front = node
if l.back == nil {
l.back = node
}
l.size++
return node
}
// PushBack adds a new node with the given value to the back of the list.
func (l *List[T]) PushBack(value T) *Node[T] {
node := &Node[T]{
prev: l.back,
Value: value,
}
if l.back != nil {
l.back.next = node
}
l.back = node
if l.front == nil {
l.front = node
}
l.size++
return node
}
// InsertBefore adds a new node with the given value before the node mark.
func (l *List[T]) InsertBefore(value T, mark *Node[T]) *Node[T] {
node := &Node[T]{
Value: value,
prev: mark.prev,
next: mark,
}
mark.prev = node
if node.prev != nil {
node.prev.next = node
}
if l.front == mark {
l.front = node
}
l.size++
return node
}
// InsertBefore adds a new node with the given value after the node mark.
func (l *List[T]) InsertAfter(value T, mark *Node[T]) *Node[T] {
node := &Node[T]{
Value: value,
prev: mark,
next: mark.next,
}
mark.next = node
if node.next != nil {
node.next.prev = node
}
if l.back == mark {
l.back = node
}
l.size++
return node
}
// Remove removes node from the list.
func (l *List[T]) Remove(node *Node[T]) {
l.remove(node)
node.prev = nil
node.next = nil
l.size--
}
func (l *List[T]) remove(node *Node[T]) {
if l.front == node {
l.front = l.front.next
} else {
node.prev.next = node.next
}
if l.back == node {
l.back = l.back.prev
} else {
node.next.prev = node.prev
}
}
// MoveBefore moves node just before mark. Afterwards, mark.Prev() == node && node.Next() == mark.
func (l *List[T]) MoveBefore(node *Node[T], mark *Node[T]) {
if node == mark {
return
}
l.remove(node)
node.prev = mark.prev
mark.prev = node
node.next = mark
if node.prev != nil {
node.prev.next = node
}
if l.front == mark {
l.front = node
}
}
// MoveAfter moves node just after mark. Afterwards, mark.Next() == node && node.Prev() == mark.
func (l *List[T]) MoveAfter(node *Node[T], mark *Node[T]) {
if node == mark {
return
}
l.remove(node)
node.next = mark.next
mark.next = node
node.prev = mark
if node.next != nil {
node.next.prev = node
}
if l.back == mark {
l.back = node
}
}
// MoveToFront moves node to the front of the list.
func (l *List[T]) MoveToFront(node *Node[T]) {
l.MoveBefore(node, l.Front())
}
// MoveToFront moves node to the back of the list.
func (l *List[T]) MoveToBack(node *Node[T]) {
l.MoveAfter(node, l.Back())
}
// Node is a node in a linked-list.
type Node[T any] struct {
prev *Node[T]
next *Node[T]
// Value is user-controlled, and never modified by this package.
Value T
}
// Next returns the next node in the list that n is a part of, if there is one.
func (n *Node[T]) Next() *Node[T] {
return n.next
}
// Prev returns the previous node in the list that n is a part of, if there is one.
func (n *Node[T]) Prev() *Node[T] {
return n.prev
}
|
