Class AbstractLinkedList

  • All Implemented Interfaces:
    java.lang.Iterable, java.util.Collection, java.util.List
    Direct Known Subclasses:
    CursorableLinkedList, NodeCachingLinkedList

    public abstract class AbstractLinkedList
    extends java.lang.Object
    implements java.util.List
    An abstract implementation of a linked list which provides numerous points for subclasses to override.

    Overridable methods are provided to change the storage node and to change how nodes are added to and removed. Hopefully, all you need for unusual subclasses is here.

    Since:
    Commons Collections 3.0
    Version:
    $Revision: 646777 $ $Date: 2008-04-10 14:33:15 +0200 (Thu, 10 Apr 2008) $
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected AbstractLinkedList()
      Constructor that does nothing intended for deserialization.
      protected AbstractLinkedList​(java.util.Collection coll)
      Constructs a list copying data from the specified collection.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(int index, java.lang.Object value)  
      boolean add​(java.lang.Object value)  
      boolean addAll​(int index, java.util.Collection coll)  
      boolean addAll​(java.util.Collection coll)  
      boolean addFirst​(java.lang.Object o)  
      boolean addLast​(java.lang.Object o)  
      protected void addNode​(AbstractLinkedList.Node nodeToInsert, AbstractLinkedList.Node insertBeforeNode)
      Inserts a new node into the list.
      protected void addNodeAfter​(AbstractLinkedList.Node node, java.lang.Object value)
      Creates a new node with the specified object as its value and inserts it after node.
      protected void addNodeBefore​(AbstractLinkedList.Node node, java.lang.Object value)
      Creates a new node with the specified object as its value and inserts it before node.
      void clear()  
      boolean contains​(java.lang.Object value)  
      boolean containsAll​(java.util.Collection coll)  
      protected AbstractLinkedList.Node createHeaderNode()
      Creates a new node with previous, next and element all set to null.
      protected AbstractLinkedList.Node createNode​(java.lang.Object value)
      Creates a new node with the specified properties.
      protected java.util.Iterator createSubListIterator​(AbstractLinkedList.LinkedSubList subList)
      Creates an iterator for the sublist.
      protected java.util.ListIterator createSubListListIterator​(AbstractLinkedList.LinkedSubList subList, int fromIndex)
      Creates a list iterator for the sublist.
      protected void doReadObject​(java.io.ObjectInputStream inputStream)
      Deserializes the data held in this object to the stream specified.
      protected void doWriteObject​(java.io.ObjectOutputStream outputStream)
      Serializes the data held in this object to the stream specified.
      boolean equals​(java.lang.Object obj)  
      java.lang.Object get​(int index)  
      java.lang.Object getFirst()  
      java.lang.Object getLast()  
      protected AbstractLinkedList.Node getNode​(int index, boolean endMarkerAllowed)
      Gets the node at a particular index.
      int hashCode()  
      int indexOf​(java.lang.Object value)  
      protected void init()
      The equivalent of a default constructor, broken out so it can be called by any constructor and by readObject.
      boolean isEmpty()  
      protected boolean isEqualValue​(java.lang.Object value1, java.lang.Object value2)
      Compares two values for equals.
      java.util.Iterator iterator()  
      int lastIndexOf​(java.lang.Object value)  
      java.util.ListIterator listIterator()  
      java.util.ListIterator listIterator​(int fromIndex)  
      java.lang.Object remove​(int index)  
      boolean remove​(java.lang.Object value)  
      boolean removeAll​(java.util.Collection coll)  
      protected void removeAllNodes()
      Removes all nodes by resetting the circular list marker.
      java.lang.Object removeFirst()  
      java.lang.Object removeLast()  
      protected void removeNode​(AbstractLinkedList.Node node)
      Removes the specified node from the list.
      boolean retainAll​(java.util.Collection coll)  
      java.lang.Object set​(int index, java.lang.Object value)  
      int size()  
      java.util.List subList​(int fromIndexInclusive, int toIndexExclusive)
      Gets a sublist of the main list.
      java.lang.Object[] toArray()  
      java.lang.Object[] toArray​(java.lang.Object[] array)  
      java.lang.String toString()  
      protected void updateNode​(AbstractLinkedList.Node node, java.lang.Object value)
      Updates the node with a new value.
      • 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

        replaceAll, sort, spliterator
    • Field Detail

      • header

        protected transient AbstractLinkedList.Node header
        A AbstractLinkedList.Node which indicates the start and end of the list and does not hold a value. The value of next is the first item in the list. The value of of previous is the last item in the list.
      • size

        protected transient int size
        The size of the list
      • modCount

        protected transient int modCount
        Modification count for iterators
    • Constructor Detail

      • AbstractLinkedList

        protected AbstractLinkedList()
        Constructor that does nothing intended for deserialization.

        If this constructor is used by a serializable subclass then the init() method must be called.

      • AbstractLinkedList

        protected AbstractLinkedList​(java.util.Collection coll)
        Constructs a list copying data from the specified collection.
        Parameters:
        coll - the collection to copy
    • Method Detail

      • init

        protected void init()
        The equivalent of a default constructor, broken out so it can be called by any constructor and by readObject. Subclasses which override this method should make sure they call super, so the list is initialised properly.
      • size

        public int size()
        Specified by:
        size in interface java.util.Collection
        Specified by:
        size in interface java.util.List
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Collection
        Specified by:
        isEmpty in interface java.util.List
      • get

        public java.lang.Object get​(int index)
        Specified by:
        get in interface java.util.List
      • iterator

        public java.util.Iterator iterator()
        Specified by:
        iterator in interface java.util.Collection
        Specified by:
        iterator in interface java.lang.Iterable
        Specified by:
        iterator in interface java.util.List
      • listIterator

        public java.util.ListIterator listIterator()
        Specified by:
        listIterator in interface java.util.List
      • listIterator

        public java.util.ListIterator listIterator​(int fromIndex)
        Specified by:
        listIterator in interface java.util.List
      • indexOf

        public int indexOf​(java.lang.Object value)
        Specified by:
        indexOf in interface java.util.List
      • lastIndexOf

        public int lastIndexOf​(java.lang.Object value)
        Specified by:
        lastIndexOf in interface java.util.List
      • contains

        public boolean contains​(java.lang.Object value)
        Specified by:
        contains in interface java.util.Collection
        Specified by:
        contains in interface java.util.List
      • containsAll

        public boolean containsAll​(java.util.Collection coll)
        Specified by:
        containsAll in interface java.util.Collection
        Specified by:
        containsAll in interface java.util.List
      • toArray

        public java.lang.Object[] toArray()
        Specified by:
        toArray in interface java.util.Collection
        Specified by:
        toArray in interface java.util.List
      • toArray

        public java.lang.Object[] toArray​(java.lang.Object[] array)
        Specified by:
        toArray in interface java.util.Collection
        Specified by:
        toArray in interface java.util.List
      • subList

        public java.util.List subList​(int fromIndexInclusive,
                                      int toIndexExclusive)
        Gets a sublist of the main list.
        Specified by:
        subList in interface java.util.List
        Parameters:
        fromIndexInclusive - the index to start from
        toIndexExclusive - the index to end at
        Returns:
        the new sublist
      • add

        public boolean add​(java.lang.Object value)
        Specified by:
        add in interface java.util.Collection
        Specified by:
        add in interface java.util.List
      • add

        public void add​(int index,
                        java.lang.Object value)
        Specified by:
        add in interface java.util.List
      • addAll

        public boolean addAll​(java.util.Collection coll)
        Specified by:
        addAll in interface java.util.Collection
        Specified by:
        addAll in interface java.util.List
      • addAll

        public boolean addAll​(int index,
                              java.util.Collection coll)
        Specified by:
        addAll in interface java.util.List
      • remove

        public java.lang.Object remove​(int index)
        Specified by:
        remove in interface java.util.List
      • remove

        public boolean remove​(java.lang.Object value)
        Specified by:
        remove in interface java.util.Collection
        Specified by:
        remove in interface java.util.List
      • removeAll

        public boolean removeAll​(java.util.Collection coll)
        Specified by:
        removeAll in interface java.util.Collection
        Specified by:
        removeAll in interface java.util.List
      • retainAll

        public boolean retainAll​(java.util.Collection coll)
        Specified by:
        retainAll in interface java.util.Collection
        Specified by:
        retainAll in interface java.util.List
      • set

        public java.lang.Object set​(int index,
                                    java.lang.Object value)
        Specified by:
        set in interface java.util.List
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Collection
        Specified by:
        clear in interface java.util.List
      • getFirst

        public java.lang.Object getFirst()
      • getLast

        public java.lang.Object getLast()
      • addFirst

        public boolean addFirst​(java.lang.Object o)
      • addLast

        public boolean addLast​(java.lang.Object o)
      • removeFirst

        public java.lang.Object removeFirst()
      • removeLast

        public java.lang.Object removeLast()
      • equals

        public boolean equals​(java.lang.Object obj)
        Specified by:
        equals in interface java.util.Collection
        Specified by:
        equals in interface java.util.List
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface java.util.Collection
        Specified by:
        hashCode in interface java.util.List
        Overrides:
        hashCode in class java.lang.Object
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • isEqualValue

        protected boolean isEqualValue​(java.lang.Object value1,
                                       java.lang.Object value2)
        Compares two values for equals. This implementation uses the equals method. Subclasses can override this to match differently.
        Parameters:
        value1 - the first value to compare, may be null
        value2 - the second value to compare, may be null
        Returns:
        true if equal
      • updateNode

        protected void updateNode​(AbstractLinkedList.Node node,
                                  java.lang.Object value)
        Updates the node with a new value. This implementation sets the value on the node. Subclasses can override this to record the change.
        Parameters:
        node - node to update
        value - new value of the node
      • createHeaderNode

        protected AbstractLinkedList.Node createHeaderNode()
        Creates a new node with previous, next and element all set to null. This implementation creates a new empty Node. Subclasses can override this to create a different class.
        Returns:
        newly created node
      • createNode

        protected AbstractLinkedList.Node createNode​(java.lang.Object value)
        Creates a new node with the specified properties. This implementation creates a new Node with data. Subclasses can override this to create a different class.
        Parameters:
        value - value of the new node
      • addNode

        protected void addNode​(AbstractLinkedList.Node nodeToInsert,
                               AbstractLinkedList.Node insertBeforeNode)
        Inserts a new node into the list.
        Parameters:
        nodeToInsert - new node to insert
        insertBeforeNode - node to insert before
        Throws:
        java.lang.NullPointerException - if either node is null
      • removeNode

        protected void removeNode​(AbstractLinkedList.Node node)
        Removes the specified node from the list.
        Parameters:
        node - the node to remove
        Throws:
        java.lang.NullPointerException - if node is null
      • removeAllNodes

        protected void removeAllNodes()
        Removes all nodes by resetting the circular list marker.
      • getNode

        protected AbstractLinkedList.Node getNode​(int index,
                                                  boolean endMarkerAllowed)
                                           throws java.lang.IndexOutOfBoundsException
        Gets the node at a particular index.
        Parameters:
        index - the index, starting from 0
        endMarkerAllowed - whether or not the end marker can be returned if startIndex is set to the list's size
        Throws:
        java.lang.IndexOutOfBoundsException - if the index is less than 0; equal to the size of the list and endMakerAllowed is false; or greater than the size of the list
      • createSubListIterator

        protected java.util.Iterator createSubListIterator​(AbstractLinkedList.LinkedSubList subList)
        Creates an iterator for the sublist.
        Parameters:
        subList - the sublist to get an iterator for
      • createSubListListIterator

        protected java.util.ListIterator createSubListListIterator​(AbstractLinkedList.LinkedSubList subList,
                                                                   int fromIndex)
        Creates a list iterator for the sublist.
        Parameters:
        subList - the sublist to get an iterator for
        fromIndex - the index to start from, relative to the sublist
      • doWriteObject

        protected void doWriteObject​(java.io.ObjectOutputStream outputStream)
                              throws java.io.IOException
        Serializes the data held in this object to the stream specified.

        The first serializable subclass must call this method from writeObject.

        Throws:
        java.io.IOException
      • doReadObject

        protected void doReadObject​(java.io.ObjectInputStream inputStream)
                             throws java.io.IOException,
                                    java.lang.ClassNotFoundException
        Deserializes the data held in this object to the stream specified.

        The first serializable subclass must call this method from readObject.

        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException