// 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 of a linked list. type Element struct { // Next and previous pointers in the doubly-linked list of elements. // To simplify the implementation, internally a list l is implemented // as a ring, such that &l.root is both the next element of the last // list element (l.Back()) and the previous element of the first list // element (l.Front()). next, prev *Element // The list to which this element belongs. list *List // The value stored with this element. Value interface{} } // Next returns the next list element or nil. func ( *Element) () *Element { if := .next; .list != nil && != &.list.root { return } return nil } // Prev returns the previous list element or nil. func ( *Element) () *Element { if := .prev; .list != nil && != &.list.root { return } return nil } // List represents a doubly linked list. // The zero value for List is an empty list ready to use. type List struct { root Element // sentinel list element, only &root, root.prev, and root.next are used len int // current list length excluding (this) sentinel element } // Init initializes or clears list l. func ( *List) () *List { .root.next = &.root .root.prev = &.root .len = 0 return } // New returns an initialized list. func () *List { return new(List).Init() } // Len returns the number of elements of list l. // The complexity is O(1). func ( *List) () int { return .len } // Front returns the first element of list l or nil if the list is empty. func ( *List) () *Element { if .len == 0 { return nil } return .root.next } // Back returns the last element of list l or nil if the list is empty. func ( *List) () *Element { if .len == 0 { return nil } return .root.prev } // lazyInit lazily initializes a zero List value. func ( *List) () { if .root.next == nil { .Init() } } // insert inserts e after at, increments l.len, and returns e. func ( *List) (, *Element) *Element { .prev = .next = .next .prev.next = .next.prev = .list = .len++ return } // insertValue is a convenience wrapper for insert(&Element{Value: v}, at). func ( *List) ( interface{}, *Element) *Element { return .insert(&Element{Value: }, ) } // remove removes e from its list, decrements l.len, and returns e. func ( *List) ( *Element) *Element { .prev.next = .next .next.prev = .prev .next = nil // avoid memory leaks .prev = nil // avoid memory leaks .list = nil .len-- return } // move moves e to next to at and returns e. func ( *List) (, *Element) *Element { if == { return } .prev.next = .next .next.prev = .prev .prev = .next = .next .prev.next = .next.prev = return } // Remove removes e from l if e is an element of list l. // It returns the element value e.Value. // The element must not be nil. func ( *List) ( *Element) interface{} { if .list == { // if e.list == l, l must have been initialized when e was inserted // in l or l == nil (e is a zero Element) and l.remove will crash .remove() } return .Value } // PushFront inserts a new element e with value v at the front of list l and returns e. func ( *List) ( interface{}) *Element { .lazyInit() return .insertValue(, &.root) } // PushBack inserts a new element e with value v at the back of list l and returns e. func ( *List) ( interface{}) *Element { .lazyInit() return .insertValue(, .root.prev) } // InsertBefore inserts a new element e with value v immediately before mark and returns e. // If mark is not an element of l, the list is not modified. // The mark must not be nil. func ( *List) ( interface{}, *Element) *Element { if .list != { return nil } // see comment in List.Remove about initialization of l return .insertValue(, .prev) } // InsertAfter inserts a new element e with value v immediately after mark and returns e. // If mark is not an element of l, the list is not modified. // The mark must not be nil. func ( *List) ( interface{}, *Element) *Element { if .list != { return nil } // see comment in List.Remove about initialization of l return .insertValue(, ) } // MoveToFront moves element e to the front of list l. // If e is not an element of l, the list is not modified. // The element must not be nil. func ( *List) ( *Element) { if .list != || .root.next == { return } // see comment in List.Remove about initialization of l .move(, &.root) } // MoveToBack moves element e to the back of list l. // If e is not an element of l, the list is not modified. // The element must not be nil. func ( *List) ( *Element) { if .list != || .root.prev == { return } // see comment in List.Remove about initialization of l .move(, .root.prev) } // MoveBefore moves element e to its new position before mark. // If e or mark is not an element of l, or e == mark, the list is not modified. // The element and mark must not be nil. func ( *List) (, *Element) { if .list != || == || .list != { return } .move(, .prev) } // MoveAfter moves element e to its new position after mark. // If e or mark is not an element of l, or e == mark, the list is not modified. // The element and mark must not be nil. func ( *List) (, *Element) { if .list != || == || .list != { return } .move(, ) } // PushBackList inserts a copy of another list at the back of list l. // The lists l and other may be the same. They must not be nil. func ( *List) ( *List) { .lazyInit() for , := .Len(), .Front(); > 0; , = -1, .Next() { .insertValue(.Value, .root.prev) } } // PushFrontList inserts a copy of another list at the front of list l. // The lists l and other may be the same. They must not be nil. func ( *List) ( *List) { .lazyInit() for , := .Len(), .Back(); > 0; , = -1, .Prev() { .insertValue(.Value, &.root) } }