Implementation of a singly linked list. More...

Inheritance diagram for aud.SList< T >:

Collaboration diagram for aud.SList< T >:

Classes
class	Iterator
	Forward iterator. More...

class	Node

Public Member Functions
	SList ()
	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(n)] 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(n)] 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(n)] More...

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

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

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

Iterator	iterator ()
	get forward iterator More...

String	toString ()

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

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

Protected Attributes
Node	head_ =null

Detailed Description

Implementation of a singly linked list.

The implementation is inspired by std::forward_list (formerly extension std::slist) of the C++ standard library.

Note that we implement also operations like back and push_back and pop_back, which are O(n) and inefficient for singly linked lists. They should not be implemented (or used) for a forward iterable container! (They are incldued only to contrast Vector and DList.)

SList defines a (forward) Iterator.

Iterators implement the java.util.Iterator interface. Note that Iterator#hasNext checks whether the current entry is valid, and Iterator#next returns the current entry whil advancing to the subsequent entry.

This is the standard semantic, but I still find the terms confusing.
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.

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 53 of file SList.java.

Constructor & Destructor Documentation

◆ SList()

aud.SList< T >.SList ( )

create empty list

Definition at line 75 of file SList.java.

75{}

Member Function Documentation

◆ at()

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

retrieve i-th entry [O(n)]

Definition at line 132 of file SList.java.

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

References aud.SList< T >.head_.

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

Here is the caller graph for this function:

◆ back()

T aud.SList< T >.back ( )

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

Definition at line 121 of file SList.java.

                  {
    check(head_);
    Node node=head_;
    while (node.next_!=null)
      node=node.next_;
    return node.data_;
  }

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

Here is the caller graph for this function:

◆ clear()

void aud.SList< T >.clear ( )

Erase all entries.

[O(1)]

Definition at line 236 of file SList.java.

236{ head_=null; }

References aud.SList< T >.head_.

◆ empty()

boolean aud.SList< T >.empty ( )

determine if list is empty [O(1)]

Definition at line 94 of file SList.java.

                         {
    return head_==null;
  }

References aud.SList< T >.head_.

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

Here is the caller graph for this function:

◆ erase()

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

erase entry at position i [O(n)]

Definition at line 218 of file SList.java.

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

References aud.SList< T >.head_.

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

Here is the caller graph for this function:

◆ front()

T aud.SList< T >.front ( )

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

Definition at line 113 of file SList.java.

                   {
    return check(head_).data_;
  }

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

Here is the caller graph for this function:

◆ insert()

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

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

Definition at line 179 of file SList.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.test.SListTest.testList().

Here is the caller graph for this function:

◆ insert_after()

void aud.SList< T >.insert_after	(	Iterator	i,
		T	object
	)

insert entry after iterator position

Definition at line 287 of file SList.java.

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

◆ iterator()

Iterator aud.SList< T >.iterator ( )

get forward iterator

Definition at line 295 of file SList.java.

                             {
    return new Iterator(head_);
  }

References aud.SList< T >.head_.

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

Here is the caller graph for this function:

◆ pop_back()

void aud.SList< T >.pop_back ( )

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

Definition at line 202 of file SList.java.

                         {
    Node node=check(head_), prv=null;
    while (node.next_!=null) {
      prv=node;
      node=node.next_;
    }
    if (prv==null)
      head_=null;
    else
      prv.next_=null;
  }

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

Here is the caller graph for this function:

◆ pop_front()

void aud.SList< T >.pop_front ( )

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

Definition at line 194 of file SList.java.

                          {
    head_=check(head_).next_;
  }

References aud.SList< T >.head_.

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

Here is the caller graph for this function:

◆ push_back()

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

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

Definition at line 151 of file SList.java.

                               {
    if (head_==null)        // special case!
      head_=new Node(obj,null);
    else {
      Node node=head_;
      while (node.next_!=null)
        node=node.next_;
      node.next_=new Node(obj,null);
    }
  }

References aud.SList< T >.head_.

Referenced by aud.test.SListTest.testIterators(), and aud.test.SListTest.testList().

Here is the caller graph for this function:

◆ push_front()

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

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

Definition at line 143 of file SList.java.

                                {
    head_=new Node(obj,head_);
  }

References aud.SList< T >.head_.

Referenced by aud.test.SListTest.testEntries(), aud.test.SListTest.testInvalid_at(), aud.test.SListTest.testInvalid_erase(), aud.test.SListTest.testList(), and aud.test.SListTest.testSize().

Here is the caller graph for this function:

◆ size()

int aud.SList< T >.size ( )

determine number of entries [O(n)]

Definition at line 81 of file SList.java.

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

References aud.SList< T >.head_.

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

Here is the caller graph for this function:

◆ toDot()

String aud.SList< T >.toDot ( )

Get dot representation.

Implements aud.util.Graphvizable.

Definition at line 319 of file SList.java.

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

References aud.SList< T >.head_.

◆ toString()

String aud.SList< T >.toString ( )

Definition at line 305 of file SList.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.SList< T >.head_.

Member Data Documentation

◆ head_

Node aud.SList< T >.head_ =null

protected

Definition at line 64 of file SList.java.

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

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

SList.java

Classes

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SList()

Member Function Documentation

◆ at()

◆ back()

◆ clear()

◆ empty()

◆ erase()

◆ front()

◆ insert()

◆ insert_after()

◆ iterator()

◆ pop_back()

◆ pop_front()

◆ push_back()

◆ push_front()

◆ size()

◆ toDot()

◆ toString()

Member Data Documentation

◆ head_