GODPAPER | All Packages | All Classes | Index | Frames No Frames |
SLinkedList

Package | de.polygonal.ds
Class | public class SLinkedList
Inheritance | SLinkedList Object
Implements | Collection

A singly linked list.

Public Properties

| Property | Defined By
--- | --- | ---
|  | head : SListNode The head node being referenced. | SLinkedList
|  | size : int [read-only] The total number of items. | SLinkedList
|  | tail : SListNode The tail node being referenced. | SLinkedList

Public Methods

| Method | Defined By
--- | --- | ---
|  | SLinkedList(... args) Initializes an empty list. | SLinkedList
|  | append(... args):SListNode Appends items to the list. | SLinkedList
|  | clear():void Clears all items. | SLinkedList
|  | concat(... args):SLinkedList Concatenates the current list with all lists specified in the parameters and returns a new linked list. | SLinkedList
|  | contains(obj:*):Boolean Determines if the collection contains a given item. | SLinkedList
|  | dump():String Prints out all elements (for debug/demo purposes). | SLinkedList
|  | getIterator():Iterator Initializes an iterator object pointing to the first item in the collection. | SLinkedList
|  | getListIterator():SListIterator Creates a list iterator object pointing to the first node in the list. | SLinkedList
|  | insertAfter(itr:SListIterator, obj:*):SListNode Inserts an item after a given iterator or appends it if the iterator is invalid. | SLinkedList
|  | isEmpty():Boolean Checks if the collection is empty. | SLinkedList
|  | 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. | SLinkedList
|  | merge(... args):void Merges the current list with all lists specified in the paramaters. | SLinkedList
|  | 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. | SLinkedList
|  | popDown():void Removes and prepends the tail node to the head. | SLinkedList
|  | prepend(... args):SListNode Prepends items to the list. | SLinkedList
|  | remove(itr:SListIterator):Boolean Removes the node the iterator is pointing to while moving the iterator to the next node. | SLinkedList
|  | removeHead():* Removes the head of the list and returns the head's data or null if the list is empty. | SLinkedList
|  | removeTail():* Removes the tail of the list and returns the tail's data or null if the list is empty. | SLinkedList
|  | reverse():void Reverses the linked list in place. | SLinkedList
|  | shiftUp():void Removes and appends the head node to the tail. | SLinkedList
|  | sort(... sortOptions):void Sorts the list. | SLinkedList
|  | splice(start:SListIterator, deleteCount:uint = 0xffffffff, ... args):SLinkedList Adds nodes to and removes nodes from the list. | SLinkedList
|  | toArray():Array Converts the collection into an array. | SLinkedList
|  | toString():String Prints out a string representing the current object. | SLinkedList

Public Constants

| Constant | Defined By
--- | --- | ---
|  | DESCENDING : int [static] | SLinkedList
|  | INSERTION_SORT : int [static] | SLinkedList
|  | MERGE_SORT : int [static] | SLinkedList
|  | NUMERIC : int [static] | SLinkedList

Property Detail

head | property

`public var head:SListNode`

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

size | property |

`size:int` [read-only]

The total number of items.

Implementation
`public function get size():int`

tail | property |

`public var tail:SListNode`

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

Constructor Detail

SLinkedList | () | Constructor

`public function SLinkedList(... args)`

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

Parameters

| `... args` — A list of comma-separated values to append.

Method Detail

append | () | method

`public function append(... args):SListNode`

Appends items to the list.

Parameters

| `... args` — A list of comma-separated values to append.

Returns

| `SListNode` — 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.

clear | () | method |

`public function clear():void`

Clears all items.

concat | () | method |

`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

| `... args` — A list of one or more comma-separated SLinkedList objects.

Returns

| `SLinkedList` — A copy of the current list which also stores the values from the passed lists.

See also

merge

contains | () | method |

`public function contains(obj:*):Boolean`

Determines if the collection contains a given item.

Parameters

| `obj:*` — The item to search for.

Returns

| `Boolean` — True if the item exists, otherwise false.

dump | () | method |

`public function dump():String`

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

Returns

| `String` — A human-readable representation of the structure.

getIterator | () | method |

`public function getIterator():Iterator`

Initializes an iterator object pointing to the first item in the collection.

Returns

| `Iterator` — An iterator object.

getListIterator | () | method |

`public function getListIterator():SListIterator`

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

Returns

| `SListIterator`

insertAfter | () | method |

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

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

Parameters

| `itr:SListIterator` — An iterator object pointing to the node after which the given data is inserted.
| `obj:*` — The data to insert.

Returns

| `SListNode` — A singly linked list node wrapping the data.

isEmpty | () | method |

`public function isEmpty():Boolean`

Checks if the collection is empty.

Returns

| `Boolean` — True if empty, otherwise false.

join | () | method |

`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.

Parameters

| `sep:*`

Returns

| `String` — A string consisting of the data converted to strings and separated by the specified parameter.

merge | () | method |

`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

| `... args` — A list of one or more comma-separated SLinkedList objects.

See also

concat

nodeOf | () | method |

`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

| `obj:*` — The item to search for
| `from:SListIterator` (default = `null`)`` — A SListIterator object pointing to the node in the list from which to start searching for the item.

Returns

| `SListIterator` — 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.

popDown | () | method |

`public function popDown():void`

Removes and prepends the tail node to the head.

prepend | () | method |

`public function prepend(... args):SListNode`

Prepends items to the list.

Parameters

| `... args` — A list of one or more comma-separated values to prepend.

Returns

| `SListNode` — 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.

remove | () | method |

`public function remove(itr:SListIterator):Boolean`

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

Parameters

| `itr:SListIterator` — An iterator object pointing to the node to remove.

Returns

| `Boolean` — True if the removal succeeded, otherwise false.

removeHead | () | method |

`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 | () | method |

`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.

reverse | () | method |

`public function reverse():void`

Reverses the linked list in place.

shiftUp | () | method |

`public function shiftUp():void`

Removes and appends the head node to the tail.

sort | () | method |

`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

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

splice | () | method |

`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

| `start:SListIterator` — A 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.
| `deleteCount:uint` (default = `0xffffffff`)`` — An 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.
| `... args` — Specifies the values to insert into the list, starting at the iterator's node.

Returns

| `SLinkedList`

toArray | () | method |

`public function toArray():Array`

Converts the collection into an array.

Returns

| `Array` — An array.

toString | () | method |

`public function toString():String`

Prints out a string representing the current object.

Returns

| `String` — A string representing the current object.

Constant Detail

DESCENDING | Constant

`public static const DESCENDING:int`

INSERTION_SORT | Constant |

`public static const INSERTION_SORT:int`

MERGE_SORT | Constant |

`public static const MERGE_SORT:int`

NUMERIC | Constant |

`public static const NUMERIC:int`

Thu Jan 16 2014, 01:11 PM +08:00