Source file src/pkg/container/list/list.go
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 in the linked list. 15 type Element struct { 16 // Next and previous pointers in the doubly-linked list of elements. 17 // The front of the list has prev = nil, and the back has next = nil. 18 next, prev *Element 19 20 // The list to which this element belongs. 21 list *List 22 23 // The contents of this list element. 24 Value interface{} 25 } 26 27 // Next returns the next list element or nil. 28 func (e *Element) Next() *Element { return e.next } 29 30 // Prev returns the previous list element or nil. 31 func (e *Element) Prev() *Element { return e.prev } 32 33 // List represents a doubly linked list. 34 // The zero value for List is an empty list ready to use. 35 type List struct { 36 front, back *Element 37 len int 38 } 39 40 // Init initializes or clears a List. 41 func (l *List) Init() *List { 42 l.front = nil 43 l.back = nil 44 l.len = 0 45 return l 46 } 47 48 // New returns an initialized list. 49 func New() *List { return new(List) } 50 51 // Front returns the first element in the list. 52 func (l *List) Front() *Element { return l.front } 53 54 // Back returns the last element in the list. 55 func (l *List) Back() *Element { return l.back } 56 57 // Remove removes the element from the list 58 // and returns its Value. 59 func (l *List) Remove(e *Element) interface{} { 60 l.remove(e) 61 e.list = nil // do what remove does not 62 return e.Value 63 } 64 65 // remove the element from the list, but do not clear the Element's list field. 66 // This is so that other List methods may use remove when relocating Elements 67 // without needing to restore the list field. 68 func (l *List) remove(e *Element) { 69 if e.list != l { 70 return 71 } 72 if e.prev == nil { 73 l.front = e.next 74 } else { 75 e.prev.next = e.next 76 } 77 if e.next == nil { 78 l.back = e.prev 79 } else { 80 e.next.prev = e.prev 81 } 82 83 e.prev = nil 84 e.next = nil 85 l.len-- 86 } 87 88 func (l *List) insertBefore(e *Element, mark *Element) { 89 if mark.prev == nil { 90 // new front of the list 91 l.front = e 92 } else { 93 mark.prev.next = e 94 } 95 e.prev = mark.prev 96 mark.prev = e 97 e.next = mark 98 l.len++ 99 } 100 101 func (l *List) insertAfter(e *Element, mark *Element) { 102 if mark.next == nil { 103 // new back of the list 104 l.back = e 105 } else { 106 mark.next.prev = e 107 } 108 e.next = mark.next 109 mark.next = e 110 e.prev = mark 111 l.len++ 112 } 113 114 func (l *List) insertFront(e *Element) { 115 if l.front == nil { 116 // empty list 117 l.front, l.back = e, e 118 e.prev, e.next = nil, nil 119 l.len = 1 120 return 121 } 122 l.insertBefore(e, l.front) 123 } 124 125 func (l *List) insertBack(e *Element) { 126 if l.back == nil { 127 // empty list 128 l.front, l.back = e, e 129 e.prev, e.next = nil, nil 130 l.len = 1 131 return 132 } 133 l.insertAfter(e, l.back) 134 } 135 136 // PushFront inserts the value at the front of the list and returns a new Element containing the value. 137 func (l *List) PushFront(value interface{}) *Element { 138 e := &Element{nil, nil, l, value} 139 l.insertFront(e) 140 return e 141 } 142 143 // PushBack inserts the value at the back of the list and returns a new Element containing the value. 144 func (l *List) PushBack(value interface{}) *Element { 145 e := &Element{nil, nil, l, value} 146 l.insertBack(e) 147 return e 148 } 149 150 // InsertBefore inserts the value immediately before mark and returns a new Element containing the value. 151 func (l *List) InsertBefore(value interface{}, mark *Element) *Element { 152 if mark.list != l { 153 return nil 154 } 155 e := &Element{nil, nil, l, value} 156 l.insertBefore(e, mark) 157 return e 158 } 159 160 // InsertAfter inserts the value immediately after mark and returns a new Element containing the value. 161 func (l *List) InsertAfter(value interface{}, mark *Element) *Element { 162 if mark.list != l { 163 return nil 164 } 165 e := &Element{nil, nil, l, value} 166 l.insertAfter(e, mark) 167 return e 168 } 169 170 // MoveToFront moves the element to the front of the list. 171 func (l *List) MoveToFront(e *Element) { 172 if e.list != l || l.front == e { 173 return 174 } 175 l.remove(e) 176 l.insertFront(e) 177 } 178 179 // MoveToBack moves the element to the back of the list. 180 func (l *List) MoveToBack(e *Element) { 181 if e.list != l || l.back == e { 182 return 183 } 184 l.remove(e) 185 l.insertBack(e) 186 } 187 188 // Len returns the number of elements in the list. 189 func (l *List) Len() int { return l.len } 190 191 // PushBackList inserts each element of ol at the back of the list. 192 func (l *List) PushBackList(ol *List) { 193 last := ol.Back() 194 for e := ol.Front(); e != nil; e = e.Next() { 195 l.PushBack(e.Value) 196 if e == last { 197 break 198 } 199 } 200 } 201 202 // PushFrontList inserts each element of ol at the front of the list. The ordering of the passed list is preserved. 203 func (l *List) PushFrontList(ol *List) { 204 first := ol.Front() 205 for e := ol.Back(); e != nil; e = e.Prev() { 206 l.PushFront(e.Value) 207 if e == first { 208 break 209 } 210 } 211 }