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)
       size_t first (V value, size_t startingIndex = 0)
       size_t last (V value, size_t startingIndex = 0)

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

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

       LinkedList clear ()
       LinkedList reset ()

       LinkedList subset (size_t from, size_t length = size_t.max)
       LinkedList dup ()

       size_t size ()
       bool isEmpty ()
       V[] toArray (V[] dst)
       LinkedList sort (Compare!(V) cmp)
       LinkedList check ()
this() #
Create a new empty list
this(Ref l, size_t c) [protected] #
Special version of constructor needed by dup
~this() #
Clean up when deleted
Iterator iterator() [final] #
Return a generic iterator for contained elements
LinkedList cache(size_t chunk, size_t count = 0) [final] #
Configure the assigned allocator with the size of each allocation block (number of nodes allocated at one time) and the number of nodes to pre-populate the cache with. Time complexity: O(n)
int opApply(int delegate(ref V value) dg) [final] #
size_t 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(size_t index) [final] #
Time complexity: O(n)
size_t first(V value, size_t startingIndex = 0) [final] #
Time complexity: O(n) Returns size_t.max if no element found.
size_t last(V value, size_t startingIndex = 0) [final] #
Time complexity: O(n) Returns size_t.max if no element found.
LinkedList subset(size_t from, size_t length = size_t.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)
size_t remove(V value, bool all = false) [final] #
Time complexity: O(n)
size_t 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(size_t index, V value) [final] #
Time complexity: O(n)
LinkedList removeAt(size_t index) [final] #
Time complexity: O(n)
LinkedList replaceAt(size_t index, V value) [final] #
Time complexity: O(n)
size_t prepend(IContainer!(V) e) [final] #
Time complexity: O(number of elements in e)
size_t append(IContainer!(V) e) [final] #
Time complexity: O(n + number of elements in e)
size_t addAt(size_t index, IContainer!(V) e) [final] #
Time complexity: O(n + number of elements in e)
size_t removeRange(size_t fromIndex, size_t 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] #
size_t instances(V value) [private] #
Time complexity: O(n)
Ref firstCell() [private] #
Ref lastCell() [private] #
Ref cellAt(size_t index) [private] #
void checkIndex(size_t 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