Lecture 06 - 01/30

Arrays and Lists

Native Array Lists

/* Invariants: (things that must be true)
size: The number of items in the list should be size.
addLast: The next item we want to add, will go into position size
getLast: The item we want to return is in position size - 1
*/
public class AList<Item> {
private Item[] items;
private int size;
/** Creates an empty list. */
public AList() {
items = (Item[]) new Object[100];
size = 0;
}
/** Resizes the underlying array to the target capacity.
* Creates a new, larger array for the case where we are
* trying to add an element to the array but the array is
* already full.
* ex: trying to add the 100th element in box 101) */
private void resize(int capacity) {
Item[] a = (Item[]) new Object[capacity];
//arraycopy takes linear (O(n)) time to copy
System.arraycopy(items, 0, a, 0, size);
items = a;
}
/** Inserts X into the back of the list. */
public void addLast(Item x) {
/** This invokes the resizing method for when the array
* has been filled but we want to insert an element */
if (size == items.length) {
resize(size * 2); // See comment below
// resize(size + REFACTOR);
}
items[size] = x;
size = size + 1;
}
/** Returns the item from the back of the list. */
public int getLast() {
return items[size - 1];
}
/** Gets the ith item in the list (0 is the front). */
public int get(int i) {
return items[i];
}
/** Returns the number of items in the list. */
public int size() {
return size;
}
/** Deletes item from back of the list and
* returns deleted item. */
public int removeLast() {
int x = getLast();
items[size - 1] = null;
size = size - 1;
return x;
}
}

Resizing and Memory Efficiency: