Class FastLinkedList<E>

  • Type Parameters:
    E - The element type of this linked list.
    All Implemented Interfaces:
    java.lang.Iterable<E>, java.util.Collection<E>
    Direct Known Subclasses:
    GraphAnalyzer.IndexedLists

    public class FastLinkedList<E>
    extends java.lang.Object
    implements java.util.Collection<E>
    A linked list that provides efficient add and removal functions.
    Since:
    Ptolemy II 8.0
    Version:
    $Id$
    Author:
    Thomas Huining Feng
    Pt.AcceptedRating:
    Red (tfeng)
    Pt.ProposedRating:
    Yellow (tfeng)
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      class  FastLinkedList.Entry
      An entry in this linked list that contains an element.
    • Constructor Summary

      Constructors 
      Constructor Description
      FastLinkedList()  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(E element)
      Add an element to the end of this linked list.
      boolean addAll​(java.util.Collection<? extends E> collection)
      Add all the elements of the given collection to the end of this linked list.
      void addEntryAfter​(FastLinkedList.Entry entry, FastLinkedList.Entry previousEntry)
      Add an entry after previousEntry, or add the entry to the head if previousEntry is null.
      void addEntryBefore​(FastLinkedList.Entry entry, FastLinkedList.Entry nextEntry)
      Add an entry before nextEntry, or add the entry to the tail if nextEntry is null.
      void addEntryToHead​(FastLinkedList.Entry entry)
      Add an entry to the head of this linked list.
      void addEntryToTail​(FastLinkedList.Entry entry)
      Add an entry to the tail of this linked list.
      void clear()
      Clear this linked list.
      boolean contains​(java.lang.Object element)
      Test whether this linked list has the given element in an entry.
      boolean containsAll​(java.util.Collection<?> collection)
      Test whether this linked list has all the elements of the given collection.
      FastLinkedList.Entry findEntry​(E element)
      Find an entry with the given element and return it.
      FastLinkedList.Entry getHead()
      Get the head entry.
      FastLinkedList.Entry getTail()
      Get the tail entry.
      boolean isEmpty()
      Test whether this collection is empty.
      java.util.Iterator<E> iterator()
      Not implemented.
      boolean remove​(java.lang.Object element)
      Remove the first entry that has the given element.
      boolean removeAll​(java.util.Collection<?> collection)
      Remove all the elements of the collection from this linked list.
      boolean removeAllAfter​(FastLinkedList.Entry entry)
      Remove all entries after the given entry.
      boolean removeAllBefore​(FastLinkedList.Entry entry)
      Remove all entries before the given entry.
      boolean retainAll​(java.util.Collection<?> collection)
      Retain all elements of the given collection, but remove entries whose elements are not in the collection.
      int size()
      Get the size of this linked list.
      java.lang.Object[] toArray()
      Return an array that contains all the elements in this linked list.
      <T> T[] toArray​(T[] array)
      Store all the elements in this linked list into the given array if its size is enough for the storage, or create a new array of the same type as the given array for the storage and return it.
      • Methods inherited from class java.lang.Object

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

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

        forEach
    • Constructor Detail

      • FastLinkedList

        public FastLinkedList()
    • Method Detail

      • add

        public boolean add​(E element)
        Add an element to the end of this linked list.
        Specified by:
        add in interface java.util.Collection<E>
        Parameters:
        element - The element to be added.
        Returns:
        Always true.
      • addAll

        public boolean addAll​(java.util.Collection<? extends E> collection)
        Add all the elements of the given collection to the end of this linked list.
        Specified by:
        addAll in interface java.util.Collection<E>
        Parameters:
        collection - The collection.
        Returns:
        Always true.
      • addEntryAfter

        public void addEntryAfter​(FastLinkedList.Entry entry,
                                  FastLinkedList.Entry previousEntry)
        Add an entry after previousEntry, or add the entry to the head if previousEntry is null.
        Parameters:
        entry - The entry to be added.
        previousEntry - The previous entry.
      • addEntryBefore

        public void addEntryBefore​(FastLinkedList.Entry entry,
                                   FastLinkedList.Entry nextEntry)
        Add an entry before nextEntry, or add the entry to the tail if nextEntry is null.
        Parameters:
        entry - The entry to be added.
        nextEntry - The next entry.
      • addEntryToHead

        public void addEntryToHead​(FastLinkedList.Entry entry)
        Add an entry to the head of this linked list.
        Parameters:
        entry - The entry to be added.
      • addEntryToTail

        public void addEntryToTail​(FastLinkedList.Entry entry)
        Add an entry to the tail of this linked list.
        Parameters:
        entry - The entry to be added.
      • clear

        public void clear()
        Clear this linked list.
        Specified by:
        clear in interface java.util.Collection<E>
      • contains

        public boolean contains​(java.lang.Object element)
        Test whether this linked list has the given element in an entry.
        Specified by:
        contains in interface java.util.Collection<E>
        Parameters:
        element - The element.
        Returns:
        true if the element is found.
      • containsAll

        public boolean containsAll​(java.util.Collection<?> collection)
        Test whether this linked list has all the elements of the given collection.
        Specified by:
        containsAll in interface java.util.Collection<E>
        Parameters:
        collection - The collection.
        Returns:
        true if all the elements are found.
      • findEntry

        public FastLinkedList.Entry findEntry​(E element)
        Find an entry with the given element and return it. Return null if not found.
        Parameters:
        element - The element.
        Returns:
        The entry.
      • isEmpty

        public boolean isEmpty()
        Test whether this collection is empty.
        Specified by:
        isEmpty in interface java.util.Collection<E>
        Returns:
        true if this collection is empty.
      • iterator

        public java.util.Iterator<E> iterator()
        Not implemented.
        Specified by:
        iterator in interface java.util.Collection<E>
        Specified by:
        iterator in interface java.lang.Iterable<E>
        Returns:
        The iterator to iterate elements in this linked list.
      • remove

        public boolean remove​(java.lang.Object element)
        Remove the first entry that has the given element.
        Specified by:
        remove in interface java.util.Collection<E>
        Parameters:
        element - The element.
        Returns:
        true if an entry is removed, or false if an entry cannot be found.
      • removeAll

        public boolean removeAll​(java.util.Collection<?> collection)
        Remove all the elements of the collection from this linked list.
        Specified by:
        removeAll in interface java.util.Collection<E>
        Parameters:
        collection - The collection.
        Returns:
        true if this linked list is altered, or false if no entry is removed.
      • removeAllAfter

        public boolean removeAllAfter​(FastLinkedList.Entry entry)
        Remove all entries after the given entry.
        Parameters:
        entry - The entry, which must be contained in this linked list.
        Returns:
        true if this linked list is altered, or false if no entry is removed.
      • removeAllBefore

        public boolean removeAllBefore​(FastLinkedList.Entry entry)
        Remove all entries before the given entry.
        Parameters:
        entry - The entry, which must be contained in this linked list.
        Returns:
        true if this linked list is altered, or false if no entry is removed.
      • retainAll

        public boolean retainAll​(java.util.Collection<?> collection)
        Retain all elements of the given collection, but remove entries whose elements are not in the collection.
        Specified by:
        retainAll in interface java.util.Collection<E>
        Parameters:
        collection - The collection.
        Returns:
        true if this linked list is altered, or false if no entry is removed.
      • size

        public int size()
        Get the size of this linked list.
        Specified by:
        size in interface java.util.Collection<E>
        Returns:
        The size.
      • toArray

        public java.lang.Object[] toArray()
        Return an array that contains all the elements in this linked list.
        Specified by:
        toArray in interface java.util.Collection<E>
        Returns:
        The array.
      • toArray

        public <T> T[] toArray​(T[] array)
        Store all the elements in this linked list into the given array if its size is enough for the storage, or create a new array of the same type as the given array for the storage and return it.
        Specified by:
        toArray in interface java.util.Collection<E>
        Type Parameters:
        T - The element type of the array.
        Parameters:
        array - The array.
        Returns:
        The given array, or a new array if the given array is not big enough.