DoublyLinkedList
- Structure
-
Documentation
constructor#getFirst#getFirstNode#getLast#getLastNode#hasNextNode#getNextNode#hasPreviousNode#getPreviousNode#insertAfter#insertNodeAfter#insertBefore#insertNodeBefore#insertFirst#insertNodeFirst#insertLast#insertNodeLast#removeFirst#removeFirstNode#removeLast#removeLastNode#removeNode#add#get#size#contains#isEmpty#remove#clear#nodeIterator#iterator#shuffle#toArray
- Non-Public Properties & Methods
The internal structure of a doubly-linked list consists of elements that have both backward and forward references to the elements before and after them, respectively.
In this particular implementation, this is accomplished with a series of nodes, beginning with a special 'prologue' node, and ending with another special node, the 'epilogue' node.
The use of these special nodes allows us to avoid having to check preceding and successive node references against null or undefined, and allows us to easily check the integrity of a list by ensuring that every internal node (i.e. non-special node, i.e. nodes that are not prologue or epilogue nodes) has a proper preceding and successive node reference. With this configuration, I personally find it much easier to ensure that during iteration, you haven't simply 'fallen off the end' of the list, and if you have, you know something has definitively gone wrong.
One of the advantages of using any type of linked list is that we can modify the contents of the list in constant O(1) time, rather than the linear O(n) time that would be required to modify a more traditional list-type (such as an ArrayList).
Examples of operations that have superior time-complexities for doubly-linked lists (or singly-linked lists, for that matter) over traditional lists are #insertFirst, #insertAfter, or #removeFirst.
Of course, this is not always the case. Doubly-linked lists do have their downsides - random access requires linear time rather than the constant time required for your average array. Accessing the kth element of a doubly-linked list will require k iterations.
Initializes a new DoublyLinkedList with the specified elements.
Parameters:
- elements The elements to add to the list.
public constructor(...elements: E[]) { ... }Returns the first element in this list, or undefined if this list is empty.
Parameters:
- None
Returns The first element in this list, or undefined if this list is empty.
public getFirst(): E | undefined { ... }Returns the first node in this list, or undefined if this list is empty.
Parameters:
- None
Returns The first node in this list, or undefined if this list is empty.
public getFirstNode(): DoublyLinkedListNode<E> | undefined { ... }Returns the last element in this list, or undefined if this list is empty.
Parameters:
- None
Returns The last element in this list, or undefined if this list is empty.
public getLast(): E | undefined { ... }Returns the last node in this list, or undefined if this list is empty.
Parameters:
- None
Returns The last node in this list, or undefined if this list is empty.
public getLastNode(): DoublyLinkedListNode<E> | undefined { ... }Returns true if the provided node has a successive node.
This method will throw an error if an attempt is made to use a node that does belong to this list.
Parameters:
- node The node for which to check for a successive node.
Returns true if the provided node has a successive node.
public hasNextNode(node: DoublyLinkedListNode<E>): boolean { ... }Returns the successive node of the provided node, or undefined if the provided node has no successive sibling.
This method will throw an error if an attempt is made to use a node that does belong to this list.
Parameters:
- node The node for which to retrieve a successive node.
Returns The successive node of the provided node, or undefined if the provided node has no successive sibling.
See DoublyLinkedList#hasNextNode
public getNextNode(node: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> | undefined { ... }Returns true if the provided node has a preceding node.
This method will throw an error if an attempt is made to use a node that does belong to this list.
Parameters:
- node The node for which to check for a preceding node.
Returns true if the provided node has a preceding node.
public hasPreviousNode(node: DoublyLinkedListNode<E>): boolean { ... }Returns the preceding node of the provided node, or undefined if the provided node has no preceding sibling.
This method will throw an error if an attempt is made to use a node that does belong to this list.
Parameters:
- node The node for which to retrieve a preceding node.
Returns The preceding node of the provided node, or undefined if the provided node has no preceding sibling.
See DoublyLinkedList#hasPreviousNode
public getPreviousNode(node: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> | undefined { ... }Creates a new node with the provided content and inserts it after the provided node, returning the newly created node.
This method will throw an error if an attempt is made to use a node that does belong to this list.
Parameters:
- element The content that the newly created node should contain.
- node The node after which the newly created node should be inserted.
Returns The newly created node.
public insertAfter(element: E, node: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> { ... }Inserts the provided node after the specified preceding node, returning the node that was inserted.
This method will throw an error if an attempt is made to use a node that does belong to this list.
Parameters:
- node The node that, after this operation, will be situated after the specified preceding node.
- afterNode The node after which the provided node will be inserted.
Returns The inserted node.
public insertNodeAfter(node: DoublyLinkedListNode<E>, afterNode: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> { ... }Creates a new node with the provided content and inserts it before the provided node, returning the newly created node.
This method will throw an error if an attempt is made to use a node that does belong to this list.
Parameters:
- element The content that the newly created node should contain.
- node The node before which the newly created node should be inserted.
Returns The newly created node.
public insertBefore(element: E, node: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> { ... }Inserts the provided node before the specified succeeding node, returning the node that was inserted.
This method will throw an error if an attempt is made to use a node that does belong to this list.
Parameters:
- node The node that, after this operation, will be situated before the specified succeeding node.
- beforeNode The node before which the provided node will be inserted.
Returns The inserted node.
public insertNodeBefore(node: DoublyLinkedListNode<E>, beforeNode: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> { ... }Creates a new node with the provided content and inserts it at the beginning of the list, returning the newly created node.
Parameters:
- element The content that the newly created node should contain.
Returns The newly created node.
public insertFirst(element: E): DoublyLinkedListNode<E> { ... }Inserts the provided node at the beginning of the list, returning the node that was inserted.
Parameters:
- node The node that, after this operation, will be situated at the beginning of this list.
Returns The inserted node.
public insertNodeFirst(node: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> { ... }Creates a new node with the provided content and inserts it at the end of the list, returning the newly created node.
Parameters:
- element The content that the newly created node should contain.
Returns The newly created node.
public insertLast(element: E): DoublyLinkedListNode<E> { ... }Inserts the provided node at the end of the list, returning the node that was inserted.
Parameters:
- node The node that, after this operation, will be situated at the end of this list.
Returns The inserted node.
public insertNodeLast(node: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> { ... }Removes the first node of the list, returning the removed node's contained element.
Parameters:
- None
Returns The removed node's contained element.
public removeFirst(): E | undefined { ... }Removes the first node of the list, returning the removed node.
Parameters:
- None
Returns The removed node.
public removeFirstNode(): DoublyLinkedListNode<E> | undefined { ... }Removes the last node of the list, returning the removed node's contained element.
Parameters:
- None
Returns The removed node's contained element.
public removeLast(): E | undefined { ... }Removes the last node of the list, returning the removed node.
Parameters:
- None
Returns The removed node.
public removeLastNode(): DoublyLinkedListNode<E> | undefined { ... }Removes the specified node from the list, returning the removed node.
This method will throw an error if an attempt is made to use a node that does belong to this list.
Parameters:
- node The node that should be removed from the list.
Returns The removed node.
public removeNode(node: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> { ... }Creates a new node with the provided content and inserts it at the end of the list, returning the newly created node.
Note that this is an alias method for DoublyLinkedList#insertLast.
Parameters:
- element The content that the newly created node should contain.
Returns The newly created node.
See DoublyLinkedList#insertLast
public add(element: E): void { ... }Attempts to retrieve the element at the provided index in this list, returning undefined if the provided index is out-of-bounds.
Parameters:
- index The index at which to attempt to retrieve an element from this list.
Returns The element in this list at the specified index, or undefined if the provided index is out-of-bounds.
public get(index: number): E | undefined { ... }Returns the number of elements in this list.
Parameters:
- None
Returns The number of elements in this list.
public size(): number { ... }Returns true if this list contains the specified search element.
Parameters:
- searchElement The element to search this list for.
Returns true if this list contains the specified search element.
public contains(searchElement: E): boolean { ... }Returns true if this list contains no items.
Parameters:
- None
Returns true if this list contains no items.
public isEmpty(): boolean { ... }Removes the specified element from this list, returning the removed element or undefined if no such element was present in the list.
Note that this method only removes the first instance occurring in this list (when traversing the list from beginning to end), and does NOT remove all instances of the provided element.
Parameters:
- element The element to remove from this list.
Returns The removed element or undefined if no such element was present in the list.
public remove(element: E): E | undefined { ... }Removes all elements from this list, rendering the list empty.
Parameters:
- None
Returns: Void.
public clear(): void { ... }Returns an iterator over the nodes of this list.
Parameters:
- None
Returns An iterator over the nodes of this list.
public nodeIterator(): AbstractIterator<DoublyLinkedListNode<E>> { ... }Returns an iterator over the elements of this list.
Parameters:
- None
Returns An iterator over the elements of this list.
public iterator(): AbstractIterator<E> { ... }Randomizes the order of the elements in the list.
Parameters:
- iterations The number of times that the list should be shuffled.
Returns: Void.
public shuffle(iterations: number = 1): void { ... }Returns this list represented as an array of its elements.
Parameters:
- None
Returns This list represented as an array of its elements.
public toArray(): E[] { ... }The 'prologue' node of this list - the node that occurs before all other nodes.
Note that this node is purely used to maintain the internal structure of this list, and cannot be accessed in any way outside of the scope of this class.
private prologue: DoublyLinkedListNode<E>;The 'epilogue' node of this list - the node that occurs after all other nodes.
Note that this node is purely used to maintain the internal structure of this list, and cannot be accessed in any way outside of the scope of this class.
private epilogue: DoublyLinkedListNode<E>;Returns the epilogue node of this list.
Parameters:
- None
Returns The epilogue node of this list.
protected getEpilogueNode(): DoublyLinkedListNode<E> { ... }Returns the prologue node of this list.
Parameters:
- None
Returns The prologue node of this list.
protected getPrologueNode(): DoublyLinkedListNode<E> { ... }Creates a new node with the provided content and inserts it between some specified preceding and successive nodes, returning the newly created middle node.
Note that this method will throw an error if, prior to this method's operation, the specified preceding and successive nodes are not adjacent.
Parameters:
- content The content that the newly created node should contain.
- previousNode The node that, after this operation, will be situated just before the 'center' node.
- nextNode The node that, after this operation, will be situated just after the 'center' node.
Returns The newly created and placed 'center' node.
protected insertBetween(content: E, previousNode: DoublyLinkedListNode<E>, nextNode: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> { ... }Inserts the provided node between some specified preceding and successive nodes, returning the middle node.
Note that this method will throw an error if, prior to this method's operation, the specified preceding and successive nodes are not adjacent, or if the provided 'center' node already has sibling nodes.
Parameters:
- centerNode The node that, after this operation, will be situated between the preceding and successive nodes.
- previousNode The node that, after this operation, will be situated just before the 'center' node.
- nextNode The node that, after this operation, will be situated just after the 'center' node.
Returns The newly placed 'center' node.
protected insertNodeBetween(centerNode: DoublyLinkedListNode<E>, previousNode: DoublyLinkedListNode<E>, nextNode: DoublyLinkedListNode<E>): DoublyLinkedListNode<E> { ... }