• Type Parameters:
E - the list element type
All Implemented Interfaces:
Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

extends AbstractSequentialList<E>
implements Deque<E>
DoublyLinkedList implements a doubly linked List data structure, that exposes its ListNodes where the data is stored in.

An element holding ListNode can be removed or added to a DoublyLinkedList in constant time O(1). Other methods that operate on ListNodes directly also have constant runtime. This is also the case for methods that operate on the first(head) and last(tail) node or element. Random access methods have a runtime O(n) that is linearly dependent on the size of the DoublyLinkedList.

A DoublyLinkedList supports null elements but does not support null ListNodes. This class is not thread safe and needs to be synchronized externally if modified by concurrent threads.

The iterators over this list have a fail-fast behavior meaning that they throw a ConcurrentModificationException after they detect a structural modification of the list, that they're not responsible for.

This class is similar to LinkedList. The general difference is that the ListNodes of this List are accessible and can be removed or added directly. To ensure the integrity of the List nodes of this List have a reference to the List they belong to. This increases the memory occupied by this list implementation compared to LinkedList for the same elements. Instances of LinkedList.Node have three references each (the element, next and previous), instances of DoublyLinkedList.ListNode have four (the element, next, previous and the list).

Author:
Timofey Chudakov, Hannes Wellmann

• ### Method Detail

public void addNode​(int index,
Inserts the specified node at the specified position in this list.

This method has a linear runtime complexity O(n) that depends linearly on the distance of the index to the nearest end. Adding node as first or last takes only constant time O(1).

Parameters:
index - index at which the specified node is to be inserted
node - the node to add
Throws:
IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size())
IllegalArgumentException - if node is already part of this or another DoublyLinkedList
NullPointerException - if node is null

Inserts the specified node at the front of this list.

This method has constant runtime complexity O(1).

Parameters:
node - the node to add
Throws:
IllegalArgumentException - if node is already part of this or another DoublyLinkedList
NullPointerException - if node is null

Inserts the specified node at the end of this list.

This method has constant runtime complexity O(1).

Parameters:
node - the node to add
Throws:
IllegalArgumentException - if node is already part of this or another DoublyLinkedList
NullPointerException - if node is null

Inserts the specified node before the specified successor in this list.

This method has constant runtime complexity O(1).

Parameters:
node - the node to add
successor - ListNode before which the node is inserted
Throws:
IllegalArgumentException - if node is already contained in this or another DoublyLinkedList or successor is not contained in this list
NullPointerException - if successor or node is null
• #### getFirstNode

Returns the first node of this list.

This method has constant runtime complexity O(1).

Returns:
the first ListNode of this list
Throws:
NoSuchElementException - if this list is empty
• #### getLastNode

Returns the last node of this list.

This method has constant runtime complexity O(1).

Returns:
the last ListNode of this list
Throws:
NoSuchElementException - if this list is empty
• #### getNode

public DoublyLinkedList.ListNode<E> getNode​(int index)
Returns the node at the specified position in this list.

This method has linear runtime complexity O(n).

Parameters:
index - index of the ListNode to return
Returns:
the ListNode at the specified position in this list
Throws:
IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())
• #### indexOfNode

public int indexOfNode​(DoublyLinkedList.ListNode<E> node)
Returns the index of the specified node in this list, or -1 if this list does not contain the node.

More formally, returns the index i such that node == getNode(i), or -1 if there is no such index. Because a ListNode is contained in at most one list exactly once, the returned index (if not -1) is the only occurrence of that node.

This method has linear runtime complexity O(n) to find node but returns in constant time O(1) if node is not contained in this list.

Parameters:
node - the node to search for
Returns:
the index of the specified node in this list, or -1 if this list does not contain node
Throws:
NullPointerException - if node is null
• #### removeNode

public boolean removeNode​(DoublyLinkedList.ListNode<E> node)
Removes the node from this list. Returns true if node was in this list and is now removed. If node is not contained in this list, the list is left unchanged.

This method has constant runtime complexity O(1).

Parameters:
node - the node to remove from this list
Returns:
true if node was removed from this list
Throws:
NullPointerException - if node is null
• #### nodeOf

public DoublyLinkedList.ListNode<E> nodeOf​(Object element)
Returns the first node holding the specified element in this list. More formally, returns the first ListNode such that Objects.equals(element, node.getValue()), or null if there is no such node.

This method has linear runtime complexity O(n).

Parameters:
element - the element whose ListNode is to return
Returns:
the first ListNode holding the element or null if no node was found
• #### lastNodeOf

public DoublyLinkedList.ListNode<E> lastNodeOf​(Object element)
Returns the last node holding the specified element in this list. More formally, returns the last ListNode such that Objects.equals(element, node.getValue()), or null if there is no such node.

This method has linear runtime complexity O(n).

Parameters:
element - the element whose ListNode is to return
Returns:
the last ListNode holding the element or null if no node was found

Inserts the specified element at the front of this list. Returns the DoublyLinkedList.ListNode allocated to store the value. The returned ListNode is the new head of the list.

This method is equivalent to addFirst(Object) but returns the allocated ListNode.

Parameters:
element - the element to add
Returns:
the ListNode allocated to store the value

Inserts the specified element at the end of this list. Returns the DoublyLinkedList.ListNode allocated to store the value. The returned ListNode is the new tail of the list.

This method is equivalent to addLast(Object) but returns the allocated ListNode.

Parameters:
element - the element to add
Returns:
the ListNode allocated to store the value

E element)
Inserts the specified element before the specified successor in this list. Returns the ListNode allocated to store the value.
Parameters:
successor - ListNode before which the node holding value is inserted
element - the element to add
Returns:
the ListNode allocated to store the value
Throws:
IllegalArgumentException - if successor is not contained in this list
NullPointerException - if successor is null

public void addFirst​(E e)
Specified by:
addFirst in interface Deque<E>

public void addLast​(E e)
Specified by:
addLast in interface Deque<E>
• #### offerFirst

public boolean offerFirst​(E e)
Specified by:
offerFirst in interface Deque<E>
• #### offerLast

public boolean offerLast​(E e)
Specified by:
offerLast in interface Deque<E>
• #### removeFirst

public E removeFirst()
Specified by:
removeFirst in interface Deque<E>
• #### removeLast

public E removeLast()
Specified by:
removeLast in interface Deque<E>
• #### pollFirst

public E pollFirst()
Specified by:
pollFirst in interface Deque<E>
• #### pollLast

public E pollLast()
Specified by:
pollLast in interface Deque<E>
• #### getFirst

public E getFirst()
Specified by:
getFirst in interface Deque<E>
• #### getLast

public E getLast()
Specified by:
getLast in interface Deque<E>
• #### peekFirst

public E peekFirst()
Specified by:
peekFirst in interface Deque<E>
• #### peekLast

public E peekLast()
Specified by:
peekLast in interface Deque<E>
• #### offer

public boolean offer​(E e)
Specified by:
offer in interface Deque<E>
Specified by:
offer in interface Queue<E>
• #### remove

public E remove()
Specified by:
remove in interface Deque<E>
Specified by:
remove in interface Queue<E>
• #### poll

public E poll()
Specified by:
poll in interface Deque<E>
Specified by:
poll in interface Queue<E>
• #### element

public E element()
Specified by:
element in interface Deque<E>
Specified by:
element in interface Queue<E>
• #### peek

public E peek()
Specified by:
peek in interface Deque<E>
Specified by:
peek in interface Queue<E>
• #### push

public void push​(E e)
Specified by:
push in interface Deque<E>
• #### pop

public E pop()
Specified by:
pop in interface Deque<E>
• #### invert

public void invert()
Inverts the list. For instance, calling this method on the list $(a,b,c,\dots,x,y,z)$ will result in the list $(z,y,x,\dots,c,b,a)$. This method does only pointer manipulation, meaning that all the list nodes allocated for the previously added elements are valid after this method finishes.
• #### moveFrom

public void moveFrom​(int index,
Moves all ListNodes of the given sourceList to this list and inserts them all before the node previously at the given position. All the nodes of movedList are moved to this list. When this method terminates this list contains all nodes of movedList and movedList is empty.
Parameters:
index - index of the first element of list in this list after it was added
movedList - the DoublyLinkedList to move to this one
Throws:
NullPointerException - if movedList is null
• #### append

public void append​(DoublyLinkedList<E> movedList)
Appends the movedList to the end of this list. All the elements from movedList are transferred to this list, i.e. the list is empty after calling this method.
Parameters:
movedList - the DoublyLinkedList to append to this one
Throws:
NullPointerException - if movedList is null
• #### prepend

public void prepend​(DoublyLinkedList<E> movedList)
Prepends the movedList to the beginning of this list. All the elements from movedList are transferred to this list, i.e. the movedList is empty after calling this method.
Parameters:
movedList - the DoublyLinkedList to prepend to this one
Throws:
NullPointerException - if movedList is null
• #### circularIterator

public DoublyLinkedList.NodeIterator<E> circularIterator​(E firstElement)
Returns a DoublyLinkedList.NodeIterator that starts at the first DoublyLinkedList.ListNode of this list that is equal to the specified firstElement, iterates in forward direction over the end of this list until the first node.

The first call to DoublyLinkedList.NodeIterator.nextNode() returns the first node that holds a value such that Objects.equals(node.getValue, firstElement) returns true. The returned NodeIterator iterates in forward direction returning the respective next element in subsequent calls to next(Node). The returned iterator ignores the actual bounds of this DoublyLinkedList and iterates until the node before the first one is reached. Its hasNext() returns false if the next node would be the first one.

Parameters:
firstElement - the element equal to the first next()
Returns:
a circular NodeIterator iterating forward from firstElement
• #### reverseCircularIterator

public DoublyLinkedList.NodeIterator<E> reverseCircularIterator​(E firstElement)
Returns a DoublyLinkedList.NodeIterator that starts at the first DoublyLinkedList.ListNode of this list that is equal to the specified firstElement, iterates in reverse direction over the end of this list until the first node.

The first call to DoublyLinkedList.NodeIterator.nextNode() returns the first node that holds a value such that Objects.equals(node.getValue, firstElement) returns true. The returned NodeIterator iterates in reverse direction returning the respective previous element in subsequent calls to next(Node). The returned iterator ignores the actual bounds of this DoublyLinkedList and iterates until the node before the first one is reached. Its hasNext() returns false if the next node would be the first one.

Parameters:
firstElement - the element equal to the first next()
Returns:
a circular NodeIterator iterating backwards from firstElement