Array List and Node Lists 

Fundamental linear Containers:
Array lists, or node lists and Sequences hold elements at a rank or a position.

Array List

An extend able array, similar to an array but automatically resizes.

rank is position of element and is an integer, same as the index
n is the size of array list

Interface

The text book uses the IndexList interface

public interface IndexList<E> {
/** Returns the number of elements in this list. */
  public int size();
  /** Returns whether the list is empty. */
  public boolean isEmpty();
  /** Inserts an element e to be at index i, shifting all elements after this. */
  public void add(int i, E e) 
    throws IndexOutOfBoundsException;
  /** Returns the element at index i, without removing it. */
  public E get(int i) 
    throws IndexOutOfBoundsException;
  /** Removes and returns the element at index i, shifting the elements after this. */
  public E remove(int i)
    throws IndexOutOfBoundsException;
  /** Replaces the element at index i with e, returning the previous element at i. */
  public E set(int i, E e)
    throws IndexOutOfBoundsException;
}

Implementation:

Array Implementation.
Note the difference between: add() and remove().  add() requires making room and remove() requires filling in after removal.  Why are these methods O(n) time?

How would an extend able array and circular array be implemented?  What would be the advantages?
Circular arrays keep track of the front, f, and rear, r and use modulo arithmetic for indexing.  

IndexList Costs:

Node Lists

use nodes and link lists.

Position is an abstraction of “place”.  Not a big deal only a word. The book makes ADT with only one method:

public interface Position<E> {
  /** Return the element stored at this position. */
  E element();
}

Because the interface has only one method; they are nearly synonymous.  The author is trying to express that a position contains an element.  We can then implement Position any way we want.  For link list we will use a node.

PositionList Interface

public interface PositionList<E> {
      /** Returns the number of elements in this list. */
      public int size();
      /** Returns whether the list is empty. */
      public boolean isEmpty();
      /** Returns the first node in the list. */
      public Position<E> first();
      /** Returns the last node in the list. */
      public Position<E> last();
      /** Returns the node after a given node in the list. */
      public Position<E> next(Position<E> p)
      throws InvalidPositionException, BoundaryViolationException;
      /** Returns the node before a given node in the list. */
      public Position<E> prev(Position<E> p)
      throws InvalidPositionException, BoundaryViolationException;
      /** Inserts an element at the front of the list, returning new position. */
      public void addFirst(E e);
      /** Inserts and element at the back of the list, returning new position. */
      public void addLast(E e);
      /** Inserts an element after the given node in the list. */
      public void addAfter(Position<E> p, E e)
      throws InvalidPositionException;
      /** Inserts an element before the given node in the list. */
      public void addBefore(Position<E> p, E e)
      throws InvalidPositionException;
      /** Removes a node from the list, returning the element stored there. */
      public E remove(Position<E> p) throws InvalidPositionException;
      /** Replaces the element stored at the given node, returning old element. */
      public E set(Position<E> p, E e) throws InvalidPositionException;
}

So we need a InvalidPositionException, a run-time exception for invalid positions:

class InvalidPositionException extends RuntimeException {
       public InvalidPositionException(String err) {
         super(err);
       }
     }

DNode is the a doubly linked node that is used in the link list.  It implements Positions.  The most important part of  a class is the header line, fields and constructors:

public class DNode<E> implements Position<E> {
    private DNode<E> prev, next; // References to the nodes before and after
    private E element; // Element stored in this position
    /** Constructor */
    public DNode(DNode<E> newPrev, DNode<E> newNext, E elem) {
    prev = newPrev;
    next = newNext;
    element = elem;
    }
    // Method from interface Position
    public E element() throws InvalidPositionException {
    if ((prev == null) && (next == null))
    throw new InvalidPositionException("Position is not in a list!");
    return element;
    }

    // Accessor methods
    public DNode<E> getNext() { return next; }
    public DNode<E> getPrev() { return prev; }

    // Update methods
    public void setNext(DNode<E> newNext) { next = newNext; }
    public void setPrev(DNode<E> newPrev) { prev = newPrev; }
    public void setElement(E newElement) { element = newElement; }
 }

A DNode has two references (I will call them pointers)  to other DNodes, and an element

NodePositionList class Header line, Fields and Constructor:

public class NodePositionList<E> implements PositionList<E> {
       protected int numElts;                // Number of items in the list
       protected DNode header, trailer;      // Special sentinels

       // Constructor; O(1) time, Makes an empty list.
       public NodePostionList() {
           numElts = 0;
           header = new DNode(null, null, null);       // create header
           trailer = new DNode(header, null, null);    // create trailer
           header.setNext(trailer);    // make header and trailer point to each other
       }
... // other methods.  Study checkPosition
}

So NodePositionList class has fields for the number of nodes and header and trailer node. Header and trailer nodes have only null elements, nothing.  How can we later determine header and trailer nodes?

List cost

all  O(1)