0.0 Coding Revision

1. Array Implementations

List

package adt;
 
import java.io.Serializable;
 
/**
 * ArrayList.java A class that implements the ADT List using an array.
 *
 * @author Frank M. Carrano
 * @version 2.0
 * @param <T>
 */
 
public class ArrayList<T> implements ListInterface<T>, Serializable {
 
  private T[] array;
  private int numberOfEntries;
  private static final int DEFAULT_CAPACITY = 5;
 
  public ArrayList() {
    this(DEFAULT_CAPACITY);
  }
 
  public ArrayList(int initialCapacity) {
    numberOfEntries = 0;
    array = (T[]) new Object[initialCapacity];
  }
 
  @Override
  public boolean add(T newEntry) {
    array[numberOfEntries] = newEntry;
    numberOfEntries++;
    return true;
  }
 
  @Override
  public boolean add(int newPosition, T newEntry) {
    boolean isSuccessful = true;
 
    if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) {
        makeRoom(newPosition);
        array[newPosition - 1] = newEntry;
        numberOfEntries++;
    } else {
      isSuccessful = false;
    }
 
    return isSuccessful;
  }
 
  @Override
  public T remove(int givenPosition) {
    T result = null;
 
    if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
      result = array[givenPosition - 1];
 
      if (givenPosition < numberOfEntries) {
        removeGap(givenPosition);
      }
 
      numberOfEntries--;
    }
 
    return result;
  }
 
  @Override
  public void clear() {
    numberOfEntries = 0;
  }
 
  @Override
  public boolean replace(int givenPosition, T newEntry) {
    boolean isSuccessful = true;
 
    if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
      array[givenPosition - 1] = newEntry;
    } else {
      isSuccessful = false;
    }
 
    return isSuccessful;
  }
 
  @Override
  public T getEntry(int givenPosition) {
    T result = null;
 
    if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
      result = array[givenPosition - 1];
    }
 
    return result;
  }
 
  @Override
  public boolean contains(T anEntry) {
    boolean found = false;
    for (int index = 0; !found && (index < numberOfEntries); index++) {
      if (anEntry.equals(array[index])) {
        found = true;
      }
    }
    return found;
  }
 
  @Override
  public int getNumberOfEntries() {
    return numberOfEntries;
  }
 
  @Override
  public boolean isEmpty() {
    return numberOfEntries == 0;
  }
 
  @Override
  public boolean isFull() {
    return numberOfEntries == array.length;
  }
 
  @Override
  public String toString() {
    String outputStr = "";
    for (int index = 0; index < numberOfEntries; ++index) {
      outputStr += array[index] + "\n";
    }
 
    return outputStr;
  }
 
  /**
   * Task: Makes room for a new entry at newPosition. Precondition: 1 <=
   * newPosition <= numberOfEntries + 1; numberOfEntries is array's
 numberOfEntries before addition.
   */
  private void makeRoom(int newPosition) {
    int newIndex = newPosition - 1;
    int lastIndex = numberOfEntries - 1;
 
    // move each entry to next higher index, starting at end of
    // array and continuing until the entry at newIndex is moved
    for (int index = lastIndex; index >= newIndex; index--) {
      array[index + 1] = array[index];
    }
  }
 
  /**
   * Task: Shifts entries that are beyond the entry to be removed to the next
   * lower position. Precondition: array is not empty; 1 <= givenPosition <
 numberOfEntries; numberOfEntries is array's numberOfEntries before removal.
   */
  private void removeGap(int givenPosition) {
    // move each entry to next lower position starting at entry after the
    // one removed and continuing until end of array
    int removedIndex = givenPosition - 1;
    int lastIndex = numberOfEntries - 1;
 
    for (int index = removedIndex; index < lastIndex; index++) {
      array[index] = array[index + 1];
    }
  }
}

Stack

package adt;
 
/**
 * ArrayStack.java A class that implements the ADT Stack using an array.
 *
 * @author Frank M. Carrano
 * @version 2.0
 * @param <T>
 */
public class ArrayStack<T> implements StackInterface<T> {
 
  private T[] array;
  private int topIndex; // index of top entry
  private static final int DEFAULT_CAPACITY = 50;
 
  public ArrayStack() {
    this(DEFAULT_CAPACITY);
  }
 
  public ArrayStack(int initialCapacity) {
    array = (T[]) new Object[initialCapacity];
    topIndex = -1;
  }
 
  @Override
  public void push(T newEntry) {
    topIndex++;
 
    if (topIndex < array.length) {
      array[topIndex] = newEntry;
    }
  }
 
  @Override
  public T peek() {
    T top = null;
 
    if (!isEmpty()) {
      top = array[topIndex];
    }
 
    return top;
  } 
 
  @Override
  public T pop() {
    T top = null;
     System.out.println(top);
    if (!isEmpty()) {
      top = array[topIndex];
      array[topIndex] = null;
      topIndex--;
      
     
    } // end if
    
    return top;
  } 
 
  @Override
  public boolean isEmpty() {
    return topIndex < 0;
  } 
 
  public void clear() {
    topIndex = -1;
  } 
  
} 

Queue

package adt;
 
import java.util.Iterator;
 
/**
 * ArrayQueue.java A class that implements the ADT queue using a
 * linear array with a fixed front.
 * 
 * 
 * @author Frank M. Carrano
 * @version 2.0
 * @param <T>
 */
public class ArrayQueue<T> implements QueueInterface<T> {
 
  private T[] array;
  private final static int frontIndex = 0;
  private int backIndex;
  private static final int DEFAULT_CAPACITY = 50;
 
  public ArrayQueue() {
    this(DEFAULT_CAPACITY);
  }
 
  public ArrayQueue(int initialCapacity) {
    array = (T[]) new Object[initialCapacity];
    backIndex = -1;
  }
 
  public void enqueue(T newEntry) {
    if (!isArrayFull()) {
      backIndex++;
      array[backIndex] = newEntry;
    }
  }
 
  public T getFront() {
    T front = null;
    if (!isEmpty()) {
      front = array[frontIndex];
    }
    return front;
  }
 
  public T dequeue() {
    T front = null;
    if (!isEmpty()) {
      front = array[frontIndex];      // shift remaining array items forward one position      
      for (int i = frontIndex; i < backIndex; ++i) {
        array[i] = array[i + 1];
      }
      backIndex--;
    }
    return front;
  }
 
  public boolean isEmpty() {
    return frontIndex > backIndex;
  }
 
  public void clear() {
    if (!isEmpty()) { // deallocates only the used portion      
      for (int index = frontIndex; index <= backIndex; index++) {
        array[index] = null;
      }
      backIndex = -1;
    }
  }
 
  private boolean isArrayFull() {
    return backIndex == array.length - 1;
  }
  
  public Iterator<T> getIterator() {
    return new ArrayQueueIterator();
  }
  
  private class ArrayQueueIterator implements Iterator<T> {
    private int nextIndex;
 
    private ArrayQueueIterator() {
      nextIndex = 0;
    }
 
    @Override
    public boolean hasNext() {
      return nextIndex <= backIndex;
    }
 
    @Override
    public T next() {
      if (hasNext()) {
        T nextEntry = array[nextIndex];
        nextIndex++; // advance iterator
        return nextEntry;
      } else {
        return null;
      }
    }
  }
}

Circular Queue

package adt;
 
import java.util.Iterator;
 
/**
 * CircularArrayQueue.java  A class that implements the ADT Queue using a
 * circular array with one unused location.
 *
 * @author Frank M. Carrano
 * @version 2.0
 */
public class CircularArrayQueue<T> implements QueueInterface<T> {
 
  private T[] array; // circular array of array entries and one unused location
  private int frontIndex;
  private int backIndex;
  private static final int DEFAULT_CAPACITY = 5;
 
  public CircularArrayQueue() {
    this(DEFAULT_CAPACITY);
  }
 
  public CircularArrayQueue(int initialCapacity) {
    array = (T[]) new Object[initialCapacity + 1];
    frontIndex = 0;
    backIndex = initialCapacity;
  }
 
  public void enqueue(T newEntry) {
    if (!isArrayFull()) {
      backIndex = (backIndex + 1) % array.length;
      array[backIndex] = newEntry;
    }
  }
 
  public T getFront() {
    T front = null;
 
    if (!isEmpty()) {
      front = array[frontIndex];
    }
 
    return front;
  }
 
  public T dequeue() {
    T front = null;
 
    if (!isEmpty()) {
      front = array[frontIndex];
      array[frontIndex] = null;
      frontIndex = (frontIndex + 1) % array.length;
    }
 
    return front;
  }
 
  public boolean isEmpty() {
    return frontIndex == ((backIndex + 1) % array.length);
  }
 
  public void clear() {
    if (!isEmpty()) {
      for (int index = frontIndex; index != backIndex; index = (index + 1) % array.length) {
        array[index] = null;
      }
      array[backIndex] = null;
    }
 
    frontIndex = 0;
    backIndex = array.length - 1;
  }
 
  private boolean isArrayFull() {
    return frontIndex == ((backIndex + 2) % array.length);
  }
 
  @Override
  public Iterator<T> getIterator() {
    throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
  }
}

SortedList

package adt;
 
/**
 * SortedArrayList.java A class that implements the ADT Sorted List using an array.
 * Note: Some methods are not implemented yet and are left as practical exercises
 *
 * @author Frank M. Carrano
 * @version 2.0
 * @param <T>
 */
public class SortedArrayList<T extends Comparable<T>> implements SortedListInterface<T> {
 
  private T[] array;
  private int numberOfEntries;
  private static final int DEFAULT_CAPACITY = 25;
 
  public SortedArrayList() {
    this(DEFAULT_CAPACITY);
  }
 
  public SortedArrayList(int initialCapacity) {
    numberOfEntries = 0;
    array = (T[]) new Comparable[initialCapacity];
  }
 
  public boolean add(T newEntry) {
    int i = 0;
    while (i < numberOfEntries && newEntry.compareTo(array[i]) > 0) {
      i++;
    }
    makeRoom(i + 1);
    array[i] = newEntry;
    numberOfEntries++;
    return true;
  }
 
  public boolean remove(T anEntry) {
    throw new UnsupportedOperationException();
  }
 
  public void clear() {
    numberOfEntries = 0;
  }
 
  public boolean contains(T anEntry) {
    boolean found = false;
    for (int index = 0; !found && (index < numberOfEntries); index++) {
      if (anEntry.equals(array[index])) {
        found = true;
      }
    }
    return found;
  }
 
  public int getNumberOfEntries() {
    return numberOfEntries;
  }
 
  public boolean isEmpty() {
    return numberOfEntries == 0;
  }
 
  public String toString() {
    String outputStr = "";
    for (int index = 0; index < numberOfEntries; ++index) {
      outputStr += array[index] + "\n";
    }
 
    return outputStr;
  }
 
  private boolean isArrayFull() {
    return numberOfEntries == array.length;
  }
 
  private void doubleArray() {
    T[] oldList = array;
    int oldSize = oldList.length;
 
    array = (T[]) new Object[2 * oldSize];
 
    for (int index = 0; index < oldSize; index++) {
      array[index] = oldList[index];
    }
  }
 
  private void makeRoom(int newPosition) {
    int newIndex = newPosition - 1;
    int lastIndex = numberOfEntries - 1;
 
    for (int index = lastIndex; index >= newIndex; index--) {
      array[index + 1] = array[index];
    }
  }
 
  private void removeGap(int givenPosition) {
    int removedIndex = givenPosition - 1;
    int lastIndex = numberOfEntries - 1;
 
    
    for (int index = removedIndex; index < lastIndex; index++) {
      array[index] = array[index + 1];
    }
  }
 
}

---

2. Linked Implementations

List

package adt;
 
/**
 * LinkedList.java A class that implements the ADT List using a chain of nodes,
 * with the node implemented as an inner class.
 * 
 * @author Frank M. Carrano
 * @version 2.0
 */
public class LinkedList<T> implements ListInterface<T> {
 
  private Node firstNode; // reference to first node
  private int numberOfEntries;  	// number of entries in list
 
  public LinkedList() {
    clear();
  }
 
  @Override
  public final void clear() {
    firstNode = null;
    numberOfEntries = 0;
  }
 
  @Override
  public boolean add(T newEntry) {
    Node newNode = new Node(newEntry);	// create the new node
 
    if (isEmpty()) {
      firstNode = newNode;
    } else {                        // add to end of nonempty list
      Node currentNode = firstNode;	// traverse linked list with p pointing to the current node
      while (currentNode.next != null) { // while have not reached the last node
        currentNode = currentNode.next;
      }
      currentNode.next = newNode; // make last node reference new node
    }
 
    numberOfEntries++;
    return true;
  }
 
  @Override
  public boolean add(int newPosition, T newEntry) { // OutOfMemoryError possible
    boolean isSuccessful = true;
 
    if ((newPosition >= 1) && (newPosition <= numberOfEntries + 1)) {
      Node newNode = new Node(newEntry);
 
      if (isEmpty() || (newPosition == 1)) { // case 1: add to beginning of list
        newNode.next = firstNode;
        firstNode = newNode;
      } else {								// case 2: list is not empty and newPosition > 1
        Node nodeBefore = firstNode;
        for (int i = 1; i < newPosition - 1; ++i) {
          nodeBefore = nodeBefore.next;		// advance nodeBefore to its next node
        }
 
        newNode.next = nodeBefore.next;	// make new node point to current node at newPosition
        nodeBefore.next = newNode;		// make the node before point to the new node
      }
 
      numberOfEntries++;
    } else {
      isSuccessful = false;
    }
 
    return isSuccessful;
  }
 
  @Override
  public T remove(int givenPosition) {
    T result = null;                 // return value
 
    if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
      if (givenPosition == 1) {      // case 1: remove first entry
        result = firstNode.data;     // save entry to be removed
        firstNode = firstNode.next;
      } else {                         // case 2: givenPosition > 1
        Node nodeBefore = firstNode;
        for (int i = 1; i < givenPosition - 1; ++i) {
          nodeBefore = nodeBefore.next;		// advance nodeBefore to its next node
        }
        result = nodeBefore.next.data;  // save entry to be removed
        nodeBefore.next = nodeBefore.next.next;	// make node before point to node after the
      } 																// one to be deleted (to disconnect node from chain)
 
      numberOfEntries--;
    }
 
    return result; // return removed entry, or null if operation fails
  }
 
  @Override
  public boolean replace(int givenPosition, T newEntry) {
    boolean isSuccessful = true;
 
    if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
      Node currentNode = firstNode;
      for (int i = 0; i < givenPosition - 1; ++i) {
        currentNode = currentNode.next;		// advance currentNode to next node
      }
      currentNode.data = newEntry;	// currentNode is pointing to the node at givenPosition
    } else {
      isSuccessful = false;
    }
 
    return isSuccessful;
  }
 
  @Override
  public T getEntry(int givenPosition) {
    T result = null;
 
    if ((givenPosition >= 1) && (givenPosition <= numberOfEntries)) {
      Node currentNode = firstNode;
      for (int i = 0; i < givenPosition - 1; ++i) {
        currentNode = currentNode.next;		// advance currentNode to next node
      }
      result = currentNode.data;	// currentNode is pointing to the node at givenPosition
    }
 
    return result;
  }
 
  @Override
  public boolean contains(T anEntry) {
    boolean found = false;
    Node currentNode = firstNode;
 
    while (!found && (currentNode != null)) {
      if (anEntry.equals(currentNode.data)) {
        found = true;
      } else {
        currentNode = currentNode.next;
      }
    }
    return found;
  }
 
  @Override
  public int getNumberOfEntries() {
    return numberOfEntries;
  }
 
  @Override
  public boolean isEmpty() {
    boolean result;
 
    result = numberOfEntries == 0;
 
    return result;
  }
 
  @Override
  public boolean isFull() {
    return false;
  }
 
  @Override
  public String toString() {
    String outputStr = "";
    Node currentNode = firstNode;
    while (currentNode != null) {
      outputStr += currentNode.data + "\n";
      currentNode = currentNode.next;
    }
    return outputStr;
  }
 
  private class Node {
 
    private T data;
    private Node next;
 
    private Node(T data) {
      this.data = data;
      this.next = null;
    }
 
    private Node(T data, Node next) {
      this.data = data;
      this.next = next;
    }
  }
 
}

Queue

package adt;
 
import java.util.Iterator;
/**
 * LinkedQueue.java A class that implements the ADT Queue by using a chain of
 * nodes that has both head and tail references.
 * 
 * @author Frank M. Carrano
 * @version 2.0
 */
public class LinkedQueue<T> implements QueueInterface<T> {
 
  private Node firstNode; // references node at front of queue
  private Node lastNode;  // references node at back of queue
 
  public LinkedQueue() {
    firstNode = null;
    lastNode = null;
  } 
 
  public void enqueue(T newEntry) {
    Node newNode = new Node(newEntry, null);
 
    if (isEmpty()) {
      firstNode = newNode;
    } else {
      lastNode.next = newNode;
    }
 
    lastNode = newNode;
  } 
 
  public T getFront() {
    T front = null;
 
    if (!isEmpty()) {
      front = firstNode.data;
    }
 
    return front;
  } 
 
  public T dequeue() {
    T front = null;
 
    if (!isEmpty()) {
      front = firstNode.data;
      firstNode = firstNode.next;
 
      if (firstNode == null) {
        lastNode = null;
      }
    } 
 
    return front;
  } // end dequeue
 
  public boolean isEmpty() {
    return (firstNode == null) && (lastNode == null);
  }
 
  public void clear() {
    firstNode = null;
    lastNode = null;
  } 
  
  public Iterator<T> getIterator() {
    return new LinkedQueueIterator();
  }
 
  private class LinkedQueueIterator implements Iterator<T> {
 
    private Node currentNode;
 
    public LinkedQueueIterator() {
      currentNode = firstNode;
    }
 
    @Override
    public boolean hasNext() {
      return currentNode != null;
    }
 
    @Override
    public T next() {
      if (hasNext()) {
        T returnData = currentNode.data;
        currentNode = currentNode.next;
        return returnData;
      } else {
        return null;
      }
    }
  }
 
  private class Node {
 
    private T data; 
    private Node next; 
 
    private Node(T data) {
      this.data = data;
      this.next = null;
    } 
 
    private Node(T data, Node next) {
      this.data = data;
      this.next = next;
    } 
  } 
} 

SortedList

package adt;
 
import adt.SortedListInterface;
 
public class SortedLinkedList<T extends Comparable<T>> implements SortedListInterface<T> {
 
  private Node firstNode;
  private int numberOfEntries;
 
  public SortedLinkedList() {
    firstNode = null;
    numberOfEntries = 0;
  }
 
  public boolean add(T newEntry) {
    Node newNode = new Node(newEntry);
 
    Node nodeBefore = null;
    Node currentNode = firstNode;
    while (currentNode != null && newEntry.compareTo(currentNode.data) > 0) {
      nodeBefore = currentNode;
      currentNode = currentNode.next;
    }
 
    if (isEmpty() || (nodeBefore == null)) { // CASE 1: add at beginning
      newNode.next = firstNode;
      firstNode = newNode;
    } else {	// CASE 2: add in the middle or at the end, i.e. after nodeBefore
      newNode.next = currentNode;
      nodeBefore.next = newNode;
    }
    numberOfEntries++;
    return true;
  }
 
  public boolean remove(T anEntry) {
    throw new UnsupportedOperationException();	// Left as Practical exercise
  }
 
  public boolean contains(T anEntry) {
    boolean found = false;
    Node tempNode = firstNode;
 
    while (!found && (tempNode != null)) {
      if (anEntry.compareTo(tempNode.data) <= 0) {
        found = true;
      } else {
        tempNode = tempNode.next;
      }
    }
    if (tempNode != null && tempNode.data.equals(anEntry)) {
      return true;
    } else {
      return false;
    }
  }
 
  public final void clear() {
    firstNode = null;
    numberOfEntries = 0;
  }
 
  public int getNumberOfEntries() {
    return numberOfEntries;
  }
 
  public boolean isEmpty() {
    return (numberOfEntries == 0);
  }
 
  public String toString() {
    String outputStr = "";
    Node currentNode = firstNode;
    while (currentNode != null) {
      outputStr += currentNode.data + "\n";;
      currentNode = currentNode.next;
    }
    return outputStr;
  }
 
  private class Node {
 
    private T data;
    private Node next;
 
    private Node(T data) {
      this.data = data;
      next = null;
    }
 
    private Node(T data, Node next) {
      this.data = data;
      this.next = next;
    }
  }
}