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.
5 // The list package implements a doubly linked list.
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
14 // Element is an element in the linked list.
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.
20 // The list to which this element belongs.
23 // The contents of this list element.
27 // Next returns the next list element or nil.
28 func (e
*Element
) Next() *Element
{ return e
.next
}
30 // Prev returns the previous list element or nil.
31 func (e
*Element
) Prev() *Element
{ return e
.prev
}
33 // List represents a doubly linked list.
34 // The zero value for List is an empty list ready to use.
40 // Init initializes or clears a List.
41 func (l
*List
) Init() *List
{
48 // New returns an initialized list.
49 func New() *List
{ return new(List
) }
51 // Front returns the first element in the list.
52 func (l
*List
) Front() *Element
{ return l
.front
}
54 // Back returns the last element in the list.
55 func (l
*List
) Back() *Element
{ return l
.back
}
57 // Remove removes the element from the list
58 // and returns its Value.
59 func (l
*List
) Remove(e
*Element
) interface{} {
61 e
.list
= nil // do what remove does not
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
) {
88 func (l
*List
) insertBefore(e
*Element
, mark
*Element
) {
90 // new front of the list
101 func (l
*List
) insertAfter(e
*Element
, mark
*Element
) {
102 if mark
.next
== nil {
103 // new back of the list
114 func (l
*List
) insertFront(e
*Element
) {
117 l
.front
, l
.back
= e
, e
118 e
.prev
, e
.next
= nil, nil
122 l
.insertBefore(e
, l
.front
)
125 func (l
*List
) insertBack(e
*Element
) {
128 l
.front
, l
.back
= e
, e
129 e
.prev
, e
.next
= nil, nil
133 l
.insertAfter(e
, l
.back
)
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
}
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
}
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
{
155 e
:= &Element
{nil, nil, l
, value
}
156 l
.insertBefore(e
, mark
)
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
{
165 e
:= &Element
{nil, nil, l
, value
}
166 l
.insertAfter(e
, mark
)
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
{
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
{
188 // Len returns the number of elements in the list.
189 func (l
*List
) Len() int { return l
.len }
191 // PushBackList inserts each element of ol at the back of the list.
192 func (l
*List
) PushBackList(ol
*List
) {
194 for e
:= ol
.Front(); e
!= nil; e
= e
.Next() {
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
) {
205 for e
:= ol
.Back(); e
!= nil; e
= e
.Prev() {