Package org.jgrapht.util

Class DoublyLinkedList<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>
    public class DoublyLinkedList<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

    • Constructor Detail

      • DoublyLinkedList

        public DoublyLinkedList()

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

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

      • 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:
        java.lang.IllegalArgumentException - if node is already part of this or another DoublyLinkedList
        java.lang.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:
        java.lang.IllegalArgumentException - if node is already part of this or another DoublyLinkedList
        java.lang.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:
        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

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

      • nodeOf

        public DoublyLinkedList.ListNode<E> nodeOf​(java.lang.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​(java.lang.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:
        java.lang.IllegalArgumentException - if successor is not contained in this list
        java.lang.NullPointerException - if successor is null

      • add

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

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

      • addFirst

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

      • addLast

        public void addLast​(E e)
        Specified by:
        addLast in interface java.util.Deque<E>

      • 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,
                     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:
        java.lang.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:
        java.lang.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:
        java.lang.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

      • iterator

        public DoublyLinkedList.NodeIterator<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

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

      • listIterator

        public DoublyLinkedList.ListNodeIterator<E> listIterator​(int index)
        Specified by:
        listIterator in interface java.util.List<E>
        Specified by:
        listIterator in class java.util.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:
        java.util.NoSuchElementException - if element is not in the list