Package org.jgrapht.util

Class 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 Detail

      • DoublyLinkedList

        public DoublyLinkedList()

    • Method Detail

      • 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

      • 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

      • 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

      • 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

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

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

      • poll

        public E poll()
        Specified by:
        poll in interface Deque<E>
        Specified by:
        poll 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