Package gnu.trove.list.linked

Class TLinkedList<T extends TLinkable<T>>

  • All Implemented Interfaces:
    java.io.Externalizable, java.io.Serializable, java.lang.Iterable<T>, java.util.Collection<T>, java.util.List<T>
    public class TLinkedList<T extends TLinkable<T>>
extends java.util.AbstractSequentialList<T>
implements java.io.Externalizable

    A LinkedList implementation which holds instances of type TLinkable. Using this implementation allows you to get java.util.LinkedList behavior (a doubly linked list, with Iterators that support insert and delete operations) without incurring the overhead of creating Node wrapper objects for every element in your list.
    The requirement to achieve this time/space gain is that the Objects stored in the List implement the TLinkable interface.
    The limitations are:

    • the same object cannot be put into more than one list at the same time.
    • the same object cannot be put into the same list more than once at the same time.
    • objects must only be removed from list they are in. That is, if you have an object A and lists l1 and l2, you must ensure that you invoke List.remove(A) on the correct list.
    • It is also forbidden to invoke List.remove() with an unaffiliated TLinkable (one that belongs to no list): this will destroy the list you invoke it on.
    See Also:
    TLinkable, Serialized Form

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      protected class  TLinkedList.IteratorImpl
      A ListIterator that supports additions and deletions.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected T _head
      the head of the list
      protected int _size
      the number of elements in the list
      protected T _tail
      the tail of the list

      • Fields inherited from class java.util.AbstractList

        modCount

    • Constructor Summary

      Constructors 
      Constructor Description
      TLinkedList()
      Creates a new TLinkedList instance.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(int index, T linkable)
      Inserts linkable at index index in the list.
      boolean add​(T linkable)
      Appends linkable to the end of the list.
      void addAfter​(T current, T newElement)
      Inserts newElement into the list immediately after current.
      void addBefore​(T current, T newElement)
      Inserts newElement into the list immediately before current.
      void addFirst​(T linkable)
      Inserts linkable at the head of the list.
      void addLast​(T linkable)
      Adds linkable to the end of the list.
      void clear()
      Empties the list.
      boolean contains​(java.lang.Object o)
      A linear search for o in the list.
      boolean forEachValue​(TObjectProcedure<T> procedure)
      Executes procedure for each entry in the list.
      T get​(int index)
      T getFirst()
      Returns the head of the list
      T getLast()
      Returns the tail of the list.
      T getNext​(T current)
      Return the node following the given node.
      T getPrevious​(T current)
      Return the node preceding the given node.
      protected void insert​(int index, T linkable)
      Implementation of index-based list insertions.
      java.util.ListIterator<T> listIterator​(int index)
      Returns an iterator positioned at index.
      void readExternal​(java.io.ObjectInput in)  
      boolean remove​(java.lang.Object o)
      Removes the specified element from the list.
      T removeFirst()
      Remove and return the first element in the list.
      T removeLast()
      Remove and return the last element in the list.
      int size()
      Returns the number of elements in the list.
      java.lang.Object[] toArray()
      Copies the list's contents into a native array.
      java.lang.Object[] toUnlinkedArray()
      Copies the list to a native array, destroying the next/previous links as the copy is made.
      T[] toUnlinkedArray​(T[] a)
      Returns a typed array of the objects in the set.
      void writeExternal​(java.io.ObjectOutput out)  

      • Methods inherited from class java.util.AbstractSequentialList

        addAll, iterator, remove, set

      • Methods inherited from class java.util.AbstractList

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

      • Methods inherited from class java.util.AbstractCollection

        addAll, containsAll, isEmpty, removeAll, retainAll, 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.lang.Iterable

        forEach

      • Methods inherited from interface java.util.List

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

    • Field Detail

      • _head

        protected T extends TLinkable<T> _head
        the head of the list

      • _tail

        protected T extends TLinkable<T> _tail
        the tail of the list

      • _size

        protected int _size
        the number of elements in the list

    • Constructor Detail

      • TLinkedList

        public TLinkedList()
        Creates a new TLinkedList instance.

    • Method Detail

      • listIterator

        public java.util.ListIterator<T> listIterator​(int index)
        Returns an iterator positioned at index. Assuming that the list has a value at that index, calling next() will retrieve and advance the iterator. Assuming that there is a value before index in the list, calling previous() will retrieve it (the value at index - 1) and move the iterator to that position. So, iterating from front to back starts at 0; iterating from back to front starts at size().
        Specified by:
        listIterator in interface java.util.List<T extends TLinkable<T>>
        Specified by:
        listIterator in class java.util.AbstractSequentialList<T extends TLinkable<T>>
        Parameters:
        index - an int value
        Returns:
        a ListIterator value

      • size

        public int size()
        Returns the number of elements in the list.
        Specified by:
        size in interface java.util.Collection<T extends TLinkable<T>>
        Specified by:
        size in interface java.util.List<T extends TLinkable<T>>
        Specified by:
        size in class java.util.AbstractCollection<T extends TLinkable<T>>
        Returns:
        an int value

      • add

        public void add​(int index,
                T linkable)
        Inserts linkable at index index in the list. All values > index are shifted over one position to accommodate the new addition.
        Specified by:
        add in interface java.util.List<T extends TLinkable<T>>
        Overrides:
        add in class java.util.AbstractSequentialList<T extends TLinkable<T>>
        Parameters:
        index - an int value
        linkable - an object of type TLinkable

      • add

        public boolean add​(T linkable)
        Appends linkable to the end of the list.
        Specified by:
        add in interface java.util.Collection<T extends TLinkable<T>>
        Specified by:
        add in interface java.util.List<T extends TLinkable<T>>
        Overrides:
        add in class java.util.AbstractList<T extends TLinkable<T>>
        Parameters:
        linkable - an object of type TLinkable
        Returns:
        always true

      • addFirst

        public void addFirst​(T linkable)
        Inserts linkable at the head of the list.
        Parameters:
        linkable - an object of type TLinkable

      • addLast

        public void addLast​(T linkable)
        Adds linkable to the end of the list.
        Parameters:
        linkable - an object of type TLinkable

      • clear

        public void clear()
        Empties the list.
        Specified by:
        clear in interface java.util.Collection<T extends TLinkable<T>>
        Specified by:
        clear in interface java.util.List<T extends TLinkable<T>>
        Overrides:
        clear in class java.util.AbstractList<T extends TLinkable<T>>

      • toArray

        public java.lang.Object[] toArray()
        Copies the list's contents into a native array. This will be a shallow copy: the Tlinkable instances in the Object[] array have links to one another: changing those will put this list into an unpredictable state. Holding a reference to one element in the list will prevent the others from being garbage collected unless you clear the next/previous links. Caveat programmer!
        Specified by:
        toArray in interface java.util.Collection<T extends TLinkable<T>>
        Specified by:
        toArray in interface java.util.List<T extends TLinkable<T>>
        Overrides:
        toArray in class java.util.AbstractCollection<T extends TLinkable<T>>
        Returns:
        an Object[] value

      • toUnlinkedArray

        public java.lang.Object[] toUnlinkedArray()
        Copies the list to a native array, destroying the next/previous links as the copy is made. This list will be emptied after the copy (as if clear() had been invoked). The Object[] array returned will contain TLinkables that do not hold references to one another and so are less likely to be the cause of memory leaks.
        Returns:
        an Object[] value

      • toUnlinkedArray

        public T[] toUnlinkedArray​(T[] a)
        Returns a typed array of the objects in the set.
        Parameters:
        a - an Object[] value
        Returns:
        an Object[] value

      • contains

        public boolean contains​(java.lang.Object o)
        A linear search for o in the list.
        Specified by:
        contains in interface java.util.Collection<T extends TLinkable<T>>
        Specified by:
        contains in interface java.util.List<T extends TLinkable<T>>
        Overrides:
        contains in class java.util.AbstractCollection<T extends TLinkable<T>>
        Parameters:
        o - an Object value
        Returns:
        a boolean value

      • get

        public T get​(int index)
        Specified by:
        get in interface java.util.List<T extends TLinkable<T>>
        Overrides:
        get in class java.util.AbstractSequentialList<T extends TLinkable<T>>

      • getFirst

        public T getFirst()
        Returns the head of the list
        Returns:
        an Object value

      • getLast

        public T getLast()
        Returns the tail of the list.
        Returns:
        an Object value

      • getNext

        public T getNext​(T current)
        Return the node following the given node. This method exists for two reasons:
        1. It's really not recommended that the methods implemented by TLinkable be called directly since they're used internally by this class.
        2. This solves problems arising from generics when working with the linked objects directly.
        NOTE: this should only be used with nodes contained in the list. The results are undefined with anything else.
        Parameters:
        current - The current node
        Returns:
        the node after the current node

      • getPrevious

        public T getPrevious​(T current)
        Return the node preceding the given node. This method exists for two reasons:
        1. It's really not recommended that the methods implemented by TLinkable be called directly since they're used internally by this class.
        2. This solves problems arising from generics when working with the linked objects directly.
        NOTE: this should only be used with nodes contained in the list. The results are undefined with anything else.
        Parameters:
        current - The current node
        Returns:
        the node after the current node

      • removeFirst

        public T removeFirst()
        Remove and return the first element in the list.
        Returns:
        an Object value

      • removeLast

        public T removeLast()
        Remove and return the last element in the list.
        Returns:
        an Object value

      • insert

        protected void insert​(int index,
                      T linkable)
        Implementation of index-based list insertions.
        Parameters:
        index - an int value
        linkable - an object of type TLinkable

      • remove

        public boolean remove​(java.lang.Object o)
        Removes the specified element from the list. Note that it is the caller's responsibility to ensure that the element does, in fact, belong to this list and not another instance of TLinkedList.
        Specified by:
        remove in interface java.util.Collection<T extends TLinkable<T>>
        Specified by:
        remove in interface java.util.List<T extends TLinkable<T>>
        Overrides:
        remove in class java.util.AbstractCollection<T extends TLinkable<T>>
        Parameters:
        o - a TLinkable element already inserted in this list.
        Returns:
        true if the element was a TLinkable and removed

      • addBefore

        public void addBefore​(T current,
                      T newElement)
        Inserts newElement into the list immediately before current. All elements to the right of and including current are shifted over.
        Parameters:
        current - a TLinkable value currently in the list.
        newElement - a TLinkable value to be added to the list.

      • addAfter

        public void addAfter​(T current,
                     T newElement)
        Inserts newElement into the list immediately after current. All elements to the left of and including current are shifted over.
        Parameters:
        current - a TLinkable value currently in the list.
        newElement - a TLinkable value to be added to the list.

      • forEachValue

        public boolean forEachValue​(TObjectProcedure<T> procedure)
        Executes procedure for each entry in the list.
        Parameters:
        procedure - a TObjectProcedure value
        Returns:
        false if the loop over the values terminated because the procedure returned false for some value.

      • writeExternal

        public void writeExternal​(java.io.ObjectOutput out)
                   throws java.io.IOException
        Specified by:
        writeExternal in interface java.io.Externalizable
        Throws:
        java.io.IOException

      • readExternal

        public void readExternal​(java.io.ObjectInput in)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException
        Specified by:
        readExternal in interface java.io.Externalizable
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException