Package aud

Class DList<T>

java.lang.Object
aud.DList<T>
All Implemented Interfaces:
Graphvizable, Iterable<T>
public class DList<T> extends Object implements Iterable<T>, Graphvizable
Implementation of a doubly linked list.

The implementation is inspired by std::list of the C++ standard library.

DList does not define a bidirectional ListIterator. DList defines DList<T>.ForwardIterator (standard) iterator() and DList<T>.BackwardIterator reverse_iterator().

  • Iterators remain valid after insertion.
  • Iterators remain valid after removing entries, unless the current entry (that an iterator "points to") is removed.
  • There are methods to insert entries before and after an interator.

The utility class DList<T>.Backwards allows for using loops like 


 for (T item : dlist.backwards()) { ... }
Implementation note: Methods that access (or erase) entries generally assume that entries exist (!empty()). A java.lang.IndexOutOfBoundsException is thrown otherwise (see utility method check()).

  • Field Details

  • Constructor Details

    • DList

      public DList()
      create empty list

  • Method Details

    • size

      public int size()
      determine number of entries [O(n)]

    • empty

      public boolean empty()
      determine if list is empty [O(1)]

    • front

      public T front()
      retrieve first entry (must exist) [O(1)]

    • back

      public T back()
      retrieve last entry (must exist) [O(1)]

    • at

      public T at(int i)
      retrieve i-th entry [O(n)]
      Throws:
      IndexOutOfBoundsException

    • push_front

      public void push_front(T obj)
      insert entry at front of list [O(1)]

    • push_back

      public void push_back(T obj)
      append entry obj at end of list [O(1)]

    • insert

      public void insert(int i, T obj)
      insert new entry obj at position i [O(n)]

    • pop_front

      public void pop_front()
      erase first entry (must exist) [O(1)]

    • pop_back

      public void pop_back()
      erase last entry (must exist) [O(1)]

    • erase

      public void erase(int i)
      erase entry at position i [O(n)]

    • clear

      public void clear()
      Erase all entries. [O(1)]

    • iterator

      public DList<T>.ForwardIterator iterator()
      get forward iterator
      Specified by:
      iterator in interface Iterable<T>

    • reverse_iterator

      public DList<T>.BackwardIterator reverse_iterator()
      get backward iterator iterator

    • backwards

      public DList<T>.Backwards backwards()
      Get instance that provides a DList<T>.BackwardIterator. You cannot use reverse_iterator() directly in a for-each loop, because this loop assumes the iterator is provided via the Iterable interface, which is already implemented (in forward direction). The utility class DList<T>.Backwards implements Iterable and provides a DList<T>.BackwardIterator. Then in a for-each loop, instead of list just write list.backwards.

    • insert_after

      public void insert_after(DList<T>.ForwardIterator i, T object)
      insert entry after iterator position

    • insert_before

      public void insert_before(DList<T>.ForwardIterator i, T object)
      insert entry before iterator position

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • toDot

      public String toDot()
      Description copied from interface: Graphvizable
      Get dot representation.

      Specified by:
      toDot in interface Graphvizable