The implementation of several methods is (or can be) the same between our ArrayList and LinkedList. Write a common abstract superclass called AbstractList that implements the common behavior and is extended by both ArrayList and LinkedList. Factor out the common code from the two list classes into this abstract superclass so that no code duplication occurs between the two. Use iterators wherever possible in the abstract code to ensure that the implementation is efficient for both types of lists.
*********************
ArrayList.java
*********************
// Class ArrayList can be used to store a list of values of type E.
import java.util.*;
public class ArrayList implements List { private E[] elementData; private int size; public static final int DEFAULT_CAPACITY = 100;
@SuppressWarnings("unchecked") public ArrayList(int capacity) { if (capacity < 0) { throw new IllegalArgumentException("capacity: " + capacity); } elementData = (E[]) new Object[capacity]; size = 0; } public ArrayList() { this(DEFAULT_CAPACITY); } public int size() { return size; } public E get(int index) { checkIndex(index); return elementData[index]; } public String toString() { if (size == 0) { return "[]"; } else { String result = "[" + elementData[0]; for (int i = 1; i < size; i++) { result += ", " + elementData[i]; } result += "]"; return result; } } public int indexOf(E value) { for (int i = 0; i < size; i++) { if (elementData[i].equals(value)) { return i; } } return -1; } public boolean isEmpty() { return size == 0; } public boolean contains(E value) { return indexOf(value) >= 0; } public void add(E value) { ensureCapacity(size + 1); elementData[size] = value; size++; } public void add(int index, E value) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("index: " + index); } ensureCapacity(size + 1); for (int i = size; i >= index + 1; i--) { elementData[i] = elementData[i - 1]; } elementData[index] = value; size++; } public void remove(int index) { checkIndex(index); for (int i = index; i < size - 1; i++) { elementData[i] = elementData[i + 1]; } elementData[size - 1] = null; size--; } public void set(int index, E value) { checkIndex(index); elementData[index] = value; } public void clear() { for (int i = 0; i < size; i++) { elementData[i] = null; } size = 0; } public void addAll(List other) { for (E value: other) { add(value); } } public Iterator iterator() { return new ArrayListIterator(); } public void ensureCapacity(int capacity) { if (capacity > elementData.length) { int newCapacity = elementData.length * 2 + 1; if (capacity > newCapacity) { newCapacity = capacity; } elementData = Arrays.copyOf(elementData, newCapacity); } } private void checkIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("index: " + index); } } private class ArrayListIterator implements Iterator { private int position; private boolean removeOK; public ArrayListIterator() { position = 0; removeOK = false; } public boolean hasNext() { return position < size(); } public E next() { if (!hasNext()) { throw new NoSuchElementException(); } E result = elementData[position]; position++; removeOK = true; return result; } public void remove() { if (!removeOK) { throw new IllegalStateException(); } ArrayList.this.remove(position - 1); position--; removeOK = false; } } }
*****************
LinkedList.java
*****************
import java.util.*;
public class LinkedList implements List { private ListNode front; private ListNode back; private int size;
public LinkedList() { front = new ListNode(null); back = new ListNode(null); clear(); } public int size() { return size; } public E get(int index) { checkIndex(index); ListNode current = nodeAt(index); return current.data; } public String toString() { if (size == 0) { return "[]"; } else { String result = "[" + front.next.data; ListNode current = front.next.next; while (current != back) { result += ", " + current.data; current = current.next; } result += "]"; return result; } } public int indexOf(E value) { int index = 0; ListNode current = front.next; while (current != back) { if (current.data.equals(value)) { return index; } index++; current = current.next; } return -1; } public boolean isEmpty() { return size == 0; } public boolean contains(E value) { return indexOf(value) >= 0; } public void add(E value) { add(size, value); } public void add(int index, E value) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("index: " + index); } ListNode current = nodeAt(index - 1); ListNode newNode = new ListNode(value, current.next, current); current.next = newNode; newNode.next.prev = newNode; size++; } public void addAll(List other) { for (E value: other) { add(value); } } public void remove(int index) { checkIndex(index); ListNode current = nodeAt(index - 1); current.next = current.next.next; current.next.prev = current; size--; } public void set(int index, E value) { checkIndex(index); ListNode current = nodeAt(index); current.data = value; } public void clear() { front.next = back; back.prev = front; size = 0; } public Iterator iterator() { return new LinkedIterator(); } private ListNode nodeAt(int index) { ListNode current; if (index < size / 2) { current = front; for (int i = 0; i < index + 1; i++) { current = current.next; } } else { current = back; for (int i = size; i >= index + 1; i--) { current = current.prev; } } return current; } private void checkIndex(int index) { if (index < 0 || index >= size()) { throw new IndexOutOfBoundsException("index: " + index); } } private static class ListNode { public E data; public ListNode next; public ListNode prev; public ListNode(E data, ListNode next, ListNode prev) { this.data = data; this.next = next; this.prev = prev; } public ListNode(E data) { this(data, null, null); } } private class LinkedIterator implements Iterator { private ListNode current; private boolean removeOK; public LinkedIterator() { current = front.next; removeOK = false; } public boolean hasNext() { return current != back; } public E next() { if (!hasNext()) { throw new NoSuchElementException(); } E result = current.data; current = current.next; removeOK = true; return result; } public void remove() { if (!removeOK) { throw new IllegalStateException(); } ListNode prev2 = current.prev.prev; prev2.next = current; current.prev = prev2; size--; removeOK = false; } } }
