Chapter 3 Lists, Stacks, and Queues
3.1 Abstract Data Types (ADTs)
An abstract data type (ADT) is a set of objects together with a set of operations. Abstract data types are mathematical abstractions; nowhere in an ADT’s definition is there any mention of how the set of operations is implemented.
3.2 The List ADT
We will deal with a general list of the form
3.3 Lists in the Java Collections API
3.3.1 Collection Interface
The Collections API resides in package java.util.
The Collection interface extends the Iterable interface. Classes that implement the Iterable interface can have the enhanced for loop used on them to view all their items.
3.3.2 Iterators
Collections that implement the Iterable interface must provide a method named iterator that returns an object of type Iterator. The Iterator is an interface defined in package java.util.
public interface Collection<E> extends Iterable<T> {
......
java.util.Iterator<E> iterator();
}
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}The main advantage of the Iterator’s remove method is that the Collection’s remove method must first find the item to remove.
When using the iterator directly (rather than indirectly via an enhanced for loop) it is important to keep in mind a fundamental rule: If you make a structural change to the collection being iterated (i.e., an add, remove, or clear method is applied on the collection), then the iterator is no longer valid (and a ConcurrentModificationException is thrown on subsequent attempts to use the iterator). This is a second reason to prefer the iterator’s remove method sometimes.
3.3.3 The List Interface, ArrayList, and LinkedList
The List interface specifies the listIterator method that produces a more complicated iterator than normally expected.
The ArrayList provides a growable array implementation of the List ADT. The advantage of using the ArrayList is that calls to get and set take constant time. The disadvantage is that insertion of new items and removal of existing items is expensive, unless the changes are made at the end of the ArrayList.
The LinkedList provides a doubly linked list implementation of the List ADT. The advantage of using the LinkedList is that insertion of new items and removal of existing items is cheap, provided that the position of the changes is known. This means that adds and removes from the front of the list are constant-time operations, so much so that the LinkedList provides methods addFirst and removeFirst, addLast and removeLast, and getFirst and getLast to efficiently add, remove, and access the items at both ends of the list. The disadvantage is that the LinkedList is not easily indexable, so calls to get are expensive unless they are very close to one of the ends of the list.
Both ArrayList and LinkedList are inefficient for searches, so calls to the Collection contains and remove methods take linear time.
3.3.4 Example: Using remove on a LinkedList
public static void removeEvensVer1(List<Integer> lst) {
int i = 0;
while(i < lst.size())
if(lst.get(i) % 2 == 0)
lst.remove(i);
else
i++;
}On an ArrayList, as expected, the remove is not efficient, so the routine takes quadratic time. A LinkedList exposes two problems. First, the call to get is not efficient, so the routine takes quadratic time. Additionally, the call to remove is equally inefficient, because it is expensive to get to position i.
public static void removeEvensVer2(List<Integer> lst) {
for(Integer x: lst)
if(x % 2 == 0)
lst.remove(x);
}This is not an efficient operation because the remove method has to search for the item again, which takes linear time. But if we run the code, we find out that the situation is even worse: The program generates an exception because when an item is removed, the underlying iterator used by the enhanced for loop is invalidated.
public static void removeEvensVer3(List<Integer> lst) {
Iterator<Integer> itr = lst.iterator();
while(itr.hasNext())
if(itr.next() % 2 == 0)
itr.remove();
}For a LinkedList, the call to the iterator’s remove method is only constant time, because the iterator is at (or near) the node that needs to be removed. Thus, for a LinkedList, the entire routine takes linear time, rather than quadratic time. For an ArrayList, even though the iterator is at the point that needs to be removed, the remove is still expensive, because array items must be shifted, so as expected, the entire routine still takes quadratic time for an ArrayList.
3.6 The Stack ADT
3.6.1 Stack Model
A stack is a list with the restriction that insertions and deletions can be performed in only one position, namely, the end of the list, called the top. The fundamental operations on a stack are push, which is equivalent to an insert, and pop, which deletes the most recently inserted element. The most recently inserted element can be examined prior to performing a pop by use of the top routine. A pop or top on an empty stack is generally considered an error in the stack ADT. On the other hand, running out of space when performing a push is an implementation limit but not an ADT error.
Stacks are sometimes known as LIFO (last in, first out) lists.
3.7 The Queue ADT
Queues are lists. With a queue, however, insertion is done at one end, whereas deletion is performed at the other end.
3.7.1 Queue Model
The basic operations on a queue are enqueue, which inserts an element at the end of the list (called the rear), and dequeue, which deletes (and returns) the element at the start of the list (known as the front).
3.7.2 Array Implementation of Queues
For each queue data structure, we keep an array and the positions front and back, which represent the ends of the queue.
After some enqueues, the queue appears to be full, since back is now at the last array index, and the next enqueue would be in a nonexistent position. The simple solution is that whenever front or back gets to the end of the array, it is wrapped around to the beginning. The following figures show the queue during some operations. This is known as a circular array implementation.