We've been using the List ADT in our homework assignments, and so far you've seen two different implementations of a List: the FixedList and the recursive LinkedList. To review, here are the following methods that must be defined for a List

• get(i): return the data at the i-th place in the list.<
• set(i,e): return the i-th piece of data, and also replace it with e.
• add(i,e): insert e in the list at location i. All data with locations greater than i are shifted to a location one greater.
• remove(i): remove and return the data at i. Shift all data at higher indices down.
• size() return the number of elements in the list.

This is all an ADT is! Any way of making this work, no matter how stupid or slow, still means that it is an it is a list. However, implementing it with different data structures gives us different run times, and thus the choice of implementation can have a big impact on the performance of your program. Perhaps you should use an array back end, like FixedList or ArrayList, or a linked node structure like LinkedList. Presumably, you could implement all four of those methods with a combination of strategies.

Another important thing to consider with ADT's is that they do not specify what kind (or type) of element they can store. Looking at the definition above and in the code samples provided in the first few homework, the type of e is undefined, just referred to as an element. This generalization of the ADT is called generics in Java, and templates in C++. And, most Object Oriented programming languages have a notion of generalizing data structures.

As an example of generics, consider defining a LinkedList implementation of Strings, which may have the following Java decelerations:

public class LinkedList implements List{

    private class Node{
        String data;
        Node next;
    }

    Node head = null;

    void set(int i, String e){/*---*/}
    String get(int i){/*---*/}
    void add(int i, String e){/*---*/}      
    String remove(int i){/*---*/}
    int size(){/*---*/}
}

This implementation is fine and well whenever we want to store String's, but what if we want to store int's or double's or Object's or whatever we want? We have to copy paste the code and create a whole new implementation at each of the types. That, is simply, a nightmare for a programmer.

What we want is to write one implementation of the data structure that can store all the things we want. One way to do this is to leverage the subclassing in Java and recognize that Object is the base type, and, thus, everything is a subclass of Object. Maybe we could define our LinkedList implementation like so:

public class LinkedList implements List{

    private class Node{
        Object data; //<---
        Node next;
    }

    Node head = null;

    //rest of methods to follow ...
    void set(int i, Object e){/*---*/}
    Object get(int i){/*---*/}
    void add(int i, Object e){/*---*/}      
    Object remove(int i){/*---*/}
    int size(){/*---*/}
}

Now when we use this implementation, we have to cast the elements going in and going out of the data structure as the implementation expects and returns Objects, not the specific type we are using. For example:

List l = new LinkedList();

l.add(0, (Object) "Go"); //Cast to object
l.add(1, (Object) "Navy");

//Cast to String
System.out.println("" + ((String) l.get(0)) + ((String) l.get(1)));

While this is better, you should feel dissatisfied. Foremost, all that casting is a runtime check, meaning that if you make a mistake it won't be noticed until you actually run the program. That may be too late to actually fix the mistake. What we would prefer is for Java to be able to recognize what type the list is suppose to store and ensure that all our use cases match that type.

That is exactly what generics do. You define the type for the class in greater-then and less-then brackets, and this acts as a "meta-argument" to the constructor defining the type that is being stored. Using generics, we get the definition of the LinkedList from the homework:

public class LinkedList<T> implements List<T>{

    private class Node{
        T data; 
        Node next;
    }

    Node head = null;

    //rest of methods to follow ...
    void set(int i, T e){/*---*/}
    T get(int i){/*---*/}
    void add(int i, T e){/*---*/}      
    T remove(int i){/*---*/}
    int size(){/*---*/}
}

Notice that we've specified a new type-variable, T, that defines what type of elements the LinkedList stores.

To motivate iterators, consider the following simple code for iterating over a List l.

for(int i=0;i<l.size();i++){
    l.get(i);
}

What is the runtime of this procedure? First consider the ArrayList or FixedList implementation which uses an underlying array storage. It's, \(O(n)\), right? The get() operation requires a constant number of operations to access the array at index i and return the element.

What if we are using the recursive LinkedList implementation? To get() an element we must traverse from the head of the list to index i. If we do that \(n\) times, we are left with the following summation and calculation (see this article for calculating the sum of the natural numbers).

Frankly, that sucks. This should clearly be \(O(n)\). How do we get there?

The problem with the iteration above for linked list is that it doesn't preserve any state when you are doing the iteration. Every get() requires you to start over! That's where the additional \(n\) factor comes in and you get \(O(n^2)\) instead of \(O(n)\).

Java provides a means to overcome this issue using an Iterator, and you can find the documentation here. The Iterators interface defines three methods (where E is the generic):

//return true if the iteration has more elements    
boolean hasNext();

//Returns the next element in the iteration
E next();

//Removes from the underlying collection the last element returned by
//this iterator (optional operation)
void remove();

What this interface enables is that a new Iterator is generate at the start of each iteraction, storing where in the iteration we are at. You can keep call next() until there is no more elements, and you can check the case where we've reached the end using hasNext(). The remove() interface is optional.

We won't spend too much time implementing Iterator's in this class, but just to show you how this all fits together, here's an Iterator implementation for the recursive LinkedList:

import java.lang.Iterable;
import java.lang.Iterator;

//now implements Iterable
public class LinkedList<T> implements List<T>,Iterable<T>{

    private class Node{
        T data; 
        Node next;
    }

    Node head = null;

    //rest of methods to follow ...
    void set(int i, T e){/*---*/}
    T get(int i){/*---*/}
    void add(int i, T e){/*---*/}      
    T remove(int i){/*---*/}
    int size(){/*---*/}

    //Iterable interfaces require that you can return an Iterator
    public Iterator<T> iterator(){
        return new LLIteartor<T>(head);
    }

    //the Iterator we will return
    private class LLIterator implements Iterator<T>{
        private Node cur;

        public LLIterator(Node start){cur=start;}

        public boolean hasNext(){ return cur!=null; }

        public T next(){
            T data = cur.data;
            cur = cur.next;
            return data;
        }

        public void remove() { throw new UnsupportedOperationException();}
    }

}

Now, we can use the LinkedList in a foreach iteration like so:

LinkedList<String> l = new LinkedList<String>();
l.add(0,"Go Navy!");
l.add(1,"Beat Army!");

//foreach iteration, assign s to each element in l using the Iterator methods
for(String s : l){
    System.out.println(s); //prints "Go Navy!\nBeat Army!\n"
}

You can pretty easily imagine how size() is implemented for an array-based list — you just get the length of the array. But for a linked list, we have been iterating over the whole list and counting, taking \(O(n)\), right?

Well, all that work could be easily avoided by storing one extra little piece of data in the Linked List class; namely, an int for the current size of the list. This value would be updated on each add() or remove() operation, and returned by each a call to size().

public class LinkedList<T> implements List<T>,Iterable<T>{

    private class Node{
        T data; 
        Node next;
    }

    Node head = null;
    int length = 0;

    //rest of methods to follow ...
    void set(int i, T e){/*---*/}
    T get(int i){/*---*/}
    void add(int i, T e){/*---*/}      
    T remove(int i){/*---*/}

    int size(){ return length;}

There is something subtle but important about why this is okay: An ADT implementation is allowed to store extra data besides whatever information the ADT itself specifies.

In the case of a List, the ADT just specifies that you are storing an ordered sequence of elements. It says nothing about storing the size. But your data structure is allowed to store the size, in order to make the <code>size()</code> operation more efficient! The key is actually that the total storage is still the same in terms of big-O, since \(n+1 \in O(n)\).

After all of that work, we can now chart the big-O of our list implementations:

Let's use the scheme that every time we run out of room on our array, we double the size of the array. Will we have lots of unused indices? Yup. But, if our biggest number of elements in the list is \(n\), the most memory we'll use is \(2n\). And, while that might hurt, at least that's still \(O(n)\). (Yup! We can (and do) use Big-O in reference to memory, too!)

Now, we only resize every time we actually fill this too-big array. Isn't the worst case still O(n)? Well, sort of. For the first time, our "number of operations as a function of \(n\)" function isn't smoothly increasing; instead, it's spiky. This is because almost all of the time, adding to the end is O(1) because there will be space for the new element. However, every now and then, it's O(n). See:

If you drew a line threw those little red "outlier" dots, it'd be a straight line; \(O(n)\). But almost all the dots are right there at the bottom, \(O(1)\), not increasing at all even with thousands of elements in the array.

What we'd like to say is that those \(O(n)\) dots don't ultimately matter, and the real cost is \(O(1)\). Amortized analysis is what lets us say this and still be mathematically correct.

Pretend you have a business. Every 10 years, you have to buy a $100,000 machine. You have two ways you could consider this; either, every ten years you lose massively, having to pay $100,000, or every year you put aside $10,000 to be used later. This is called amortizing the cost. We can do the same thing here.

Let's assume assigning one element to an array is 1 operation. Again, if we double the size of the array every time we need more space, starting with an array of size one, we would get the following series of costs when adding 17 elements to an initially-empty array: 1 2 3 1 5 1 1 1 9 1 1 1 1 1 1 1 17.

The reason is that when the size reaches \(1, 2, 3, 5, 9, 17\), which is 1 more than each power of 2, we have to allocate a new array and copy everything over. So those are the "outlier" and expensive additions. But all the other additions are cheap; they just involve copying a single element.

But we can amortize these expensive additions over the previous "cheap" ones! Check it out:

Noticing the theme? No matter how big our list becomes, the amortized cost of a single add never gets bigger than 3. So, the cost of an add, even with resizing the array, is \(O(1)\) (amortized).

Another way of putting this is that the sum total cost of a series of \(n\) additions onto the end of an initially-empty array is \(O(n)\). In fact, if we take the same graph as above and plot the running sum instead of the individual cost of each operation, the fact that this line is \(O(n)\) becomes fairly obvious:

As you may already know, this is in fact exactly how Java's ArrayList class works. Using similar ideas they can also remove from the end of an ArrayList in \(O(1)\) amortized time, and guarantee that the space usage is kept at \(O(n)\). In fact, the previous graphs came from timing Java's own ArrayList!

There is one additional problem with the doubling-size array implementation of a List: the size of the array no longer matches the size of the list! So just like with linked lists, we have to store an extra int for the "actual" size of the list, which will always be less than the size of the array. Again, this keeps the storage as \(O(n)\) and so it's okay.

It is very important for amortized analysis that the storage array doubles when it is full, otherwise the analysis from before falls apart. The add-to-back operation becomes \(O(n)\) again. To see this we must use a bit of notation to express the amortized concepts from above. First, lets show, again, that the amortized cost of add-to-back for an array list that expands by doubling is \(O(1)\). Using that baseline, we can show that if we do something less than doubling, say constant size expansion, we go back to being an \(O(n)\) operation.

Our second ADT is the Stack. We're pretty familiar with Stacks already, so this might not be so hard. Stacks work like a stack of plates: you only add plates onto the top of the stack, and you only remove stacks from the top of the stack. This makes them a LIFO (last-in-first-out).

The methods of a stack are:

• push(e): Add element e to the top of the stack.
• pop():Take the top element off the top of the stack, and return it.
• peek() : Return the top element of the stack, without altering the stack.
• size() : Return the number of elements in the stack

Let's consider an example. On the left column of this table, I will have some commands. In the middle, I'll put what is returned, if anything. On the right, I'll put the state of the stack, with the top of the stack on the left.

Implementation with Linked Lists should seem relatively easy to you; if "first" refers to the top element of the stack, then push() is just an add-to-front, pop() is a remove-from-front, and peek is just return first.getData(); (modulo error checking for an empty stack, of course).

This means that for stacks implemented by linked lists, all three methods can be run in \(O(1)\) time. Great!

What about arrays? Well, if we used a "dumb" array, each push() and pop() would cost \(O(n)\) because of the need to copy the entire contents each time. But as we saw above with amortized ArrayList, we can be smart about this and leave some empty space in the array, doubling it when necessary. You could technically also shrink the array (halving when necessary) in pop(), but that makes everything more cumbersome, so we'll assume the resizings only happen during push() only.

OK, so stacks are fast! What can we do with them?

• Reverse stuff - pushing everything on, and then popping it all off puts it in reverse order.
• Maze solving - every time you come to a junction, push it on the stack. When your decision doesn't work out, pop to the last junction, and go the other way. If there are no more possible directions, pop again.
• For more complex uses of stacks, stay tuned…

And, you'll see Maze solving in the project!

We know Queues well from IC211. If a Stack is a LIFO (Last-In First-Out), then a Queue is a FIFO (First-In First-Out). In other words, things come out in exactly the same order they went in.

Think about a line for the checkout counter at the grocery store (after all, "queue" is British for "line"). People can only join the line at the end, and only leave the line at the front. In between, they never switch order.

The methods a Queue must have are:

• enqueue(e): Add an element to the back of the Queue
• dequeue(): Remove and return the front element of the Queue
• peek(): Return, but do not remove, the front element of the Queue
• size(): Return the number of elements in the queue

Implementation with a Linked List is fairly straightforward. Enqueue is just an add-to-back operation, which is \(O(1)\) if we have a tail reference to track the last Node in the linked list. Just like we discussed with the size() operation, adding new book keeping elements is totally fine for a ADT.

Dequeue is also simple, and is remove-from-front operation, which, again, is \(O(1)\). We already track the front of the list with a head reference, so we are good to go there.

Finally, peek() is the same as dequeue() but without removal. That operation just returns the value of the first Node in the list, like head.getData(), which is clearly \(O(1)\).

So, Linked Lists are great(!) at implementing Queues. What about ArrayLists?