1 // Copyright 2009 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // Package list implements a doubly linked list. 6 // 7 // To iterate over a list (where l is a *List): 8 // for e := l.Front(); e != nil; e = e.Next() { 9 // // do something with e.Value 10 // } 11 // 12 package list 13 14 // Element is an element of a linked list. 15 type Element struct { 16 // Next and previous pointers in the doubly-linked list of elements. 17 // To simplify the implementation, internally a list l is implemented 18 // as a ring, such that &l.root is both the next element of the last 19 // list element (l.Back()) and the previous element of the first list 20 // element (l.Front()). 21 next, prev *Element 22 23 // The list to which this element belongs. 24 list *List 25 26 // The value stored with this element. 27 Value interface{} 28 } 29 30 // Next returns the next list element or nil. 31 func (e *Element) Next() *Element { 32 if p := e.next; e.list != nil && p != &e.list.root { 33 return p 34 } 35 return nil 36 } 37 38 // Prev returns the previous list element or nil. 39 func (e *Element) Prev() *Element { 40 if p := e.prev; e.list != nil && p != &e.list.root { 41 return p 42 } 43 return nil 44 } 45 46 // List represents a doubly linked list. 47 // The zero value for List is an empty list ready to use. 48 type List struct { 49 root Element // sentinel list element, only &root, root.prev, and root.next are used 50 len int // current list length excluding (this) sentinel element 51 } 52 53 // Init initializes or clears list l. 54 func (l *List) Init() *List { 55 l.root.next = &l.root 56 l.root.prev = &l.root 57 l.len = 0 58 return l 59 } 60 61 // New returns an initialized list. 62 func New() *List { return new(List).Init() } 63 64 // Len returns the number of elements of list l. 65 // The complexity is O(1). 66 func (l *List) Len() int { return l.len } 67 68 // Front returns the first element of list l or nil if the list is empty. 69 func (l *List) Front() *Element { 70 if l.len == 0 { 71 return nil 72 } 73 return l.root.next 74 } 75 76 // Back returns the last element of list l or nil if the list is empty. 77 func (l *List) Back() *Element { 78 if l.len == 0 { 79 return nil 80 } 81 return l.root.prev 82 } 83 84 // lazyInit lazily initializes a zero List value. 85 func (l *List) lazyInit() { 86 if l.root.next == nil { 87 l.Init() 88 } 89 } 90 91 // insert inserts e after at, increments l.len, and returns e. 92 func (l *List) insert(e, at *Element) *Element { 93 e.prev = at 94 e.next = at.next 95 e.prev.next = e 96 e.next.prev = e 97 e.list = l 98 l.len++ 99 return e 100 } 101 102 // insertValue is a convenience wrapper for insert(&Element{Value: v}, at). 103 func (l *List) insertValue(v interface{}, at *Element) *Element { 104 return l.insert(&Element{Value: v}, at) 105 } 106 107 // remove removes e from its list, decrements l.len, and returns e. 108 func (l *List) remove(e *Element) *Element { 109 e.prev.next = e.next 110 e.next.prev = e.prev 111 e.next = nil // avoid memory leaks 112 e.prev = nil // avoid memory leaks 113 e.list = nil 114 l.len-- 115 return e 116 } 117 118 // move moves e to next to at and returns e. 119 func (l *List) move(e, at *Element) *Element { 120 if e == at { 121 return e 122 } 123 e.prev.next = e.next 124 e.next.prev = e.prev 125 126 e.prev = at 127 e.next = at.next 128 e.prev.next = e 129 e.next.prev = e 130 131 return e 132 } 133 134 // Remove removes e from l if e is an element of list l. 135 // It returns the element value e.Value. 136 // The element must not be nil. 137 func (l *List) Remove(e *Element) interface{} { 138 if e.list == l { 139 // if e.list == l, l must have been initialized when e was inserted 140 // in l or l == nil (e is a zero Element) and l.remove will crash 141 l.remove(e) 142 } 143 return e.Value 144 } 145 146 // PushFront inserts a new element e with value v at the front of list l and returns e. 147 func (l *List) PushFront(v interface{}) *Element { 148 l.lazyInit() 149 return l.insertValue(v, &l.root) 150 } 151 152 // PushBack inserts a new element e with value v at the back of list l and returns e. 153 func (l *List) PushBack(v interface{}) *Element { 154 l.lazyInit() 155 return l.insertValue(v, l.root.prev) 156 } 157 158 // InsertBefore inserts a new element e with value v immediately before mark and returns e. 159 // If mark is not an element of l, the list is not modified. 160 // The mark must not be nil. 161 func (l *List) InsertBefore(v interface{}, mark *Element) *Element { 162 if mark.list != l { 163 return nil 164 } 165 // see comment in List.Remove about initialization of l 166 return l.insertValue(v, mark.prev) 167 } 168 169 // InsertAfter inserts a new element e with value v immediately after mark and returns e. 170 // If mark is not an element of l, the list is not modified. 171 // The mark must not be nil. 172 func (l *List) InsertAfter(v interface{}, mark *Element) *Element { 173 if mark.list != l { 174 return nil 175 } 176 // see comment in List.Remove about initialization of l 177 return l.insertValue(v, mark) 178 } 179 180 // MoveToFront moves element e to the front of list l. 181 // If e is not an element of l, the list is not modified. 182 // The element must not be nil. 183 func (l *List) MoveToFront(e *Element) { 184 if e.list != l || l.root.next == e { 185 return 186 } 187 // see comment in List.Remove about initialization of l 188 l.move(e, &l.root) 189 } 190 191 // MoveToBack moves element e to the back of list l. 192 // If e is not an element of l, the list is not modified. 193 // The element must not be nil. 194 func (l *List) MoveToBack(e *Element) { 195 if e.list != l || l.root.prev == e { 196 return 197 } 198 // see comment in List.Remove about initialization of l 199 l.move(e, l.root.prev) 200 } 201 202 // MoveBefore moves element e to its new position before mark. 203 // If e or mark is not an element of l, or e == mark, the list is not modified. 204 // The element and mark must not be nil. 205 func (l *List) MoveBefore(e, mark *Element) { 206 if e.list != l || e == mark || mark.list != l { 207 return 208 } 209 l.move(e, mark.prev) 210 } 211 212 // MoveAfter moves element e to its new position after mark. 213 // If e or mark is not an element of l, or e == mark, the list is not modified. 214 // The element and mark must not be nil. 215 func (l *List) MoveAfter(e, mark *Element) { 216 if e.list != l || e == mark || mark.list != l { 217 return 218 } 219 l.move(e, mark) 220 } 221 222 // PushBackList inserts a copy of another list at the back of list l. 223 // The lists l and other may be the same. They must not be nil. 224 func (l *List) PushBackList(other *List) { 225 l.lazyInit() 226 for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() { 227 l.insertValue(e.Value, l.root.prev) 228 } 229 } 230 231 // PushFrontList inserts a copy of another list at the front of list l. 232 // The lists l and other may be the same. They must not be nil. 233 func (l *List) PushFrontList(other *List) { 234 l.lazyInit() 235 for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() { 236 l.insertValue(e.Value, &l.root) 237 } 238 } 239