Package com.linkedin.alpini.base.misc

Class DoublyLinkedList<E extends DoublyLinkedList.Entry<E>>

  • 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 DoublyLinkedList.Entry<E>>
extends java.util.AbstractSequentialList<E>
implements java.util.Deque<E>
    Linked list implementation of the List interface. Implements all optional list operations, but only permits elements of the DoublyLinkedList.Entry class. In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue. The class implements the Deque interface, providing first-in-first-out queue operations for add, poll, along with other stack and deque operations. All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index. Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static class  DoublyLinkedList.Entry<E extends DoublyLinkedList.Entry<E>>
      In order to maintain a doubly-linked list, each element needs to establish links to its adjacent elements.

    • Field Summary

      • Fields inherited from class java.util.AbstractList

        modCount

    • Constructor Summary

      Constructors 
      Constructor Description
      DoublyLinkedList()
      Constructs an empty list.
      DoublyLinkedList​(java.util.Collection<? extends E> source)
      Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addFirst​(E e)
      Inserts the specified element at the beginning of this list.
      void addLast​(E e)
      Appends the specified element to the end of this list.
      boolean contains​(java.lang.Object o)
      Returns true if this list contains the specified element.
      java.util.Iterator<E> descendingIterator()
      Returns an iterator over the elements in reverse sequential order.
      E element()
      Returns the first element in this list.
      E getFirst()
      Returns the first element in this list.
      E getLast()
      Returns the last element in this list.
      java.util.ListIterator<E> listIterator​(int i)
      Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.
      boolean offer​(E e)
      Adds the specified element as the tail (last element) of this list.
      boolean offerFirst​(E e)
      Inserts the specified element at the front of this list.
      boolean offerLast​(E e)
      Inserts the specified element at the end of this list.
      E peek()  
      E peekFirst()
      Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
      E peekLast()
      Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.
      E poll()
      Retrieves and removes the head (first element) of this list
      E pollFirst()
      Retrieves and removes the first element of this list, or returns null if this list is empty.
      E pollLast()
      Retrieves and removes the last element of this list, or returns null if this list is empty.
      E pop()
      Pops an element from the stack represented by this list.
      void push​(E e)
      Pushes an element onto the stack represented by this list.
      E remove()
      Retrieves and removes the head (first element) of this list.
      boolean remove​(java.lang.Object o)
      Removes the first occurrence of the specified element from this list, if it is present.
      E removeFirst()
      Removes and returns the first element from this list.
      boolean removeFirstOccurrence​(java.lang.Object o)
      Removes the first occurrence of the specified element in this list.
      E removeLast()
      Removes and returns the last element from this list.
      boolean removeLastOccurrence​(java.lang.Object o)
      Removes the last occurrence of the specified element in this list
      int size()
      Returns the number of elements in this list.
      protected boolean unlink​(DoublyLinkedList.Entry<E> entry)
      Called to remove children from the list.

      • Methods inherited from class java.util.AbstractSequentialList

        add, addAll, get, iterator, remove, set

      • Methods inherited from class java.util.AbstractList

        add, clear, equals, hashCode, indexOf, lastIndexOf, listIterator, removeRange, subList

      • Methods inherited from class java.util.AbstractCollection

        addAll, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait

      • Methods inherited from interface java.util.Collection

        parallelStream, removeIf, stream, toArray

      • Methods inherited from interface java.util.Deque

        add, addAll, iterator

      • Methods inherited from interface java.lang.Iterable

        forEach

      • Methods inherited from interface java.util.List

        addAll, containsAll, isEmpty, removeAll, replaceAll, retainAll, sort, spliterator, toArray, toArray

    • Constructor Detail

      • DoublyLinkedList

        public DoublyLinkedList()
        Constructs an empty list.

      • DoublyLinkedList

        public DoublyLinkedList​(java.util.Collection<? extends E> source)
        Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
        Parameters:
        source - the collection whose elements are to be placed into this list
        Throws:
        java.lang.NullPointerException - if the specified collection is null

    • Method Detail

      • unlink

        protected boolean unlink​(DoublyLinkedList.Entry<E> entry)
        Called to remove children from the list.
        Parameters:
        entry - child entry.
        Returns:
        true if successful.

      • addFirst

        public void addFirst​(E e)
        Inserts the specified element at the beginning of this list.
        Specified by:
        addFirst in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        e - the element to add

      • addLast

        public void addLast​(E e)
        Appends the specified element to the end of this list.
        Specified by:
        addLast in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        e - the element to add

      • contains

        public boolean contains​(java.lang.Object o)
        Returns true if this list contains the specified element.
        Specified by:
        contains in interface java.util.Collection<E extends DoublyLinkedList.Entry<E>>
        Specified by:
        contains in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Specified by:
        contains in interface java.util.List<E extends DoublyLinkedList.Entry<E>>
        Overrides:
        contains in class java.util.AbstractCollection<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        o - element whose presence in this list is to be tested
        Returns:
        if this list contains the specified element

      • element

        public E element()
        Returns the first element in this list.
        Specified by:
        element in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Specified by:
        element in interface java.util.Queue<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the first element in this list
        Throws:
        java.util.NoSuchElementException - if this list is empty

      • getFirst

        public E getFirst()
        Returns the first element in this list.
        Specified by:
        getFirst in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the first element in this list
        Throws:
        java.util.NoSuchElementException - if this list is empty

      • getLast

        public E getLast()
        Returns the last element in this list.
        Specified by:
        getLast in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the last element in this list
        Throws:
        java.util.NoSuchElementException - if this list is empty

      • offer

        public boolean offer​(E e)
        Adds the specified element as the tail (last element) of this list.
        Specified by:
        offer in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Specified by:
        offer in interface java.util.Queue<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        e - the element to add
        Returns:
        true

      • offerFirst

        public boolean offerFirst​(E e)
        Inserts the specified element at the front of this list.
        Specified by:
        offerFirst in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        e - the element to insert
        Returns:
        true

      • offerLast

        public boolean offerLast​(E e)
        Inserts the specified element at the end of this list.
        Specified by:
        offerLast in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        e - the element to insert
        Returns:
        true

      • peekFirst

        public E peekFirst()
        Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
        Specified by:
        peekFirst in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the first element of this list, or null

      • peekLast

        public E peekLast()
        Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.
        Specified by:
        peekLast in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the last element of this list, or null

      • poll

        public E poll()
        Retrieves and removes the head (first element) of this list
        Specified by:
        poll in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Specified by:
        poll in interface java.util.Queue<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the head of this list, or null

      • pollFirst

        public E pollFirst()
        Retrieves and removes the first element of this list, or returns null if this list is empty.
        Specified by:
        pollFirst in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the first element of this list, or null

      • pollLast

        public E pollLast()
        Retrieves and removes the last element of this list, or returns null if this list is empty.
        Specified by:
        pollLast in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the last element of this list, or null

      • pop

        public E pop()
        Pops an element from the stack represented by this list.
        Specified by:
        pop in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the element at the front of this list
        Throws:
        java.util.NoSuchElementException - if this list is empty.
        See Also:
        LinkedList.pop()

      • push

        public void push​(E e)
        Pushes an element onto the stack represented by this list.
        Specified by:
        push in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        e - the element to push
        See Also:
        LinkedList.push(Object)

      • remove

        public E remove()
        Retrieves and removes the head (first element) of this list.
        Specified by:
        remove in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Specified by:
        remove in interface java.util.Queue<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the head of this list
        Throws:
        java.util.NoSuchElementException - if this list is empty
        See Also:
        LinkedList.remove()

      • removeFirst

        public E removeFirst()
        Removes and returns the first element from this list.
        Specified by:
        removeFirst in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the first element from this list
        Throws:
        java.util.NoSuchElementException - if this list is empty
        See Also:
        LinkedList.removeFirst()

      • remove

        public boolean remove​(java.lang.Object o)
        Removes the first occurrence of the specified element from this list, if it is present.
        Specified by:
        remove in interface java.util.Collection<E extends DoublyLinkedList.Entry<E>>
        Specified by:
        remove in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Specified by:
        remove in interface java.util.List<E extends DoublyLinkedList.Entry<E>>
        Overrides:
        remove in class java.util.AbstractCollection<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        o - element to be removed from this list,
        Returns:
        true if this list contained the specified element
        See Also:
        LinkedList.remove(Object)

      • removeFirstOccurrence

        public boolean removeFirstOccurrence​(java.lang.Object o)
        Removes the first occurrence of the specified element in this list.
        Specified by:
        removeFirstOccurrence in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        o - element to be removed from this list, if present
        Returns:
        true if the list contained the specified element
        See Also:
        LinkedList.removeFirstOccurrence(Object)

      • removeLastOccurrence

        public boolean removeLastOccurrence​(java.lang.Object o)
        Removes the last occurrence of the specified element in this list
        Specified by:
        removeLastOccurrence in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        o - element to be removed from this list, if present
        Returns:
        true if the list contained the specified element
        See Also:
        LinkedList.removeLastOccurrence(Object)

      • removeLast

        public E removeLast()
        Removes and returns the last element from this list.
        Specified by:
        removeLast in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        the last element from this list
        Throws:
        java.util.NoSuchElementException - if this list is empty
        See Also:
        LinkedList.removeLast()

      • listIterator

        @Nonnull
public java.util.ListIterator<E> listIterator​(int i)
        Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.
        Specified by:
        listIterator in interface java.util.List<E extends DoublyLinkedList.Entry<E>>
        Specified by:
        listIterator in class java.util.AbstractSequentialList<E extends DoublyLinkedList.Entry<E>>
        Parameters:
        i - index of the first element to be returned from the list-iterator (by a call to next)
        Returns:
        a ListIterator of the elements in this list
        Throws:
        java.lang.IndexOutOfBoundsException - if the index is out of range.
        See Also:
        List.listIterator(int)

      • descendingIterator

        @Nonnull
public java.util.Iterator<E> descendingIterator()
        Returns an iterator over the elements in reverse sequential order. The elements will be returned in order from last (tail) to first (head).
        Specified by:
        descendingIterator in interface java.util.Deque<E extends DoublyLinkedList.Entry<E>>
        Returns:
        an iterator over the elements in reverse sequence
        See Also:
        LinkedList.descendingIterator()