Implementation of a doubly linked list. More...

Inheritance diagram for aud.DList< T >:

Collaboration diagram for aud.DList< T >:

Classes
class	BackwardIterator
	Backward iterator. More...

class	Backwards
	Utility class to obtain a `BackwardIterator`. More...

class	ForwardIterator
	Forward iterator. More...

class	Node

Public Member Functions
	DList ()
	create empty list More...

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

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

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

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

T	at (int i)
	retrieve i-th entry [O(n)] More...

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

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

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

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

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

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

void	clear ()
	Erase all entries. More...

ForwardIterator	iterator ()
	get forward iterator More...

BackwardIterator	reverse_iterator ()
	get backward iterator iterator More...

Backwards	backwards ()
	Get instance that provides a `BackwardIterator`. More...

void	insert_after (ForwardIterator i, T object)
	insert entry after iterator position More...

void	insert_before (ForwardIterator i, T object)
	insert entry before iterator position More...

String	toString ()

String	toDot ()
	Get dot representation. More...

String	toDot ()
	Get dot representation. More...

Protected Attributes
Node	head_ = null

Node	tail_ = null

Detailed Description

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 ForwardIterator (standard) iterator and 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 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()).

Definition at line 46 of file DList.java.

Constructor & Destructor Documentation

◆ DList()

aud.DList< T >.DList ( )

create empty list

Definition at line 73 of file DList.java.

73{}

Member Function Documentation

◆ at()

T aud.DList< T >.at ( int i )

retrieve i-th entry [O(n)]

Exceptions

IndexOutOfBoundsException

Definition at line 131 of file DList.java.

                     {
    Node node=head_;
    for (int j=0;node!=null && j<i;++j)
      node=node.next_;
    return check(node).data_;
  }

References aud.DList< T >.head_.

Referenced by aud.test.DListTest.testEntries(), aud.test.DListTest.testInvalid_at(), and aud.test.DListTest.testList().

Here is the caller graph for this function:

◆ back()

T aud.DList< T >.back ( )

retrieve last entry (must exist) [O(1)]

Definition at line 122 of file DList.java.

                  {
    return check(tail_).data_;
  }

Referenced by aud.test.DListTest.testInvalid_back(), and aud.test.DListTest.testList().

Here is the caller graph for this function:

◆ backwards()

Backwards aud.DList< T >.backwards ( )

Get instance that provides a 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 Backwards implements Iterable and provides a BackwardIterator. Then in a for-each loop, instead of list just write list.backwards.

Definition at line 346 of file DList.java.

                               {
    return new Backwards(this);
  }

Referenced by aud.test.DListTest.testIterators().

Here is the caller graph for this function:

◆ clear()

void aud.DList< T >.clear ( )

Erase all entries.

[O(1)]

Definition at line 245 of file DList.java.

245{ head_=tail_=null; }

References aud.DList< T >.head_, and aud.DList< T >.tail_.

◆ empty()

boolean aud.DList< T >.empty ( )

determine if list is empty [O(1)]

Definition at line 92 of file DList.java.

                         {
    assert((head_==null&&tail_==null)||
           (head_!=null && tail_!=null));
    return head_==null;
  }

References aud.DList< T >.head_, and aud.DList< T >.tail_.

Referenced by aud.test.DListTest.testCtor(), and aud.test.DListTest.testList().

Here is the caller graph for this function:

◆ erase()

void aud.DList< T >.erase ( int i )

erase entry at position i [O(n)]

Definition at line 224 of file DList.java.

                           {
    Node node=head_;
    for (int j=0;j<i && node!=null;++j)
      node=node.next_;
    check(node);
 
    if (node.prev_!=null)
      node.prev_.next_=node.next_;
    else
      head_=node.next_; // erased first!
 
    if (node.next_!=null)
      node.next_.prev_=node.prev_;
    else
      tail_=node.prev_; // erased last!
  }

References aud.DList< T >.head_.

Referenced by aud.test.DListTest.testInvalid_erase(), and aud.test.DListTest.testList().

Here is the caller graph for this function:

◆ front()

T aud.DList< T >.front ( )

retrieve first entry (must exist) [O(1)]

Definition at line 113 of file DList.java.

                   {
    return check(head_).data_;
  }

Referenced by aud.test.DListTest.testEntries(), aud.test.DListTest.testInvalid_front(), and aud.test.DListTest.testList().

Here is the caller graph for this function:

◆ insert()

void aud.DList< T >.insert	(	int	i,
		T	obj
	)

insert new entry obj at position i [O(n)]

Definition at line 185 of file DList.java.

                                  {
    if (i==0)
      insert_after((Node) null,obj);
    else {
      Node node=head_;
      for (int j=0;j<i-1 && node!=null;++j)
        node=node.next_;
      insert_after(check(node),obj);
    }
  }

Referenced by aud.util.SingleStepperDemo.main(), and aud.test.DListTest.testList().

Here is the caller graph for this function:

◆ insert_after()

void aud.DList< T >.insert_after	(	ForwardIterator	i,
		T	object
	)

insert entry after iterator position

Definition at line 351 of file DList.java.

                                                       {
    check(i.node_);
    insert_after(i.node_,object);
  }

◆ insert_before()

void aud.DList< T >.insert_before	(	ForwardIterator	i,
		T	object
	)

insert entry before iterator position

Definition at line 356 of file DList.java.

                                                        {
    check(i.node_);
    insert_after(i.node_.prev_,object);
  }

Referenced by aud.test.DListTest.testIterators().

Here is the caller graph for this function:

◆ iterator()

ForwardIterator aud.DList< T >.iterator ( )

get forward iterator

Definition at line 303 of file DList.java.

                                    {
    return new ForwardIterator(head_);
  }

References aud.DList< T >.head_.

Referenced by aud.test.DListTest.testIterators().

Here is the caller graph for this function:

◆ pop_back()

void aud.DList< T >.pop_back ( )

erase last entry (must exist) [O(1)]

Definition at line 212 of file DList.java.

                         {
    tail_=check(tail_).prev_;
    if (tail_==null)
      head_=null;
    else
      tail_.next_=null;
  }

References aud.DList< T >.tail_.

Referenced by aud.test.DListTest.testInvalid_pop_back(), and aud.test.DListTest.testList().

Here is the caller graph for this function:

◆ pop_front()

void aud.DList< T >.pop_front ( )

erase first entry (must exist) [O(1)]

Definition at line 200 of file DList.java.

                          {
    head_=check(head_).next_;
    if (head_==null)
      tail_=null;
    else
      head_.prev_=null;
  }

References aud.DList< T >.head_.

Referenced by aud.test.DListTest.testInvalid_pop_front(), and aud.test.DListTest.testList().

Here is the caller graph for this function:

◆ push_back()

void aud.DList< T >.push_back ( T obj )

append entry obj at end of list [O(1)]

Definition at line 154 of file DList.java.

                               {
    tail_=new Node(obj,tail_,null);
    if (tail_.prev_!=null)
      tail_.prev_.next_=tail_;
    if (head_==null)
      head_=tail_;
  }

References aud.DList< T >.head_, and aud.DList< T >.tail_.

Referenced by aud.util.SingleStepperDemo.main(), aud.test.DListTest.testIterators(), and aud.test.DListTest.testList().

Here is the caller graph for this function:

◆ push_front()

void aud.DList< T >.push_front ( T obj )

insert entry at front of list [O(1)]

Definition at line 142 of file DList.java.

                                {
    head_=new Node(obj,null,head_);
    if (head_.next_!=null)
      head_.next_.prev_=head_;
    if (tail_==null)
      tail_=head_;
  }

References aud.DList< T >.head_, and aud.DList< T >.tail_.

Referenced by aud.util.SingleStepperDemo.main(), aud.test.DListTest.testEntries(), aud.test.DListTest.testInvalid_at(), aud.test.DListTest.testInvalid_erase(), aud.test.DListTest.testList(), and aud.test.DListTest.testSize().

Here is the caller graph for this function:

◆ reverse_iterator()

BackwardIterator aud.DList< T >.reverse_iterator ( )

get backward iterator iterator

Definition at line 307 of file DList.java.

                                             {
    return new BackwardIterator(tail_);
  }

References aud.DList< T >.tail_.

Referenced by aud.test.DListTest.testIterators().

Here is the caller graph for this function:

◆ size()

int aud.DList< T >.size ( )

determine number of entries [O(n)]

Definition at line 79 of file DList.java.

                    {
    int n=0;
    Node node=head_;
    while (node!=null) {
      node=node.next_;
      ++n;
    }
    return n;
  }

References aud.DList< T >.head_.

Referenced by aud.test.DListTest.testEntries(), aud.test.DListTest.testList(), and aud.test.DListTest.testSize().

Here is the caller graph for this function:

◆ toDot()

String aud.DList< T >.toDot ( )

Get dot representation.

Implements aud.util.Graphvizable.

Definition at line 380 of file DList.java.

                        {
    String rv="digraph DList {\n\t\n\tnode [shape=box];\n\t";
    Node node=head_;
 
    while (node!=null) {
      String prv=node.prev_!=null ? node.prev_.data_.toString() : "null";
      String nxt=node.next_!=null ? node.next_.data_.toString() : "null";
 
      rv+="\""+node.data_.toString()+"\" -> \""+prv
        +"\" [color=blue,label=prev];\n\t"
        +"\""+node.data_.toString()+"\" -> \""+nxt
        +"\" [color=blue,label=next];\n\t";
 
      node=node.next_;
    }
    rv+="\n}\n";
    return rv;
  }

References aud.DList< T >.head_.

◆ toString()

String aud.DList< T >.toString ( )

Definition at line 366 of file DList.java.

                           {
    String rv="[";
    Node node=head_;
    while (node!=null) {
      rv+=node.data_.toString();
      if (node.next_!=null)
        rv+=",";
      node=node.next_;
    }
    rv+="]";
    return rv;
  }

References aud.DList< T >.head_.

Member Data Documentation

◆ head_

Node aud.DList< T >.head_ = null

protected

Definition at line 59 of file DList.java.

Referenced by aud.DList< T >.at(), aud.DList< T >.clear(), aud.DList< T >.empty(), aud.DList< T >.erase(), aud.DList< T >.iterator(), aud.DList< T >.pop_front(), aud.DList< T >.push_back(), aud.DList< T >.push_front(), aud.DList< T >.size(), aud.DList< T >.toDot(), and aud.DList< T >.toString().

◆ tail_

Node aud.DList< T >.tail_ = null

protected

Definition at line 60 of file DList.java.

Referenced by aud.DList< T >.clear(), aud.DList< T >.empty(), aud.DList< T >.pop_back(), aud.DList< T >.push_back(), aud.DList< T >.push_front(), and aud.DList< T >.reverse_iterator().

The documentation for this class was generated from the following file:

DList.java

Classes

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ DList()

Member Function Documentation

◆ at()

◆ back()

◆ backwards()

◆ clear()

◆ empty()

◆ erase()

◆ front()

◆ insert()

◆ insert_after()

◆ insert_before()

◆ iterator()

◆ pop_back()

◆ pop_front()

◆ push_back()

◆ push_front()

◆ reverse_iterator()

◆ size()

◆ toDot()

◆ toString()

Member Data Documentation

◆ head_

◆ tail_