tango.util.container.LinkedList

License:

BSD style: see license.txt

Version:

Apr 2008: Initial release

Authors:

Kris

Since:

0.99.7

Based upon Doug Lea's Java collection package

class LinkedList(V, alias Reap = Container.reap, alias Heap = Container.DefaultCollect) : IContainer!(V) #
List of singly-linked values
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

Iterator iterator ()
       int opApply (int delegate(ref V value) dg)

       V head ()
       V tail ()
       V head (V value)
       V tail (V value)
       V removeHead ()
       V removeTail ()

       bool contains (V value)
       uint first (V value, uint startingIndex = 0)
       uint last (V value, uint startingIndex = 0)

       LinkedList add (V value)
       LinkedList prepend (V value)
       uint prepend (IContainer!(V) e)
       LinkedList append (V value)
       uint append (IContainer!(V) e)
       LinkedList addAt (uint index, V value)
       uint addAt (uint index, IContainer!(V) e)

       V get (uint index)
       bool take (ref V v)
       uint remove (V value, bool all)
       bool removeAt (uint index)
       uint removeRange (uint fromIndex, uint toIndex)
       uint replace (V oldElement, V newElement, bool all)
       bool replaceAt (uint index, V value)

       LinkedList clear ()
       LinkedList reset ()

       LinkedList subset (uint from, uint length = int.max)
       LinkedList dup ()

       uint size ()
       bool isEmpty ()
       V[] toArray (V[] dst)
       LinkedList sort (Compare!(V) cmp)
       LinkedList check ()
this() #
Create a new empty list
this(Ref l, int c) [protected] #
Special version of constructor needed by dup
~this() #
Clean up when deleted
Alloc allocator() [final] #
Return the configured allocator
Iterator iterator() [final] #
Return a generic iterator for contained elements
int opApply(int delegate(ref V value) dg) [final] #
uint size() [final] #
Return the number of elements contained
LinkedList dup() [final] #
Build an independent copy of the list. The elements themselves are not cloned
bool contains(V value) [final] #
Time complexity: O(n)
V head() [final] #
Time complexity: O(1)
V tail() [final] #
Time complexity: O(n)
V get(uint index) [final] #
Time complexity: O(n)
uint first(V value, uint startingIndex = 0) [final] #
Time complexity: O(n)
uint last(V value, uint startingIndex = 0) [final] #
Time complexity: O(n)
LinkedList subset(uint from, uint length = int.max) [final] #
Time complexity: O(length)
LinkedList clear() [final] #
Time complexity: O(n)
LinkedList reset() [final] #
Reset the HashMap contents and optionally configure a new heap manager. We cannot guarantee to clean up reconfigured allocators, so be sure to invoke reset() before discarding this class
Time complexity: O(n)
bool take(ref V v) [final] #
Takes the first value on the list
Time complexity: O(1)
LinkedList sort(Compare!(V) cmp) [final] #
Uses a merge-sort-based algorithm.
Time complexity: O(n log n)
LinkedList add(V value) [final] #
Time complexity: O(1)
LinkedList prepend(V value) [final] #
Time complexity: O(1)
uint remove(V value, bool all = false) [final] #
Time complexity: O(n)
uint replace(V oldElement, V newElement, bool all = false) [final] #
Time complexity: O(n)
V head(V value) [final] #
Time complexity: O(1)
V removeHead() [final] #
Time complexity: O(1)
LinkedList append(V value) [final] #
Time complexity: O(n)
V tail(V value) [final] #
Time complexity: O(n)
V removeTail() [final] #
Time complexity: O(n)
LinkedList addAt(uint index, V value) [final] #
Time complexity: O(n)
LinkedList removeAt(uint index) [final] #
Time complexity: O(n)
LinkedList replaceAt(uint index, V value) [final] #
Time complexity: O(n)
uint prepend(IContainer!(V) e) [final] #
Time complexity: O(number of elements in e)
uint append(IContainer!(V) e) [final] #
Time complexity: O(n + number of elements in e)
uint addAt(uint index, IContainer!(V) e) [final] #
Time complexity: O(n + number of elements in e)
uint removeRange(uint fromIndex, uint toIndex) [final] #
Time complexity: O(n)
V[] toArray(V[] dst = null) [final] #
Copy and return the contained set of values in an array, using the optional dst as a recipient (which is resized as necessary).
Returns a slice of dst representing the container values. Time complexity: O(n)
bool isEmpty() [final] #
Is this container empty? Time complexity: O(1)
LinkedList check() [final] #
uint instances(V value) [private] #
Time complexity: O(n)
Ref firstCell() [private] #
Ref lastCell() [private] #
Ref cellAt(uint index) [private] #
void checkIndex(uint index) [private] #
void splice_(IContainer!(V) e, Ref hd, Ref tl) [private] #
Splice elements of e between hd and tl. If hd is null return new hd
Returns the count of new elements added
LinkedList clear(bool all) [private] #
Time complexity: O(n)
void increment() [private] #
new element was added
void decrement(Ref p) [private] #
element was removed
void mutate() [private] #
set was changed
struct Iterator [private] #
List iterator
bool valid() #
Did the container change underneath us?
bool next(ref V v) #
Accesses the next value, and returns false when there are no further values to traverse
V* next() #
Return a pointer to the next value, or null when there are no further values to traverse
void insert(V value) #
Insert a new value before the node about to be iterated (or after the node that was just iterated).
bool insertPrior(V value) #
Insert a new value before the value that was just iterated.
Returns true if the prior node existed and the insertion worked. False otherwise.
int opApply(int delegate(ref V value) dg) #
Foreach support
bool remove() #
Remove value at the current iterator location