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.