Stacks and Queues as implemented using a LinkedList

When speed is more important, you need to use an array.
When memory is more important, you need to use a LinkedList.

Have you noticed that in both the stack and the queue, we have to use a 'MAX_SIZE' variable to maintain the length of elements and to do memory management within each structure? It's just a list. We've already proven that the linked list is better suited for arrays than arrays themselves when memory is concerned.

Why don't we implement the Stacks and Queues with LinkedList? Because then the problem becomes too easy.

With both the stack and the queue, memory is more important than speed. If we implement a Queue as a LinkedList, "dequeue" and "front" are almost as their array-based counter parts, but the "enqueue" method is a little slower. The Stack operations when implemented in a LinkedList all require some looping, making them a little slower than their array-based counter parts.

Nothing says we can't implement them together either.

class List<T> extends LinkedList<T> {
void push(T data)    { insert(data, size());    }
T    pop()           { return remove(size()-1); }
T    top()           { return get(size()-1);    }
void enqueue(T data) { insert(data, size());    }
T    dequeue()       { return remove(0);        }
T    front()         { return get(0);           }
} // End Class

Doubly-Linked List

In our LinkedList implementation, we use a Node structure which has a data field and a next field. A more sophisticated version of the LinkedList uses a second link in each node. The purpose of this link is to point to the previous node. In addition to a second link in each node, there exist a "tail" object which points to the last element in the linked list.

Show drawings of how to perform insert and removal using a doubly-linked list.

More on Recursion

The most common example of recursion is the factorial problem. The factorial of a number is represented by "x!", such as "5!", this means "1*2*3*4*5", which is 120. We can easily compute this with an iterative loop.

int ifact(int x) {
int f = 1;
for (int i = 2; i <= x; i++)
f *= i;
return f;
}
int rfact(int x) {
if (x == 1) return 1; // Base Statement
return x * fact(x-1); // Recursive Statement
}

This piece of code shows how we "descend" deeper into a loop using recursion and then "ascend" back up to the top level.

static void deep(int level) {
System.out.println("Entering "+level);
if (level == 0) {
System.out.println("Hit bottom.");
return;
}
deep(level-1);
System.out.println("Leaving "+level);
}

If call "deep(3)", the following happens:

Entering 3
Entering 2
Entering 1
Entering 0
Hit bottom.
Leaving 1
Leaving 2
Leaving 3

How might we write a recursive method to compute the modulus of the division of two numbers?

int mod(int num, int denom) {
if (num < denom)
return num;
return mod(num-denom, denom);
}