Fundamental linear Containers:
Array lists, or node lists and
Sequences hold elements at a rank or a position.
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
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; }
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.
return |
Method |
Time |
integer, n |
size() |
O(1) |
boolean |
isEmpty() |
O(1) |
E element |
get(int i) |
O(1) |
E |
set(int i, E element) |
O(1) |
void |
add(int i, E element) |
O(n) |
E element |
remove(int i) |
O(n) |
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.
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?
all O(1)