Class LinkedDeque<E extends Linked<E>>

  • Type Parameters:
    E - the type of elements held in this collection
    All Implemented Interfaces:
    java.lang.Iterable<E>, java.util.Collection<E>, java.util.Deque<E>, java.util.Queue<E>

    @NotThreadSafe
    final class LinkedDeque<E extends Linked<E>>
    extends java.util.AbstractCollection<E>
    implements java.util.Deque<E>
    Linked list implementation of the Deque interface where the link pointers are tightly integrated with the element. Linked deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads. Null elements are prohibited.

    Most LinkedDeque operations run in constant time by assuming that the Linked parameter is associated with the deque instance. Any usage that violates this assumption will result in non-deterministic behavior.

    The iterators returned by this class are not fail-fast: If the deque is modified at any time after the iterator is created, the iterator will be in an unknown state. Thus, in the face of concurrent modification, the iterator risks arbitrary, non-deterministic behavior at an undetermined time in the future.

    See Also:
    http://code.google.com/p/concurrentlinkedhashmap/
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) E first
      Pointer to first node.
      (package private) E last
      Pointer to last node.
    • Constructor Summary

      Constructors 
      Constructor Description
      LinkedDeque()  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(E e)  
      void addFirst​(E e)  
      void addLast​(E e)  
      (package private) void checkNotEmpty()  
      void clear()  
      (package private) boolean contains​(Linked<?> e)  
      boolean contains​(java.lang.Object o)  
      java.util.Iterator<E> descendingIterator()  
      E element()  
      E getFirst()  
      E getLast()  
      boolean isEmpty()  
      java.util.Iterator<E> iterator()  
      (package private) void linkFirst​(E e)
      Links the element to the front of the deque so that it becomes the first element.
      (package private) void linkLast​(E e)
      Links the element to the back of the deque so that it becomes the last element.
      void moveToBack​(E e)
      Moves the element to the back of the deque so that it becomes the last element.
      void moveToFront​(E e)
      Moves the element to the front of the deque so that it becomes the first element.
      boolean offer​(E e)  
      boolean offerFirst​(E e)  
      boolean offerLast​(E e)  
      E peek()  
      E peekFirst()  
      E peekLast()  
      E poll()  
      E pollFirst()  
      E pollLast()  
      E pop()  
      void push​(E e)  
      E remove()  
      (package private) boolean remove​(E e)  
      boolean remove​(java.lang.Object o)  
      boolean removeAll​(java.util.Collection<?> c)  
      E removeFirst()  
      boolean removeFirstOccurrence​(java.lang.Object o)  
      E removeLast()  
      boolean removeLastOccurrence​(java.lang.Object o)  
      int size()
      (package private) void unlink​(E e)
      Unlinks the non-null element.
      (package private) E unlinkFirst()
      Unlinks the non-null first element.
      (package private) E unlinkLast()
      Unlinks the non-null last element.
      • Methods inherited from class java.util.AbstractCollection

        addAll, containsAll, retainAll, toArray, toArray, toString
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Collection

        addAll, containsAll, equals, hashCode, parallelStream, removeIf, retainAll, spliterator, stream, toArray, toArray
      • Methods inherited from interface java.lang.Iterable

        forEach
    • Field Detail

      • first

        E extends Linked<E> first
        Pointer to first node. Invariant: (first == null && last == null) || (first.prev == null)
      • last

        E extends Linked<E> last
        Pointer to last node. Invariant: (first == null && last == null) || (last.next == null)
    • Constructor Detail

      • LinkedDeque

        LinkedDeque()
    • Method Detail

      • linkFirst

        void linkFirst​(E e)
        Links the element to the front of the deque so that it becomes the first element.
        Parameters:
        e - the unlinked element
      • linkLast

        void linkLast​(E e)
        Links the element to the back of the deque so that it becomes the last element.
        Parameters:
        e - the unlinked element
      • unlinkFirst

        E unlinkFirst()
        Unlinks the non-null first element.
      • unlinkLast

        E unlinkLast()
        Unlinks the non-null last element.
      • unlink

        void unlink​(E e)
        Unlinks the non-null element.
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Collection<E extends Linked<E>>
        Overrides:
        isEmpty in class java.util.AbstractCollection<E extends Linked<E>>
      • checkNotEmpty

        void checkNotEmpty()
      • size

        public int size()

        Beware that, unlike in most collections, this method is NOT a constant-time operation.

        Specified by:
        size in interface java.util.Collection<E extends Linked<E>>
        Specified by:
        size in interface java.util.Deque<E extends Linked<E>>
        Specified by:
        size in class java.util.AbstractCollection<E extends Linked<E>>
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection<E extends Linked<E>>
        Overrides:
        clear in class java.util.AbstractCollection<E extends Linked<E>>
      • contains

        public boolean contains​(java.lang.Object o)
        Specified by:
        contains in interface java.util.Collection<E extends Linked<E>>
        Specified by:
        contains in interface java.util.Deque<E extends Linked<E>>
        Overrides:
        contains in class java.util.AbstractCollection<E extends Linked<E>>
      • contains

        boolean contains​(Linked<?> e)
      • moveToFront

        public void moveToFront​(E e)
        Moves the element to the front of the deque so that it becomes the first element.
        Parameters:
        e - the linked element
      • moveToBack

        public void moveToBack​(E e)
        Moves the element to the back of the deque so that it becomes the last element.
        Parameters:
        e - the linked element
      • peek

        public E peek()
        Specified by:
        peek in interface java.util.Deque<E extends Linked<E>>
        Specified by:
        peek in interface java.util.Queue<E extends Linked<E>>
      • peekFirst

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

        public E peekLast()
        Specified by:
        peekLast in interface java.util.Deque<E extends Linked<E>>
      • getFirst

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

        public E getLast()
        Specified by:
        getLast in interface java.util.Deque<E extends Linked<E>>
      • element

        public E element()
        Specified by:
        element in interface java.util.Deque<E extends Linked<E>>
        Specified by:
        element in interface java.util.Queue<E extends Linked<E>>
      • offer

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

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

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

        public boolean add​(E e)
        Specified by:
        add in interface java.util.Collection<E extends Linked<E>>
        Specified by:
        add in interface java.util.Deque<E extends Linked<E>>
        Specified by:
        add in interface java.util.Queue<E extends Linked<E>>
        Overrides:
        add in class java.util.AbstractCollection<E extends Linked<E>>
      • addFirst

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

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

        public E poll()
        Specified by:
        poll in interface java.util.Deque<E extends Linked<E>>
        Specified by:
        poll in interface java.util.Queue<E extends Linked<E>>
      • pollFirst

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

        public E pollLast()
        Specified by:
        pollLast in interface java.util.Deque<E extends Linked<E>>
      • remove

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

        public boolean remove​(java.lang.Object o)
        Specified by:
        remove in interface java.util.Collection<E extends Linked<E>>
        Specified by:
        remove in interface java.util.Deque<E extends Linked<E>>
        Overrides:
        remove in class java.util.AbstractCollection<E extends Linked<E>>
      • remove

        boolean remove​(E e)
      • removeFirst

        public E removeFirst()
        Specified by:
        removeFirst in interface java.util.Deque<E extends Linked<E>>
      • removeFirstOccurrence

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

        public E removeLast()
        Specified by:
        removeLast in interface java.util.Deque<E extends Linked<E>>
      • removeLastOccurrence

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

        public boolean removeAll​(java.util.Collection<?> c)
        Specified by:
        removeAll in interface java.util.Collection<E extends Linked<E>>
        Overrides:
        removeAll in class java.util.AbstractCollection<E extends Linked<E>>
      • push

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

        public E pop()
        Specified by:
        pop in interface java.util.Deque<E extends Linked<E>>
      • iterator

        public java.util.Iterator<E> iterator()
        Specified by:
        iterator in interface java.util.Collection<E extends Linked<E>>
        Specified by:
        iterator in interface java.util.Deque<E extends Linked<E>>
        Specified by:
        iterator in interface java.lang.Iterable<E extends Linked<E>>
        Specified by:
        iterator in class java.util.AbstractCollection<E extends Linked<E>>
      • descendingIterator

        public java.util.Iterator<E> descendingIterator()
        Specified by:
        descendingIterator in interface java.util.Deque<E extends Linked<E>>