Instantly share code, notes, and snippets.

@bytecodeman /MyArrayList.java Secret
Last active Nov 27, 2018

Embed
What would you like to do?
CSC-220 Modified LinkList Textbook Code
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;
}
}
package chapter24;
public class MyLinkedList<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 MyLinkedList() {
}
/** Create a list from an array of objects */
public MyLinkedList(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects[i]);
}
/** Return the head element in the list */
public E getFirst() {
if (head == null) {
return null;
}
return head.element;
}
/** Return the last element in the list */
public E getLast() {
if (tail == null) {
return null;
}
return tail.element;
}
/** Add an element to the beginning of the list */
public void addFirst(E e) {
Node<E> newNode = new Node<>(e);
newNode.next = head;
head = newNode;
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);
if (tail == null) {
head = tail = newNode;
}
else {
tail.next = newNode;
tail = newNode;
}
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> prev = null;
Node<E> current = head;
for (int i = 0; i < index; i++) {
prev = current;
current = current.next;
}
prev.next = new Node<>(e, current);
size++;
}
}
/**
* Remove the head node and return the object that is contained in the removed
* node.
*/
public E removeFirst() {
if (head == null) {
return null;
}
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 (tail == null) {
return null;
}
if (head == tail) {
E temp = head.element;
head = tail = null;
size = 0;
return temp;
}
Node<E> current = head;
while (current != null && current.next != tail) {
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;
}
if (index == 0) {
return removeFirst();
}
if (index == size - 1) {
return removeLast();
}
Node<E> prev = null;
Node<E> current = head;
for (int i = 0; i < index; i++) {
prev = current;
current = current.next;
}
prev.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;
while (current != null) {
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() {
}
}
}
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() {
}
}
}
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;
}
}
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() + " ");
}
}
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());
}
}
// 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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment