Arrays and Lists

• However, not fast for arbitrary retrieval (for element in the middle, for example, takes O(n)$O(n)$ time), slow for links not near sentinel node

Native Array Lists

• Retrieval from any position of an array is very fast, independent of array size
• This is partly due to fact that memory boxes are all same size of bits
• We want to build array version of a list:
/* 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
* 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. */
/** 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:

• In AList, resizing requires recreating the entire list since size is fixed so it takes linear time, while in SLList it takes constant time since only adding another link
• Thus as we increase our number of inserts into both data structures, plotting total cumulative operations vs. number of inserts we see a linear relationship for SLList and an exponential one for AList
• We can fix this by instead of increasing size by some REFACTOR constant (such as 1) each time, multiply it by some REFACTOR constant (such as 2). This will drastically improve performance and reduce the impact of that exponential relationship

• This is how lists in Python work!
• Note:

• Let the usage ration R = size/items.length
• To be efficient, if R < 0.25 (very little amount of array actually filled), then half the array size.