SLinkedList

SLinkedList

A singly linked list.

Summary
SLinkedListA singly linked list.
Variables
headThe head node being referenced.
tailThe tail node being referenced.
Functions
SLinkedListInitializes an empty list.
appendAppends items to the list.
prependPrepends items to the list.
insertAfterInserts an item after a given iterator or appends it if the iterator is invalid.
removeRemoves the node the iterator is pointing to while moving the iterator to the next node.
removeHeadRemoves the head of the list and returns the head’s data or null if the list is empty.
removeTailRemoves the tail of the list and returns the tail’s data or null if the list is empty.
mergeMerges the current list with all lists specified in the paramaters.
concatConcatenates the current list with all lists specified in the parameters and returns a new linked list.
sortSorts the list.
nodeOfSearches for an item in the list by using strict equality (===) and returns an iterator pointing to the node containing the item or null if the item was not found.
spliceAdds nodes to and removes nodes from the list.
shiftUpRemoves and appends the head node to the tail.
popDownRemoves and prepends the tail node to the head.
reverseReverses the linked list in place.
joinConverts the data in the linked list to strings, inserts the given separator between the elements, concatenates them, and returns the resulting string.
contains@inheritDoc
clear@inheritDoc
getIterator@inheritDoc
getListIteratorCreates a list iterator object pointing to the first node in the list.
Properties
size@inheritDoc
Functions
isEmpty@inheritDoc
toArray@inheritDoc
toStringPrints out a string representing the current object.
dumpPrints out all elements (for debug/demo purposes).

Variables

head

public var head: SListNode

The head node being referenced.  This is the first node in the list.

tail

public var tail: SListNode

The tail node being referenced.  This is the last node in the list.

Functions

SLinkedList

public function SLinkedList(...args)

Initializes an empty list.  You can add initial items by passing them as a comma-separated list of values.

Parameters

argsA list of comma-separated values to append. 

append

public function append(...args):SListNode

Appends items to the list.

Parameters

argsA list of comma-separated values to append. 

Returns

A SListNode object wrapping the data.  If multiple values are added, the returned node represents the node that stores the data of the first argument. 

prepend

public function prepend(...args):SListNode

Prepends items to the list.

Parameters

argsA list of one or more comma-separated values to prepend. 

Returns

A SListNode object wrapping the data.  If multiple values are added, the returned node represents the node that stores the data of the first argument. 

insertAfter

public function insertAfter(itr: SListIterator,
obj: *):SListNode

Inserts an item after a given iterator or appends it if the iterator is invalid.

Parameters

itrAn iterator object pointing to the node after which the given data is inserted.
objThe data to insert. 

Returns

A singly linked list node wrapping the data. 

remove

public function remove(itr: SListIterator):Boolean

Removes the node the iterator is pointing to while moving the iterator to the next node.

Parameters

itrAn iterator object pointing to the node to remove. 

Returns

True if the removal succeeded, otherwise false. 

removeHead

public function removeHead():*

Removes the head of the list and returns the head’s data or null if the list is empty.

Returns

The data which was associated with the removed node. 

removeTail

public function removeTail():*

Removes the tail of the list and returns the tail’s data or null if the list is empty.

Returns

The data which was associated with the removed node. 

merge

public function merge(...args):void

Merges the current list with all lists specified in the paramaters.  The list is directly modified to reflect the changes.  Due to the rearrangement of the node pointers all passed lists become invalid and should be discarded.

Parameters

argsA list of one or more comma-separated SLinkedList objects. 

See Also

concat

concat

public function concat(...args):SLinkedList

Concatenates the current list with all lists specified in the parameters and returns a new linked list.  The original list and all passed lists are left unchanged.

Parameters

argsA list of one or more comma-separated SLinkedList objects. 

Returns

A copy of the current list which also stores the values from the passed lists. 

See Also

merge

sort

public function sort(...sortOptions):void

Sorts the list.  The default sorting algorithm is ‘mergesort’.  If the LinkedList.INSERTION_SORT flag is used, the list is sorted using the insertion sort algorithm instead, which is much faster for nearly sorted lists. 

  • default sort behaviour: mergesort, numeric, ascending
  • sorting is ascending (for character-strings: a precedes z)
  • sorting is case-sensitive: Z precedes a
  • the list is directly modified to reflect the sort order
  • multiple elements that have identical values are placed consecutively in the sorted array in no particular order

Parameters

sortOptions

See Also

//www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html (http:)

nodeOf

public function nodeOf(obj: *,  
from: SListIterator = null):SListIterator

Searches for an item in the list by using strict equality (===) and returns an iterator pointing to the node containing the item or null if the item was not found.

Parameters

param obj The item to search for
param from A SListIterator object pointing to the node in the list from which to start searching for the item. 

Returns

A SListIterator object pointing to the node with the found item or null if no item exists matching the input data or the iterator is invalid. 

splice

public function splice(start: SListIterator,  
deleteCount: uint = 0xffffffff,
...args   ):SLinkedList

Adds nodes to and removes nodes from the list.  This method directly modifies the list without making a copy.

Parameters

startA SListIterator object pointing to the node where the insertion or deletion begins.  The iterator is updated so it still points to the original node, even if the node now belongs to another list.
deleteCountAn integer that specifies the number of nodes to delete.  This number includes the node referenced by the iterator.  If no value is specified for the deleteCount parameter, the method deletes all of the nodes from the start iterator to the tail of the list.  If the value is 0, no nodes are deleted.
argsSpecifies the values to insert into the list, starting at the iterator’s node. 
returnA SListIterator object containing the nodes that were removed from the original list or null if the iterator is invalid. 

shiftUp

public function shiftUp():void

Removes and appends the head node to the tail.

popDown

public function popDown():void

Removes and prepends the tail node to the head.

reverse

public function reverse():void

Reverses the linked list in place.

join

public function join(sep: *):String

Converts the data in the linked list to strings, inserts the given separator between the elements, concatenates them, and returns the resulting string.

Returns

A string consisting of the data converted to strings and separated by the specified parameter. 

contains

public function contains(obj: *):Boolean

@inheritDoc

clear

public function clear():void

@inheritDoc

getIterator

public function getIterator():Iterator

@inheritDoc

getListIterator

public function getListIterator():SListIterator

Creates a list iterator object pointing to the first node in the list.

Returns

A SListIterator object. 

Properties

size

public function get size():int

@inheritDoc

Functions

isEmpty

public function isEmpty():Boolean

@inheritDoc

toArray

public function toArray():Array

@inheritDoc

toString

public function toString():String

Prints out a string representing the current object.

Returns

A string representing the current object. 

dump

public function dump():String

Prints out all elements (for debug/demo purposes).

Returns

A human-readable representation of the structure. 

A ‘java-style’ collection interface.
public var head: SListNode
The head node being referenced.
public var tail: SListNode
The tail node being referenced.
public function SLinkedList(...args)
Initializes an empty list.
public function append(...args):SListNode
Appends items to the list.
public function prepend(...args):SListNode
Prepends items to the list.
public function insertAfter(itr: SListIterator,
obj: *):SListNode
Inserts an item after a given iterator or appends it if the iterator is invalid.
public function remove(itr: SListIterator):Boolean
Removes the node the iterator is pointing to while moving the iterator to the next node.
public function removeHead():*
Removes the head of the list and returns the head’s data or null if the list is empty.
public function removeTail():*
Removes the tail of the list and returns the tail’s data or null if the list is empty.
public function merge(...args):void
Merges the current list with all lists specified in the paramaters.
public function concat(...args):SLinkedList
Concatenates the current list with all lists specified in the parameters and returns a new linked list.
public function sort(...sortOptions):void
Sorts the list.
public function nodeOf(obj: *,  
from: SListIterator = null):SListIterator
Searches for an item in the list by using strict equality (===) and returns an iterator pointing to the node containing the item or null if the item was not found.
public function splice(start: SListIterator,  
deleteCount: uint = 0xffffffff,
...args   ):SLinkedList
Adds nodes to and removes nodes from the list.
public function shiftUp():void
Removes and appends the head node to the tail.
public function popDown():void
Removes and prepends the tail node to the head.
public function reverse():void
Reverses the linked list in place.
public function join(sep: *):String
Converts the data in the linked list to strings, inserts the given separator between the elements, concatenates them, and returns the resulting string.
public function contains(obj: *):Boolean
@inheritDoc
public function clear():void
@inheritDoc
public function getIterator():Iterator
@inheritDoc
public function getListIterator():SListIterator
Creates a list iterator object pointing to the first node in the list.
public function get size():int
@inheritDoc
public function isEmpty():Boolean
@inheritDoc
public function toArray():Array
@inheritDoc
public function toString():String
Prints out a string representing the current object.
public function dump():String
Prints out all elements (for debug/demo purposes).
Close