- DLLists made add/get/remove from First/Last in the list very fast
- However, not fast for arbitrary retrieval (for element in the middle, for example, takes
O(n) time), slow for links not near sentinel node - Lets try using an array structure instead of links

- 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

* 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;

}

}

- 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.