CS61B(7): ALists, Resizing, vs. SLists

This is the lecture note of CS61B - Lecture 7.

We have already seen how we can harness recursive class definition to build an expandable list, ie. the IntList, the SLList, and the DLList.

Now let us stop continuing it and try to use another basic data structure, array, to build list, which is called AList. You will find these two kinds of lists have differnet pros and cons.

AList: Array-based List

The data structure of DLList we have talked in the previous lecture is pretty beautiful. And it also has fast operations like addFirst, addLast etc. So why should we try to build AList?

Let's see a limitation of DLList.

1. Naive AList

🐹 Retrieval from any postion of an array is very fast.

// We only do back operations in the lecture. Project 1 will give you 
// a chance to implement front operations like addFirst, getFirst.

/* Invariants:
 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"
 size: The number of items in the list should be "size".
*/

public class AList {
    private int[] items;
    private int size;

    /** Creates an empty list. */
    public AList() {
        items = new int[100];
        size = 0;
    }

    /** Inserts X into the back of the list. */
    public void addLast(Item x) {
        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;
    }
} 

2. removeLast( ) method

The answer is we only need to change size.

/** Deletes item from back of the list and returns deleted item. */
public int removeLast() {
    int x = getLast();
    // items[size - 1] = null;   yeah but unnecessary
    size = size - 1;
    return x;
    }

3. Resizing Arrays

When the array gets too full, just make a new array!

🦉 Resizing process:

• int[ ] a = new int[newSize]
• System.arraycopy( )
• a[size] = targetNum
• items = a
• size += 1

Let's implement this process.

private void resize(int capacity) {
    int[] a = new int[capacity];
    System.arraycopy(items, 0, a, 0, size);
    items = a;
}


public void addLast(int x) {
    if (size == items.length) {
        resize(size + 1);
    }

    items[size] = x;
    size = size + 1;
}

Performance Problem 1

The big issue here is that how to set a proper capacity as the parameter of resize method?

Let's do an experiment to test the speed of resizing when using two different strategies.

• one is resize(size + 10)
• another is resize(2 * size)

Performance Problem 2

There is another performance problem. Suppose we have a very rare situation:

• Insert 1,000,000,000 items.
• Then remove 990,000,000 items.

Our data structure will handle this spike of events as well as it could, but afterwards there is a problem - a waste of space!

You will implement this during project 1.

Final Code

Finally, let's make AList generic, and we will get the following code.

public class AList<Item> {
    private Item[] items;
    private int size;

    /** Creates an empty list. */
    public AList() {
        items = (Item[]) new Object[100];   // Java Syntax: casting
        size = 0;
    }

    /** Resizes the underlying array to the target capacity. */
    private void resize(int capacity) {
        Item[] a = (Item[]) new Object[capacity];
        System.arraycopy(items, 0, a, 0, size);
        items = a;
    }

    /** Inserts X into the back of the list. */
    public void addLast(Item x) {
        if (size == items.length) {
            resize(size + 10);
            // resize(size * 2);
        }

        items[size] = x;
        size = size + 1;
    }

    /** Returns the item from the back of the list. */
    public Item getLast() {
        return items[size - 1];
    }

    /** Gets the ith item in the list (0 is the front). */
    public Item 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 Item removeLast() {
        Item x = getLast();
        items[size - 1] = null;
        size = size - 1;
        return x;
    }
} 

No Loitering

The last thing we should notice is loitering. Different from int[], when using Item[] we should null out the deleted items manually to save memory usage.