Module org.jgrapht.core
Package org.jgrapht.util

Class DoublyLinkedList<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.AbstractSequentialList<E>
org.jgrapht.util.DoublyLinkedList<E>
Type Parameters:
E - the list element type
All Implemented Interfaces:
Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>
public class DoublyLinkedList<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

  • Constructor Details

    • DoublyLinkedList

      public DoublyLinkedList()

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface Collection<E>
      Specified by:
      isEmpty in interface List<E>
      Overrides:
      isEmpty in class AbstractCollection<E>

    • size

      public int size()
      Specified by:
      size in interface Collection<E>
      Specified by:
      size in interface Deque<E>
      Specified by:
      size in interface List<E>
      Specified by:
      size in class AbstractCollection<E>

    • clear

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

    • addNode

      public void addNode(int index, DoublyLinkedList.ListNode<E> node)
      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

    • addNodeFirst

      public void addNodeFirst(DoublyLinkedList.ListNode<E> node)
      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

    • addNodeLast

      public void addNodeLast(DoublyLinkedList.ListNode<E> node)
      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

    • addNodeBefore

      public void addNodeBefore(DoublyLinkedList.ListNode<E> node, DoublyLinkedList.ListNode<E> successor)
      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

      public DoublyLinkedList.ListNode<E> 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

      public DoublyLinkedList.ListNode<E> 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

    • containsNode

      public boolean containsNode(DoublyLinkedList.ListNode<E> node)
      Returns true if this DoublyLinkedList contains the specified DoublyLinkedList.ListNode.

      This method has constant runtime complexity O(1).

      Parameters:
      node - the node whose presence in this DoublyLinkedList is to be tested
      Returns:
      true if this DoublyLinkedList contains the DoublyLinkedList.ListNode
      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

    • addElementFirst

      public DoublyLinkedList.ListNode<E> addElementFirst(E element)
      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

    • addElementLast

      public DoublyLinkedList.ListNode<E> addElementLast(E element)
      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

    • addElementBeforeNode

      public DoublyLinkedList.ListNode<E> addElementBeforeNode(DoublyLinkedList.ListNode<E> successor, 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

    • add

      public void add(int index, E element)
      Specified by:
      add in interface List<E>
      Overrides:
      add in class AbstractSequentialList<E>

    • get

      public E get(int index)
      Specified by:
      get in interface List<E>
      Overrides:
      get in class AbstractSequentialList<E>

    • remove

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

    • addFirst

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

    • addLast

      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>

    • removeFirstOccurrence

      public boolean removeFirstOccurrence(Object o)
      Specified by:
      removeFirstOccurrence in interface Deque<E>

    • removeLastOccurrence

      public boolean removeLastOccurrence(Object o)
      Specified by:
      removeLastOccurrence 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, DoublyLinkedList<E> movedList)
      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

    • descendingIterator

      public DoublyLinkedList.NodeIterator<E> descendingIterator()
      Specified by:
      descendingIterator in interface Deque<E>

    • iterator

      public DoublyLinkedList.NodeIterator<E> iterator()
      Specified by:
      iterator in interface Collection<E>
      Specified by:
      iterator in interface Deque<E>
      Specified by:
      iterator in interface Iterable<E>
      Specified by:
      iterator in interface List<E>
      Overrides:
      iterator in class AbstractSequentialList<E>

    • listIterator

      public DoublyLinkedList.ListNodeIterator<E> listIterator()
      Specified by:
      listIterator in interface List<E>
      Overrides:
      listIterator in class AbstractList<E>

    • listIterator

      public DoublyLinkedList.ListNodeIterator<E> listIterator(int index)
      Specified by:
      listIterator in interface List<E>
      Specified by:
      listIterator in class AbstractSequentialList<E>

    • listIterator

      public DoublyLinkedList.ListNodeIterator<E> listIterator(E element)
      Returns a DoublyLinkedList.ListNodeIterator over the elements in this list (in proper sequence) starting with the first DoublyLinkedList.ListNode whose value is equal to the specified element.
      Parameters:
      element - the first element to be returned from the list iterator (by a call to the next method)
      Returns:
      a list iterator over the elements in this list (in proper sequence)
      Throws:
      NoSuchElementException - if element is not in the list