• java.lang.Object
• java.util.AbstractCollection<E>
• java.util.AbstractList<E>
• java.util.AbstractSequentialList<E>
• Type Parameters:
E - the list element type
All Implemented Interfaces:
java.lang.Iterable<E>, java.util.Collection<E>, java.util.Deque<E>, java.util.List<E>, java.util.Queue<E>

extends java.util.AbstractSequentialList<E>
implements java.util.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

• #### isEmpty

public boolean isEmpty()
Specified by:
isEmpty in interface java.util.Collection<E>
Specified by:
isEmpty in interface java.util.List<E>
Overrides:
isEmpty in class java.util.AbstractCollection<E>
• #### size

public int size()
Specified by:
size in interface java.util.Collection<E>
Specified by:
size in interface java.util.Deque<E>
Specified by:
size in interface java.util.List<E>
Specified by:
size in class java.util.AbstractCollection<E>
• #### clear

public void clear()
Specified by:
clear in interface java.util.Collection<E>
Specified by:
clear in interface java.util.List<E>
Overrides:
clear in class java.util.AbstractList<E>

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:
java.lang.IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size())
java.lang.IllegalArgumentException - if node is already part of this or another DoublyLinkedList
java.lang.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:
java.lang.IllegalArgumentException - if node is already part of this or another DoublyLinkedList
java.lang.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:
java.lang.IllegalArgumentException - if node is already part of this or another DoublyLinkedList
java.lang.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:
java.lang.IllegalArgumentException - if node is already contained in this or another DoublyLinkedList or successor is not contained in this list
java.lang.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:
java.util.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:
java.util.NoSuchElementException - if this list is empty
• #### getNode

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:
java.lang.IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())
• #### indexOfNode

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:
java.lang.NullPointerException - if node is null
• #### containsNode

This method has constant runtime complexity O(1).

Parameters:
node - the node whose presence in this DoublyLinkedList is to be tested
Returns:
Throws:
java.lang.NullPointerException - if node is null
• #### removeNode

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:
java.lang.NullPointerException - if node is null
• #### nodeOf

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

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:
java.lang.IllegalArgumentException - if successor is not contained in this list
java.lang.NullPointerException - if successor is null

E element)
Specified by:
Overrides:
• #### get

public E get​(int index)
Specified by:
get in interface java.util.List<E>
Overrides:
get in class java.util.AbstractSequentialList<E>
• #### remove

public E remove​(int index)
Specified by:
remove in interface java.util.List<E>
Overrides:
remove in class java.util.AbstractSequentialList<E>

Specified by:

Specified by:
• #### offerFirst

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

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

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

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

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

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

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

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

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

public E peekLast()
Specified by:
peekLast in interface java.util.Deque<E>
• #### removeFirstOccurrence

public boolean removeFirstOccurrence​(java.lang.Object o)
Specified by:
removeFirstOccurrence in interface java.util.Deque<E>
• #### removeLastOccurrence

public boolean removeLastOccurrence​(java.lang.Object o)
Specified by:
removeLastOccurrence in interface java.util.Deque<E>
• #### offer

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

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

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

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

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

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

public E pop()
Specified by:
pop in interface java.util.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:
java.lang.NullPointerException - if movedList is null
• #### append

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:
java.lang.NullPointerException - if movedList is null
• #### prepend

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:
java.lang.NullPointerException - if movedList is null
• #### circularIterator

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

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
• #### descendingIterator

Specified by:
descendingIterator in interface java.util.Deque<E>
• #### iterator

Specified by:
iterator in interface java.util.Collection<E>
Specified by:
iterator in interface java.util.Deque<E>
Specified by:
iterator in interface java.lang.Iterable<E>
Specified by:
iterator in interface java.util.List<E>
Overrides:
iterator in class java.util.AbstractSequentialList<E>
• #### listIterator

Specified by:
listIterator in interface java.util.List<E>
Overrides:
listIterator in class java.util.AbstractList<E>
• #### listIterator

Specified by:
listIterator in interface java.util.List<E>
Specified by:
listIterator in class java.util.AbstractSequentialList<E>