Interview(3)Vector List

Interview(3)Vector List

Stack and Queue are special sequences.
Stack - insert, remove and access only apply to top item
Queue - remove and access only apply to top item, insert apply to bottom item
Deque - insert, remove and access only apply to top/bottom items.

Rank - Vector - Array List
getSize()
isEmpty()
getAtRank(r) - 0<=r < getSize(), return item whose rank is r
replaceAtRank(r, e) - replace the item whose rank is r, return the original item
insertAtRank(r, e) - insert the item at rank r, move the r+ items
removeAtRank(r) - remove the item at rank r, move the r+ items

public class VectorArray implements Vector{
    private final int N = 1024; //max size
    private int n = 0;    //count
    private Object[] A; //array

    public VectorArray(){
        A = new Object[N];
        n = 0;
    }

    public int getSize() { return n; }
   
    public boolean isEmpty() {  return (0 == n) ? true : false; }

    public Object getAtRank(int r) //O(1)
    throws ExceptionBoundaryViolation{
        if (0>r || r >= n ) { throw new ExceptionBoundaryViolation(“Error: boundary over”); }
        return A[r];
    }

    public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
        if ( 0> r || r >= n) { throw new ExceptionBoundaryViolation(“Error: “); }
        Object bak = A[r];
        A[r] = obj;
        return bak;
    }   

    public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
        if (0>r || r> n ) { throw new ExceptionBoundaryViolation(“Error”); }
        if (n >= N) { throw new ExceptionBoundaryViolation(“Error"); }
        for (int i = n; i> r; i—) { A[i] = A[i-1]; } //all the items behind r will move to r+1
        A[r] = obj; // insert the object to rank r
        n++; //update total size of the vector
        return obj;
    }

    public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
        if(0>r|| r>=n) { throw new ExceptionBoundaryViolation(“Error”); }
        Object bak = A[r];
        for (int i = r; i<n; i++) { A[i] = A[i+1]; } //
        n- - ; //update the size of the vector
        return bak;
    }
}

O(N);

Extend the Size of the Vector
if n>=N, insertAtRank()
#1 Create a new 2N new array B
#2 Copy all elements in A[] to B[]
#3 Replace A back to B

public class VectorExtArray implements Vector {
    private int N = 8; //initial capacity N
    private int n;
    private Object A[];

    public VectorExtArray() {
        A = new Object[N];
        n = 0;
    }

    public int getSize() { return n; }

    public boolean isEmpty() {
        return (0 == n) ? true : false;
    }

    public Object getAtRank(int r) throws ExceptionBoundaryViolation {
        if ( 0 > r || r >= n ) { throw new ExceptionBoundaryViolation(“Error”);  }
        return A[r];
    }

    public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
        if ( 0 > r || r >= n ) { throw new ExceptionBoundaryViolation(“Error”); }
        Object bak = A[r];
        A[r] = obj;
        return bak;
    }

    public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
        if ( 0 > r || r > n) { throw new ExceptionBoundaryViolation(“Error”); }
        if ( N <= n) {
            N * = 2;
            Object B[] = new Object[N]; // create a new array 2N
            for ( int i = 0; i<n; i++) {
                B[i] = A[i]; // copy all elements from A[] to B[]
            }
            A = B;
        }
       
        for(int i = n; i> r; i- - ) { A[i] = A[i -1]; }
        A[r] = obj;//insert
        n++;
        return obj;
    }

    public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
        if ( 0> r || r>=n) { throw new ExceptionBoundaryViolation(“Error”); }
        Object bak = A[r];
        for(int i = r; i< n-1; i++) { A[i] = A[i+1]; }
        n- - ;
        return bak;
    }
}

java.util.ArrayList and java.util.Vector Classes
Vector is similar with ArrayList, but it is synchronized.
ArrayList is a better choice if your program is thread-safe.

Vector and ArrayList require space as more elements are added. Vector each time doubles its array size, while ArrayList grow 50% of its size each time.

ArrayList
methods - first(), last(), getPrev(p); getNext(p); replace(p, e); insertFirst(e); insertLast(e); insertBefore(p, e); insertAfter(p, e);
                 remove(p);

method: insertBefore(p, e)
inputs: position p, item e
outputs: insert item e before position p
{
    create a new node v;
    v.setElement(e);   //store the item e in node v
    v.setPrev(p.getPrev);  //link the p’s prev
    (p.getPrev()).setNext(v); //link p’s prev
    p.setPrev(v); //p will be the next of v
    return ((Position)v); //
}

insertAfter(), insertFirst(), insertLast will all be similar

remove(p) Algorithm
method: remove(p)
inputs: Position p
outputs: remove the item e in position p, return e
{
    bak = p.element; // backup the current item
    (p.getNext()).setPrev(p.getPrev);  //link p’s next with p’s previous
    (p.getPrev()).setNext(p.getNext);
    p.setNext(null); //isolate item p
    p.setPrev(null); //isolate item p
    return bak;
}

Final List Implementation with Double End Node
public class ListDLNode implements List {
    protected int numElem; //size of items
    protected DLNode header, trailer; // first node and last node

    public ListDLNode(){
        numElem = 0; //empty
        header = new DLNode(null, null, null); //first
        trailer = new DLNode(null, header, null); //tailer
        header.setNext(trailer); //link header and trailer
    }

    protected DLNode checkPosition(Position p) throws ExceptionPositionInvalid {
        if (null == p){
            throw new ExceptionPositionInvalid(“Error, position is null”);
        }
        if(header == p){
            throw new ExceptionPositionInvalid(“Error, header is invalid position”);
        }
        if(trailer == p){
            throw new ExceptionPositionInvalid(“Error, trailer is invalid position”);
        }
        DLNode temp = (DLNode)p;
        return temp;
    }

    public int getSize() { return numElem; }
    public boolean isEmpty() { return (numElem == 0); }
    public Position first() throws ExceptionListEmpty {
        if(isEmpty()){
            throw new ExceptionListEmpty(“Error: empty list”);
        }
        return header.getNext();
    }

    public Position last() throws ExceptionListEmpty {
        if(isEmpty()){
            throw new ExceptionListEmpty(Error: empty list“");
        }
        return trailer.getPrev();
    }

    public Position getPrev(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation{
        DLNode v = checkPosition(p);
        DLNode prev = v.getPrev();
        if(prev == header){
            throw new ExceptionBoundaryViolation(“error: reach the header of list”);
        }
        return prev;
    }

    public Position getNext(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation {
        DLNode v = checkPosition(p);
        DLNode next = v.getNext();
        if(next == trailer){
            throw new ExceptionBoundaryViolation(“error: reach the trailer”);
        }
        return next;
    }

    public Position insertBefore(Position p, Object element) throws ExceptionPositionInvalid {
        DLNode v = checkPosition(p);
        numElem++;
        DLNode newNode = new DLNode(element, v.getPrev(), v);
        v.getPrev().setNext(newNode);
        v.setPrev(newNode);
        return newNode;
    }

    public Position insertAfter(Position p, Object element) throws ExceptionPositionInvalid {
        DLNode v = checkPosition(p);
        numElem++;
        DLNode newNode = new DLNode(element, v, v.getNext());
        v.getNext().setPrev(newNode);
        .vsetNext(newNode);
        return newNode;
    }

    public Position insertFirst(Object e){
        numElem++;
        DLNode newNode = new DLNode(e, header, header.getNext());
        header.getNext().setPrev(newNode);
        header.setNext(newNode);
        return newNode;
    }

    public Position insertLast(Object e) {
        numElem++;
        DLNode newNode = new DLNode(e, trailer.getPrev(), trailer);
        if(null == trailer.getPrev()) {
            System.out.println(“!!!prev is null, that is impossible!!!");
        }
        trailer.getPrev().setNext(newNode);
        trailer.setPrev(newNode);
        return newNode;
    }

    public Object remove(Position p) throws ExceptionPositionInvalid {
        DLNode v = checkPosition(p);
        numElem- - ;
        DLNode vPrev = v.getPrev();
        DLNode vNext = v.getNext();
        vPrev.setNext(vNext);
        vNext.setPrev(vPrev);
        Object vElem = v.getElem();   
        v.setNext(null);
        v.setPrev(null)
        return vElem;
    }

    public Object removeFirst() { return remove(header.getNext()); }

    public Object removeLast() { return remove(trailer.getPrev()); }

    public Object replace(Position p, Object obj) throws ExceptionPositionInvalid {
        DLNode v = checkPosition(p);
        Object oldElem = v.getElem();
        v.setElem(obj);
        return oldElem;
    }
}

References:
https://stackoverflow.com/questions/2986296/what-are-the-differences-between-arraylist-and-vector