Package org.apache.juneau.commons.collections

Class SortedLinkedList<E>

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
org.apache.juneau.commons.collections.SortedLinkedList<E>
Type Parameters:
E - The element type.
All Implemented Interfaces:
Iterable<E>, Collection<E>, List<E>
public class SortedLinkedList<E> extends AbstractList<E>
A sorted list implementation backed by a LinkedList.

Unlike TreeSet, this class allows duplicate elements and maintains them in sorted order according to a specified Comparator or natural ordering. All modification operations (add, set, etc.) automatically maintain the sorted order.

This implementation uses a LinkedList internally, providing:

  • Efficient insertions (O(1) once insertion point is found)
  • No array shifting overhead
  • Linear search for finding insertion points (O(n))

For better random access performance, consider using SortedArrayList.

Features:
  • Maintains elements in sorted order automatically
  • Allows duplicate elements (unlike TreeSet)
  • Efficient insertion (O(1) once position is found)
  • No array shifting overhead
  • Supports custom comparators or natural ordering
Performance Characteristics:
  • add(E): O(n) - linear search to find position + O(1) insertion
  • get(int): O(n) - must traverse to index
  • contains(Object): O(n) - linear search
  • remove(Object): O(n) - linear search + O(1) removal
  • set(int, E): O(n) - may need to re-sort if element order changes
Usage:

// Natural ordering SortedLinkedList<String> list = new SortedLinkedList<>(); list.add("c"); list.add("a"); list.add("b"); // list contains: ["a", "b", "c"] // Custom comparator SortedLinkedList<String> list2 = new SortedLinkedList<>(Comparator.comparing(String::length)); list2.add("ccc"); list2.add("a"); list2.add("bb"); // list2 contains: ["a", "bb", "ccc"] (sorted by length)

Notes:
  • All elements must be mutually comparable (or comparable via the comparator)
  • Null elements are allowed only if the comparator supports them
  • The list maintains sorted order at all times - you cannot insert at a specific index
  • Calling set(int, E) may cause the element to move to maintain sorted order
  • This implementation is not thread-safe
  • Better suited for frequent insertions and removals, less suited for random access
See Also:

  • Constructor Details

    • SortedLinkedList

      public SortedLinkedList()
      Creates a new sorted list using natural ordering.

      Elements must implement Comparable.

      Throws:
      ClassCastException - if elements are not comparable.

    • SortedLinkedList

      public SortedLinkedList(Comparator<? super E> comparator)
      Creates a new sorted list using the specified comparator.
      Parameters:
      comparator - The comparator to use for sorting. Must not be null.

    • SortedLinkedList

      public SortedLinkedList(Collection<? extends E> c)
      Creates a new sorted list containing the elements of the specified collection.

      The elements are sorted according to natural ordering.

      Parameters:
      c - The collection whose elements are to be placed into this list.

    • SortedLinkedList

      public SortedLinkedList(Comparator<? super E> comparator, Collection<? extends E> c)
      Creates a new sorted list containing the elements of the specified collection.
      Parameters:
      comparator - The comparator to use for sorting. Must not be null.
      c - The collection whose elements are to be placed into this list.

  • Method Details

    • add

      public boolean add(E e)
      Adds the specified element to this list in sorted order.

      The element is inserted at the appropriate position to maintain sorted order. If there are equal elements, the new element is inserted after existing equal elements (maintains insertion order for equal elements).

      Specified by:
      add in interface Collection<E>
      Specified by:
      add in interface List<E>
      Overrides:
      add in class AbstractList<E>
      Parameters:
      e - The element to be added.
      Returns:
      true (as specified by Collection.add(Object)).

    • add

      public void add(int index, E element)
      Inserts the specified element at the specified position.

      Note: The index parameter is ignored - the element is always inserted in sorted order. This method exists to satisfy the List interface contract.

      Specified by:
      add in interface List<E>
      Overrides:
      add in class AbstractList<E>
      Parameters:
      index - Ignored - element is inserted in sorted order.
      element - The element to be inserted.

    • addAll

      public boolean addAll(Collection<? extends E> c)
      Adds all elements from the specified collection to this list in sorted order.
      Specified by:
      addAll in interface Collection<E>
      Specified by:
      addAll in interface List<E>
      Overrides:
      addAll in class AbstractCollection<E>
      Parameters:
      c - The collection containing elements to be added.
      Returns:
      true if this list changed as a result of the call.

    • addAll

      public boolean addAll(int index, Collection<? extends E> c)
      Adds all elements from the specified collection at the specified position.

      Note: The index parameter is ignored - elements are always inserted in sorted order.

      Specified by:
      addAll in interface List<E>
      Overrides:
      addAll in class AbstractList<E>
      Parameters:
      index - Ignored - elements are inserted in sorted order.
      c - The collection containing elements to be added.
      Returns:
      true if this list changed as a result of the call.

    • set

      public E set(int index, E element)
      Replaces the element at the specified position with the specified element.

      Important: After setting the element, the list is re-sorted to maintain sorted order. The element may move to a different position if its sort order changed.

      Specified by:
      set in interface List<E>
      Overrides:
      set in class AbstractList<E>
      Parameters:
      index - The index of the element to replace.
      element - The element to be stored at the specified position.
      Returns:
      The element previously at the specified position.
      Throws:
      IndexOutOfBoundsException - if the index is out of range.

    • get

      public E get(int index)
      Returns the element at the specified position.
      Specified by:
      get in interface List<E>
      Specified by:
      get in class AbstractList<E>
      Parameters:
      index - The index of the element to return.
      Returns:
      The element at the specified position.
      Throws:
      IndexOutOfBoundsException - if the index is out of range.

    • remove

      public E remove(int index)
      Removes the element at the specified position.
      Specified by:
      remove in interface List<E>
      Overrides:
      remove in class AbstractList<E>
      Parameters:
      index - The index of the element to be removed.
      Returns:
      The element that was removed.
      Throws:
      IndexOutOfBoundsException - if the index is out of range.

    • size

      public int size()
      Returns the number of elements in this list.
      Specified by:
      size in interface Collection<E>
      Specified by:
      size in interface List<E>
      Specified by:
      size in class AbstractCollection<E>
      Returns:
      The number of elements in this list.

    • comparator

      public Comparator<? super E> comparator()
      Returns the comparator used to order the elements in this list.
      Returns:
      The comparator, or null if natural ordering is used.

    • equals

      public boolean equals(Object obj)
      Compares the specified object with this list for equality.

      Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. Two elements e1 and e2 are considered equal if (e1==null ? e2==null : e1.equals(e2)).

      Specified by:
      equals in interface Collection<E>
      Specified by:
      equals in interface List<E>
      Overrides:
      equals in class AbstractList<E>
      Parameters:
      obj - The object to be compared for equality with this list.
      Returns:
      true if the specified object is equal to this list.

    • hashCode

      public int hashCode()
      Returns the hash code value for this list.

      The hash code of a list is defined to be the result of the following calculation:

      int hashCode = 1; for (E e : list) hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());

      Specified by:
      hashCode in interface Collection<E>
      Specified by:
      hashCode in interface List<E>
      Overrides:
      hashCode in class AbstractList<E>
      Returns:
      The hash code value for this list.

    • toString

      public String toString()
      Returns a string representation of this list.

      The string representation consists of a list of the list's elements in the order they are returned by its iterator, enclosed in square brackets ("[]"). Adjacent elements are separated by the characters ", " (comma and space). Elements are converted to strings as by String.valueOf(Object).

      Overrides:
      toString in class AbstractCollection<E>
      Returns:
      A string representation of this list.