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.Collect): IContainer!(V);

List of singly-linked values

	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);

Special version of constructor needed by dup

Alloc allocator ();

Return the configured allocator

Iterator iterator ();

Return a generic iterator for contained elements

int opApply (int delegate(ref V value) dg);

uint size ();

Return the number of elements contained

LinkedList dup ();

Build an independent copy of the list. The elements themselves are not cloned

bool contains (V value);

Time complexity: O(n)

V head ();

Time complexity: O(1)

V tail ();

Time complexity: O(n)

V get (uint index);

Time complexity: O(n)

uint first (V value, uint startingIndex = 0);

Time complexity: O(n)

uint last (V value, uint startingIndex = 0);

Time complexity: O(n)

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

Time complexity: O(length)

LinkedList clear ();

Time complexity: O(n)

LinkedList reset ();

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);

Takes the first value on the list

Time complexity: O(1)

LinkedList sort (Compare!(V) cmp);

Uses a merge- sort -based algorithm.

Time complexity: O(n log n)

LinkedList add (V value);

Time complexity: O(1)

LinkedList prepend (V value);

Time complexity: O(1)

uint remove (V value, bool all = false);

Time complexity: O(n)

uint replace (V oldElement, V newElement, bool all = false);

Time complexity: O(n)

V head (V value);

Time complexity: O(1)

V removeHead ();

Time complexity: O(1)

LinkedList append (V value);

Time complexity: O(n)

V tail (V value);

Time complexity: O(n)

V removeTail ();

Time complexity: O(n)

LinkedList addAt (uint index, V value);

Time complexity: O(n)

LinkedList removeAt (uint index);

Time complexity: O(n)

LinkedList replaceAt (uint index, V value);

Time complexity: O(n)

uint prepend (IContainer!(V) e);

Time complexity: O(number of elements in e)

uint append (IContainer!(V) e);

Time complexity: O(n + number of elements in e)

uint addAt (uint index, IContainer!(V) e);

Time complexity: O(n + number of elements in e)

uint removeRange (uint fromIndex, uint toIndex);

Time complexity: O(n)

V[] toArray (V[] dst = null);

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 ();

Is this container empty?

Time complexity: O(1)

LinkedList check ();

uint instances (V value);

Time complexity: O(n)

Ref firstCell ();

Ref lastCell ();

Ref cellAt (uint index);

void checkIndex (uint index);

void splice_ (IContainer!(V) e, Ref hd, Ref tl);

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);

Time complexity: O(n)

void increment ();

new element was added

void decrement (Ref p);

element was removed

void mutate ();

set was changed

struct Iterator ;

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
int opApply (int delegate(ref V value) dg);: Foreach support
bool remove ();: Remove value at the current iterator location

anchorFromTitle('tango.util.container.LinkedList', 'source/', 'html');