A singly linked list
Example:
var o = new polygonal.ds.Sll<Int>();
for (i in 0...4) o.append(i);
trace(o); //outputs:
[ Sll size=4
head
0 -> 0
1 -> 1
2 -> 2
3 -> 3
]
Constructor
new (reservedSize:Int = 0, ?source:Array<T>)
Parameters:
reservedSize | if > 0, this list maintains an object pool of node objects. Prevents frequent node allocation and thus increases performance at the cost of using more memory. |
|---|
Variables
read onlyisCircular:Bool = false
Returns true if this list is circular.
A list is circular if the tail points to the head.
read onlykey:Int = HashKey.next()
A unique identifier for this object.
A hash table transforms this key into an index of an array element by using a hash function.
reuseIterator:Bool = false
If true, reuses the iterator object instead of allocating a new one when calling this.iterator().
The default is false.
If this value is true, nested iterations will fail as only one iteration is allowed at a time.
Methods
append (val:T):SllNode<T>
Appends val to the tail of this list by creating a SllNode object storing val.
Returns:
the appended node storing val.
clear (gc:Bool = false):Void
Removes all elements.
Parameters:
gc | if true, nodes, pointers and elements are nullified upon removal so the garbage collector can reclaim used memory. |
|---|
clone (byRef:Bool = true, ?copier:T ‑> T):Collection<T>
Creates and returns a shallow copy (structure only - default) or deep copy (structure & elements) of this list.
If byRef is true, primitive elements are copied by value whereas objects are copied by reference.
If byRef is false, the copier function is used for copying elements. If omitted, clone() is called on each element assuming all elements implement Cloneable.
close ():Sll<T>
Makes this list circular by connecting the tail to the head.
Silently fails if this list is already closed.
concat (list:Sll<T>):Sll<T>
Concatenates this list with list by appending all elements of list to this list.
This list and list are left untouched.
Returns:
a new list containing the elements of both lists.
inlinecreateNode (val:T):SllNode<T>
Creates and returns a new SllNode object storing val and pointing to this list.
inlineforEach (f:T ‑> Int ‑> T):Sll<T>
Calls f on all elements.
The function signature is: f(input, index):output
- input: current element
- index: the index number of the given element (0=head)
- output: element to be stored at given index
free ():Void
Destroys this object by explicitly nullifying all nodes, pointers and data for GC'ing used resources.
Improves GC efficiency/performance (optional).
getNodeAt (i:Int):SllNode<T>
Returns the node at "index" i.
The index is measured relative to the head node (= index 0).
getRange (fromIndex:Int, toIndex:Int):List<T>
Returns a Sll object storing elements in the range [fromIndex, toIndex).
If toIndex is negative, the value represents the number of elements.
insert (index:Int, val:T):Void
Inserts val before the element at index (0=head).
If index equals this.size, val gets appended to the end of the list.
insertAfter (node:SllNode<T>, val:T):SllNode<T>
Inserts val after node by creating a SllNode object storing val.
Returns:
the inserted node storing val.
insertBefore (node:SllNode<T>, val:T):SllNode<T>
Inserts val before node by creating a SllNode object storing val.
Returns:
the inserted node storing val.
iterator ():Itr<T>
Returns a new SllIterator object to iterate over all elements contained in this singly linked list.
The elements are visited from head to tail.
If performance is crucial, use the following loop instead:
var node = mySll.head;
while (node != null)
{
var element = node.val;
node = node.next;
}
See:
join (sep:String):String
Converts the data in the linked list to strings, inserts sep between the elements, concatenates them, and returns the resulting string.
merge (list:Sll<T>):Sll<T>
Merges this list with list by linking both lists together.
The merge operation destroys list so it should be discarded.
nodeOf (val:T, ?from:SllNode<T>):SllNode<T>
Searches for val in this list from head to tail starting at node from.
Returns:
the node containing val or null if such a node does not exist.
If from is null, the search starts at the head of this list.
open ():Sll<T>
Makes this list non-circular by disconnecting the tail from the head and vice versa.
Silently fails if this list is already non-circular.
prepend (val:T):SllNode<T>
Prepends val to the head of this list by creating a SllNode object storing val.
Returns:
the prepended node storing val.
remove (val:T):Bool
Removes all nodes storing val.
Returns:
true if at least one occurrence of val was removed.
shuffle (?rvals:Array<Float>):Sll<T>
Shuffles the elements of this collection by using the Fisher-Yates algorithm.
Parameters:
rvals | a list of random double values in the interval [0, 1) defining the new positions of the elements.
If omitted, random values are generated on-the-fly by calling |
|---|
sort (?cmp:T ‑> T ‑> Int, useInsertionSort:Bool = false):Sll<T>
Sorts the elements of this list using the merge sort algorithm.
Parameters:
cmp | a comparison function.
If null, the elements are compared using |
|---|---|
useInsertionSort | if true, the linked list is sorted using the insertion sort algorithm. This is faster for nearly sorted lists. |
toArray ():Array<T>
Returns an array containing all elements in this singly linked list.
The elements are ordered head-to-tail.