CSC-220 Modified LinkList Textbook Code

MyArrayList.java

package chapter24;

@SuppressWarnings("unchecked")
public class MyArrayList<E> implements MyList<E> {
  public static final int INITIAL_CAPACITY = 16;
  private E[] data = (E[])new Object[INITIAL_CAPACITY];
  private int size = 0; // Number of elements in the list

  /** Create an empty list */
  public MyArrayList() {
  }

  /** Create a list from an array of objects */
  public MyArrayList(E[] objects) {
    for (int i = 0; i < objects.length; i++)
      add(objects[i]); // Warning: don’t use super(objects)! 
  }

  @Override /** Add a new element at the specified index */
  public void add(int index, E e) {   
    // Ensure the index is in the right range
    if (index < 0 || index > size)
      throw new IndexOutOfBoundsException
        ("Index: " + index + ", Size: " + size);
    
    ensureCapacity();

    // Move the elements to the right after the specified index
    for (int i = size - 1; i >= index; i--)
      data[i + 1] = data[i];

    // Insert new element to data[index]
    data[index] = e;

    // Increase size by 1
    size++;
  }

  /** Create a new larger array, double the current size + 1 */
  private void ensureCapacity() {
    if (size >= data.length) {
      E[] newData = (E[])(new Object[size * 2 + 1]);
      System.arraycopy(data, 0, newData, 0, size);
      data = newData;
    }
  }

  @Override /** Clear the list */
  public void clear() {
    data = (E[])new Object[INITIAL_CAPACITY];
    size = 0;
  }

  @Override /** Return true if this list contains the element */
  public boolean contains(Object e) {
    for (int i = 0; i < size; i++)
      if (e.equals(data[i])) return true;

    return false;
  }

  @Override /** Return the element at the specified index */
  public E get(int index) {
    checkIndex(index);
    return data[index];
  }

  private void checkIndex(int index) {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException
        ("Index: " + index + ", Size: " + size);
  }
  
  @Override /** Return the index of the first matching element 
   *  in this list. Return -1 if no match. */
  public int indexOf(Object e) {
    for (int i = 0; i < size; i++)
      if (e.equals(data[i])) return i;

    return -1;
  }

  @Override /** Return the index of the last matching element 
   *  in this list. Return -1 if no match. */
  public int lastIndexOf(E e) {
    for (int i = size - 1; i >= 0; i--)
      if (e.equals(data[i])) return i;

    return -1;
  }

  @Override /** Remove the element at the specified position 
   *  in this list. Shift any subsequent elements to the left.
   *  Return the element that was removed from the list. */
  public E remove(int index) {
    checkIndex(index);
    
    E e = data[index];

    // Shift data to the left
    for (int j = index; j < size - 1; j++)
      data[j] = data[j + 1];

    data[size - 1] = null; // This element is now null

    // Decrement size
    size--;

    return e;
  }

  @Override /** Replace the element at the specified position 
   *  in this list with the specified element. */
  public E set(int index, E e) {
    checkIndex(index);
    E old = data[index];
    data[index] = e;
    return old;
  }

  @Override
  public String toString() {
    StringBuilder result = new StringBuilder("[");

    for (int i = 0; i < size; i++) {
      result.append(data[i]);
      if (i < size - 1) result.append(", ");
    }

    return result.toString() + "]";
  }

  /** Trims the capacity to current size */
  public void trimToSize() {
    if (size != data.length) { 
      E[] newData = (E[])(new Object[size]);
      System.arraycopy(data, 0, newData, 0, size);
      data = newData;
    } // If size == capacity, no need to trim
  }

  @Override /** Override iterator() defined in Iterable */
  public java.util.Iterator<E> iterator() {
    return new ArrayListIterator();
  }
 
  private class ArrayListIterator 
      implements java.util.Iterator<E> {
    private int current = 0; // Current index 

    @Override
    public boolean hasNext() {
      return current < size;
    }

    @Override
    public E next() {
      return data[current++];
    }

    @Override // Remove the element returned by the last next()
    public void remove() {
    	if (current == 0) // next() has not been called yet
        throw new IllegalStateException(); 
      MyArrayList.this.remove(--current);
    }
  }
  
  @Override /** Return the number of elements in this list */
  public int size() {
    return size;
  }
}

MyLinkedList.java

package chapter24;

import java.util.Iterator;

public class MyLinkedList<E> implements MyList<E> {
	private static class Node<E> {
		E data;
		Node<E> next;

		public Node(E data) {
			this(data, null);
		}

		public Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
	}

	private Node<E> head = null;
	private Node<E> tail = null;
	private int size = 0; // Number of datas in the list

	/** Create an empty list */
	public MyLinkedList() {
	}

	/** Create a list from an array of objects */
	public MyLinkedList(E[] objects) {
		for (int i = 0; i < objects.length; i++)
			add(objects[i]);
	}

	public int getSize() {
		int count = 0;
		Node<E> ptr = head;
    	while (ptr != null) {
			count++;
			ptr = ptr.next;
		}
		return count;
	}
	
	/** Return the head data in the list */
	public E getFirst() {
		if (this.head != null)
			return head.data;
		return null;
	}

	/** Return the last data in the list */
	public E getLast() {
		if (this.tail != null)
			return tail.data;
		return null;
	}

	/** Add an data to the beginning of the list */
	public void addFirst(E e) {
		Node<E> newNode = new Node<>(e); // Create a new for data e
		if (head == null) {
			head = tail = newNode; // The new node is the only node in list
		}
		else {
			newNode.next = this.head; // link the new node with the head
			head = newNode; // head points to the new node
		}
		size++; // Increase size
	}

	/** Add an data to the end of the list */
	public void addLast(E e) {
		Node<E> newNode = new Node<>(e); // Create a new for data e
		if (tail == null) {
			head = tail = newNode; // The new node is the only node in list
		}
		else {
			tail.next = newNode; // Link the new with the last node
			tail = newNode; // tail now points to the last node
		}
		size++; // Increase size
	}

	 /**
				 * Add a new data at the specified index in this list. The index of the head
				 * data is 0
				 */
	@Override	
	public void add(int index, E e) {
		if (index < 0 || index > size)
			throw new RuntimeException("Bad Index " + index);
		
		if (index == 0) {
			this.addFirst(e);
		}
		else if (index == size) {
			this.addLast(e);
		}
		else {
			Node<E> newNode = new Node<>(e);
			
			Node<E> ptr = head;
			for (int i = 0; i < index - 1; i++) {
				ptr = ptr.next;
			}
			newNode.next = ptr.next;
			ptr.next = newNode;
			
			size++;
		}
	}
	
	/**
	 * Remove the head node and return the object that is contained in the removed
	 * node.
	 */
	public E removeFirst() {
		if (this.head == null) {
			return null;
		}
		E temp = head.data;
		head = head.next;
		size--;
		if (head == null) {
			tail = null;
		}
		return temp;
	}

	/**
	 * Remove the last node and return the object that is contained in the removed
	 * node.
	 */
	public E removeLast() {
		if (this.tail == null) {
			return null;
		}
		if (tail == head) {  //A list of just 1 node
			E temp = head.data;
			head = tail = null;
			size = 0;
			return temp;
		}
		Node<E> ptr = head;

		while (ptr.next != tail) {
			ptr = ptr.next;
		}

		E temp = tail.data;
		tail = ptr;
		tail.next = null;
		size--;
		return temp;

	}

	@Override /**
				 * Remove the data at the specified position in this list. Return the data
				 * that was removed from the list.
				 */
	public E remove(int index) {
		if (index < 0 || index > size) {
			throw new RuntimeException("Bad Index " + index);
		}
		
		if (index == 0) {
			return this.removeFirst();
		}
		if (index == size - 1) {
			return this.removeLast();
		}

		Node<E> ptr = head;

		for (int i = 0; i < index - 1; i++) {
			ptr = ptr.next;
		}

		Node<E> current = ptr.next;
		ptr.next = current.next;
		size--;
		return current.data;
	}

	@Override /** Override toString() to return datas in the list */
	public String toString() {
		StringBuilder result = new StringBuilder("[");
		
		Node<E> ptr = head;
		while (ptr != null) {
			result.append(ptr.data);
			ptr = ptr.next;
			if (ptr != null) {
				result.append(", "); // Separate two datas with a comma
			}
			else {
				result.append("]"); // Insert the closing ] in the string
			}
		}

		return result.toString();
	}

	@Override /** Clear the list */
	public void clear() {
		size = 0;
		head = tail = null;
	}

	@Override /** Return true if this list contains the data e */
	public boolean contains(Object e) {
		// Left as an exercise
		return true;
	}

	@Override /** Return the data at the specified index */
	public E get(int index) {
		// Left as an exercise
		return null;
	}

	@Override /**
				 * Return the index of the head matching data in this list. Return -1 if no
				 * match.
				 */
	public int indexOf(Object e) {
		// Left as an exercise
		return 0;
	}

	@Override /**
				 * Return the index of the last matching data in this list. Return -1 if no
				 * match.
				 */
	public int lastIndexOf(E e) {
		// Left as an exercise
		return 0;
	}

	@Override /**
				 * Replace the data at the specified position in this list with the specified
				 * data.
				 */
	public E set(int index, E e) {
		// Left as an exercise
		return null;
	}

	@Override /** Return the number of datas in this list */
	public int size() {
		return size;
	}

	@Override /** Override iterator() defined in Iterable */
	public Iterator<E> iterator() {
		return new LinkedListIterator();
	}

	private class LinkedListIterator implements Iterator<E> {
		private Node<E> ptr = head; // Current index

		@Override
		public boolean hasNext() {
			return (ptr != null);
		}

		@Override
		public E next() {
			E e = ptr.data;
			ptr = ptr.next;
			return e;
		}

		@Override
		public void remove() {
			
		}
	}
	
	
	public static void main(String args[]) {
		MyLinkedList<Integer> list = new MyLinkedList<>();
		list.add(3);
		list.add(6);
		list.add(2);
		list.add(313);
		
		//System.out.println(list.getSize());
		// list is iterable as ultimately it implements the Collections Interface which is iterable
		for (int x : list) {
			System.out.println(x);
		}
		
		System.out.println();
		
		Iterator<Integer> it = list.iterator();
		while (it.hasNext()) {
			int x = it.next();
			System.out.println(x);
		}
		
	}
	
}

MyLinkedListBookCode.java

package chapter24;

public class MyLinkedListBookCode<E> implements MyList<E> {
	private static class Node<E> {
		E element;
		Node<E> next;

		public Node(E element) {
			this(element, null);
		}

		public Node(E element, Node<E> next) {
			this.element = element;
			this.next = next;
		}
	}

	private Node<E> head, tail;
	private int size = 0; // Number of elements in the list

	/** Create an empty list */
	public MyLinkedListBookCode() {
	}

	/** Create a list from an array of objects */
	public MyLinkedListBookCode(E[] objects) {
		for (int i = 0; i < objects.length; i++)
			add(objects[i]);
	}

	/** Return the head element in the list */
	public E getFirst() {
		if (size == 0) {
			return null;
		}
		else {
			return head.element;
		}
	}

	/** Return the last element in the list */
	public E getLast() {
		if (size == 0) {
			return null;
		}
		else {
			return tail.element;
		}
	}

	/** Add an element to the beginning of the list */
	public void addFirst(E e) {
		Node<E> newNode = new Node<>(e); // Create a new node
		newNode.next = head; // link the new node with the head
		head = newNode; // head points to the new node
		size++; // Increase list size

		if (tail == null) // the new node is the only node in list
			tail = head;
	}

	/** Add an element to the end of the list */
	public void addLast(E e) {
		Node<E> newNode = new Node<>(e); // Create a new for element e

		if (tail == null) {
			head = tail = newNode; // The new node is the only node in list
		}
		else {
			tail.next = newNode; // Link the new with the last node
			tail = newNode; // tail now points to the last node
		}

		size++; // Increase size
	}

	@Override /**
				 * Add a new element at the specified index in this list. The index of the head
				 * element is 0
				 */
	public void add(int index, E e) {
		if (index == 0) {
			addFirst(e);
		}
		else if (index >= size) {
			addLast(e);
		}
		else {
			Node<E> current = head;
			for (int i = 1; i < index; i++) {
				current = current.next;
			}
			Node<E> temp = current.next;
			current.next = new Node<>(e);
			(current.next).next = temp;
			size++;
		}
	}

	/**
	 * Remove the head node and return the object that is contained in the removed
	 * node.
	 */
	public E removeFirst() {
		if (size == 0) {
			return null;
		}
		else {
			E temp = head.element;
			head = head.next;
			size--;
			if (head == null) {
				tail = null;
			}
			return temp;
		}
	}

	/**
	 * Remove the last node and return the object that is contained in the removed
	 * node.
	 */
	public E removeLast() {
		if (size == 0) {
			return null;
		}
		else if (size == 1) {
			E temp = head.element;
			head = tail = null;
			size = 0;
			return temp;
		}
		else {
			Node<E> current = head;

			for (int i = 0; i < size - 2; i++) {
				current = current.next;
			}

			E temp = tail.element;
			tail = current;
			tail.next = null;
			size--;
			return temp;
		}
	}

	@Override /**
				 * Remove the element at the specified position in this list. Return the element
				 * that was removed from the list.
				 */
	public E remove(int index) {
		if (index < 0 || index >= size) {
			return null;
		}
		else if (index == 0) {
			return removeFirst();
		}
		else if (index == size - 1) {
			return removeLast();
		}
		else {
			Node<E> previous = head;

			for (int i = 1; i < index; i++) {
				previous = previous.next;
			}

			Node<E> current = previous.next;
			previous.next = current.next;
			size--;
			return current.element;
		}
	}

	@Override /** Override toString() to return elements in the list */
	public String toString() {
		StringBuilder result = new StringBuilder("[");

		Node<E> current = head;
		for (int i = 0; i < size; i++) {
			result.append(current.element);
			current = current.next;
			if (current != null) {
				result.append(", "); // Separate two elements with a comma
			}
			else {
				result.append("]"); // Insert the closing ] in the string
			}
		}

		return result.toString();
	}

	@Override /** Clear the list */
	public void clear() {
		size = 0;
		head = tail = null;
	}

	@Override /** Return true if this list contains the element e */
	public boolean contains(Object e) {
		// Left as an exercise
		return true;
	}

	@Override /** Return the element at the specified index */
	public E get(int index) {
		// Left as an exercise
		return null;
	}

	@Override /**
				 * Return the index of the head matching element in this list. Return -1 if no
				 * match.
				 */
	public int indexOf(Object e) {
		// Left as an exercise
		return 0;
	}

	@Override /**
				 * Return the index of the last matching element in this list. Return -1 if no
				 * match.
				 */
	public int lastIndexOf(E e) {
		// Left as an exercise
		return 0;
	}

	@Override /**
				 * Replace the element at the specified position in this list with the specified
				 * element.
				 */
	public E set(int index, E e) {
		// Left as an exercise
		return null;
	}

	@Override /** Return the number of elements in this list */
	public int size() {
		return size;
	}

	@Override /** Override iterator() defined in Iterable */
	public java.util.Iterator<E> iterator() {
		return new LinkedListIterator();
	}

	private class LinkedListIterator implements java.util.Iterator<E> {
		private Node<E> current = head; // Current index

		@Override
		public boolean hasNext() {
			return (current != null);
		}

		@Override
		public E next() {
			E e = current.element;
			current = current.next;
			return e;
		}

		@Override
		public void remove() {
		}
	}

}

MyList.java

package chapter24;

import java.util.Collection;

public interface MyList<E> extends Collection<E> {
  /** Add a new element at the specified index in this list */
  public void add(int index, E e);

  /** Return the element from this list at the specified index */
  public E get(int index);

  /** Return the index of the first matching element in this list.
   *  Return -1 if no match. */
  public int indexOf(Object e);

  /** Return the index of the last matching element in this list
   *  Return -1 if no match. */
  public int lastIndexOf(E e);

  /** Remove the element at the specified position in this list
   *  Shift any subsequent elements to the left.
   *  Return the element that was removed from the list. */
  public E remove(int index);

  /** Replace the element at the specified position in this list
   *  with the specified element and returns the new set. */
  public E set(int index, E e);
  
  @Override /** Add a new element at the end of this list */
  public default boolean add(E e) {
    add(size(), e);
    return true;
  }

  @Override /** Return true if this list contains no elements */
  public default boolean isEmpty() {
    return size() == 0;
  }

  @Override /** Remove the first occurrence of the element e 
   *  from this list. Shift any subsequent elements to the left.
   *  Return true if the element is removed. */
  public default boolean remove(Object e) {
    if (indexOf(e) >= 0) {
      remove(indexOf(e));
      return true;
    }
    else
      return false;
  }

  @Override
  public default boolean containsAll(Collection<?> c) {
    // Left as an exercise
    return true;
  }

  @Override
  public default boolean addAll(Collection<? extends E> c) {
    // Left as an exercise
    return true;
  }

  @Override
  public default boolean removeAll(Collection<?> c) {
    // Left as an exercise
    return true;
  }

  @Override
  public default boolean retainAll(Collection<?> c) {
    // Left as an exercise
    return true;
  }

  @Override
  public default Object[] toArray() {
    // Left as an exercise
    return null;
  }

  @Override
  public default <T> T[] toArray(T[] array) {
    // Left as an exercise
    return null;
  }
}

TestMyArrayList.java

package chapter24;

public class TestMyArrayList {
  public static void main(String[] args) {
    // Create a list
    MyList<String> list = new MyArrayList<>();

    // Add elements to the list
    list.add("America"); // Add it to the list
    System.out.println("(1) " + list);

    list.add(0, "Canada"); // Add it to the beginning of the list
    System.out.println("(2) " + list);

    list.add("Russia"); // Add it to the end of the list
    System.out.println("(3) " + list);

    list.add("France"); // Add it to the end of the list
    System.out.println("(4) " + list);

    list.add(2, "Germany"); // Add it to the list at index 2
    System.out.println("(5) " + list);

    list.add(5, "Norway"); // Add it to the list at index 5
    System.out.println("(6) " + list);

    // Remove elements from the list
    list.remove("Canada"); // Same as list.remove(0) in this case
    System.out.println("(7) " + list);

    list.remove(2); // Remove the element at index 2
    System.out.println("(8) " + list);

    list.remove(list.size() - 1); // Remove the last element
    System.out.print("(9) " + list + "\n(10) ");

    for (String s: list)
      System.out.print(s.toUpperCase() + " ");
  }
}

TestMyLinkedList.java

package chapter24;

public class TestMyLinkedList {
  /** Main method */
  public static void main(String[] args) {
    // Create a list for strings
    MyLinkedListBookCode<String> list = new MyLinkedListBookCode<String>();

    // Add elements to the list
    list.add("America"); // Add it to the list
    System.out.println("(1) " + list);

    list.add(0, "Canada"); // Add it to the beginning of the list
    System.out.println("(2) " + list);

    list.add("Russia"); // Add it to the end of the list
    System.out.println("(3) " + list);

    list.addLast("France"); // Add it to the end of the list
    System.out.println("(4) " + list);

    list.add(2, "Germany"); // Add it to the list at index 2
    System.out.println("(5) " + list);

    list.add(5, "Norway"); // Add it to the list at index 5
    System.out.println("(6) " + list);

    list.add(0, "Poland"); // Same as list.addFirst("Poland")
    System.out.println("(7) " + list);

    // Remove elements from the list
    list.remove(0); // Same as list.remove("Australia") in this case
    System.out.println("(8) " + list);

    list.remove(2); // Remove the element at index 2
    System.out.println("(9) " + list);

    list.remove(list.size() - 1); // Remove the last element
    System.out.print("(10) " + list + "\n(11) ");
    
    for (String s: list)
      System.out.print(s.toUpperCase() + " ");
    
    list.clear();
    System.out.println("\nAfter clearing the list, the list size is " 
      + list.size());
  }
}

TestMyList.java

// Test Program to check ArrayList vs LinkList Performance

package chapter24;

public class TestMyList {
	/** Main method */
	public static void main(String[] args) {
		// Create a list for strings
		
		long start = System.nanoTime();
		MyList<String> list = new MyLinkedList<>();
		//MyList<String> list = new MyArrayList<String>();

		// Add elements to the list
		list.add("America"); // Add it to the list
		//System.out.println("(1) " + list);
		
		for (int i=0; i < 10000; i++) {
			list.add(0, "USAUSAUSA");
		}
		
		for (int i=0; i < 10000; i++) {
			list.remove(0);
		}

		list.add(0, "Canada"); // Add it to the beginning of the list
		//System.out.println("(2) " + list);

		list.add("Russia"); // Add it to the end of the list
		//System.out.println("(3) " + list);

		list.add("France"); // Add it to the end of the list
		//System.out.println("(4) " + list);

		list.add(2, "Germany"); // Add it to the list at index 2
		//System.out.println("(5) " + list);

		list.add(5, "Norway"); // Add it to the list at index 5
		//System.out.println("(6) " + list);

		list.add(0, "Poland"); // Same as list.addFirst("Poland")
		//System.out.println("(7) " + list);

		// Remove elements from the list
		//list.remove(0); // Same as list.remove("Australia") in this case
		//System.out.println("(8) " + list);

		//list.remove(2); // Remove the element at index 2
		//System.out.println("(9) " + list);

		//list.remove(list.size() - 1); // Remove the last element
		//System.out.print("(10) " + list + "\n(11) ");

		//for (String s : list)
		//	System.out.print(s.toUpperCase() + " ");

		long end = System.nanoTime();

		System.out.printf("%,d\n", end - start);
		//list.clear();
		//System.out.println("\nAfter clearing the list, the list size is "
		//		+ list.size());
		
		//**********************************************
		// Code to test Implementation of MyLinkedList.java 
		// unimplemented methods
		//**********************************************
		
		System.out.println(list);
		
		System.out.println(list.contains("Germany"));
		System.out.println(list.contains("Italy"));
		System.out.println(list.contains("Poland"));
		
		System.out.println(list.get(3));
		System.out.println(list.get(6));
		System.out.println(list.get(0));
		
		System.out.println(list.indexOf("Germany"));
		System.out.println(list.indexOf("Italy"));
		System.out.println(list.indexOf("Poland"));
		
		list.add("Germany");
		list.add("Italy");
		list.add("Poland");
		
		System.out.println(list.lastIndexOf("Germany"));
		System.out.println(list.lastIndexOf("Italy"));
		System.out.println(list.lastIndexOf("Poland"));
		
		list.set(0, "Tony");
		list.set(3, "Bill");
		list.set(5, "Bob");
		
		System.out.println(list);
		
	}
}