The following notes present the basic algorithms and techniques used in dynamic data structures. We also include some basic keyrmation about recursive algorithm2. In particular, the topics we cover are as follows:
The algorithms are generally presented as Java functions (methods) operating on lists of integers, however, note that these algorithms are only the minimal specification of what would be used in a practical situation. You would need to embed these in the appropriate classes to accomplish a specific purpose.
All the code below assumes the following declaration:
class Node {
public int key;
public Node next;
Node(int n, Node p) {
key = n;
next = p;
}
};
Node head;
Note that references in Java are initialized to null by default. This constructor will simplify a number of the algorithms below. For example, to create a list with one element containing the key 5, we could write:
head = new Node(5,null);
To add a node containing a 7 to the front of an existing list, we could simply write
head = new Node(7, list);
and if we have a reference p to a node in a list, we can add a new node containing 13 after p (i.e., between
the node p and the node p.next) by writing:
p.next = new Node(13, p.next);
Note that it can also be used to create simple linked lists
in a single Java statement. For example, to create a list containing
the integers 7, 8, and 12, we could write:
head = new Node( 7, new Node( 8, new Node( 12, null) ) )
The basic thing you do with a list is to "chain along" the list, performing some operation at each node (such as counting the number of nodes, or looking for a particular node). This is done with a simple for loop that initializes a reference to the first node and stops when it reaches null. Note that this loop will execute once for each node in the list, pointing p at each node in turn:
for(Node p = head; p != null; p = p.next ) {
// Do something at each node in the list
}
for(Node p = head; p != null; p = p.next )
if( C ) {
// do something to the node that p refers to
break; // if you want to stop the chaining along
}
Note that we can refer to p.key and p.next in the loop body with no worry of a NullPointerException, because we have already checked that p != null in the for loop condition.
Another possibility is to chain along, but perform some check on the next node in the list; for example, when inserting a number n into a sorted list, you need to check if the next node is bigger than n (if so, you insert N after the current element).
for(Node p = head; p != null; p = p.next )
if ( p.next != null && p.next.key has some property ) {
// Do something
}
Note that due to the lazy nature of the && Boolean operator, the only way the p.next.key gets referred to is when p.next != null tests true. Sometimes, the check for null before following a reference gets a little messy;
the next technique does the same thing, but is usually preferable.
A final paradigm is to chain along, but keep a reference q trailing p, so that you always have a reference to the previous element (except for the first time through the loop, when q has no value); this is an alternative to the previous look-ahead technique that solves a basic problem in SLLs: when you chain along, you lose the reference to the previous node:
Node q;
for(Node p = head; p != null; q = p, p = p.next ) {
// During first iteration, p points to first element and q has no value;
// thereafter, p points to a node and q points to the previous node
}
We will use these techniques in the iterative algorithms below.
This algorithm is a good place to start, as it uses the first chaining-along technique very simply:
void print() {
for(Node p = head; p != null; p = p.next )
System.out.println(p.key);
}
Another simple application of chaining along:
int length( ) {
int i=0;
for( Node p = head; p != null; p = p.next )
++i;
return( i );
}
This next function is a standard one that uses the double-condition for loop technique; it returns a reference to the node containing n if it exists, and null otherwise:
int lookup( int n) {
for( Node p = head; p != null; p = p.next )
if( p.key == n )
return p;
return p; // return null if key not found
}
We next show how to delete a node in a list, two different ways; the first uses the lookahead technique:
void deleteNode( int n ) {
Node q;
if ( head != null && head.key == n ) { // special case that you need to delete first node
head = head.next;
return;
}
for( Node p = head; p != null; p = p.next )
if( p.next != null && p.next.key == N ) {
p.next = p.next.next;
return;
}
}
The algorithm can also be written using the two pointer technique:
void deleteNode( int n ) {
Node q;
if ( head != null && head.key == n ) {
head = head.next;
return;
}
for( Node p = head; p != null ; q = p, p = p.next )
if( p.key == n ) {
q.next = p.next;
return;
}
}
This will remove the first instance of the key (in case there are duplicates); if you would like to
remove all instances, then remove the two return statements. This will work with unordered or ordered lists, although with
an ordered list it will traverse the entire list, even when you have gone past the location where the key would be.
We have shown above how easy it is to insert an item into the first position using the Node() constructor; inserting into a sorted list (in ascending order) is quite similar to the delete algorithm and again uses the two-reference technique. Unfortunately, there are three cases to consider (two involving the head reference) and this makes it a little messy. We shall combine two of the cases into one if statement, relying on the fact that the second half of an OR condition is evaluated only if the first half is false:
void insertSorted( int n ) {
Node q;
if ( head == null || n < head.key )
head = Node( n, head );
else {
for( Node p = head; p != null; q = p, p = p.next )
if( n < p.key) {
q.next = Node( n, p );
return;
}
}
}
The special cases in these algorithms, when you need to treat the first node differently than the rest, is often avoided by having a dummy first node that contains a sentinel value (say, Integer.MIN_VALUE) as a key. In this case, you would initialize your list using:
Node head = Node(Integer.MIN_VALUE,null)
and then simply eliminate the first case in the if statement in these last three algorithms. Or, when using the two pointer technique, start the for loop off with the two pointers pointing at the first two nodes:
void deleteNode( int n ) {
for( Node q = head, Node p = head.next; p != null ; q = p, p = p.next )
if( p.key == n ) {
q.next = p.next;
return;
}
}
void insertSorted( int n ) {
for( Node q = head, Node p = head.next; p != null; q = p, p = p.next )
if( n < p.key) {
q.next = Node( n, p );
return;
}
}
}
This algorithm is probably one of the most difficult for linked lists; it uses three references which chain down the list together and rearrange the next references so that they point to the precessor instead of the successor in the list. This assumes NO header node; if you have a dummy header node, then you would want to start off with pt1 = head.next.
void reverse( ) {
Node pt1 = head, pt2 = null, pt3;
while ( pt1 != null ) {
pt3 = pt2; // pt3 follows pt2
pt2 = pt1; // pt2 follows pt1
pt1 = pt1.next; // pt1 moves to next node
pt2.next = pt3; // link pt2 to preceding node
}
list = pt2;
}
Recursively defined algorithms are a central part of any advanced programming course and occur in almost every aspect of computer science. Although they are difficult to understand initially, after one gets the knack, they are easier to write, debug, and understand than their iterative counterparts. In many cases, the only realistic solution possible for a certain problem is recursive.
Let us examine the definition of the factorial function. We can define the factorial of a number n, notated n!, in two ways:
int factorial( int num ) {
int fact = 1;
for (i = 1; i <= num; ++i)
fact = fact * i;
return(fact);
}
The second definition of n! is, at first glance, nonsense, because we
are defining something in terms of itself. Its like asking someone what the food
at a Thai restaurant is like and he tells you, ``Well, it's kind of like food
from Thailand." Or you look up ``penultimate" in the dictionary and it says ``just
after propenultimate;" but when you look up ``propenultimate" it's defined as
``just before penultimate." Actually our example is not exactly this paradoxical,
because we are defining our object, if you look closely, in terms of a slightly
different object. That is, n! is defined in terms of ( n-1)!, which
has a smaller value before the ``!". Also, the definition has a condition: when
the value of n is small enough, i.e., 1, the factorial is just given explicitly
as 1. Since the recursive part always defines the factorial in terms of the factorial
of a smaller number, we must reach 1 eventually. This is the trick which
allows us to define mathematical objects in this way. We must define a mathematical
function explicitly for some values, and then we can define other values in terms
of the function itself, as long as the function will eventually reach one
of the explicit values. Let us look at the Java for this version of the function:
int factorial( int num ) {
if ( num == 1 )
return 1;
else return n * factorial( num - 1 );
}
This function has the following standard features of any recursively defined procedure
or function:
Let's look at another simple recursive algorithm similar to the factorial function:
int power( int num, int exponent ) {
if ( exponent == 1 )
return num;
else return num * power( num, exponent - 1 );
}
Here we are determining the value of an integer num raised to a power
exponent. We could have written this explicitly by just creating a
for loop to multiply num by itself exponent number of times,
i.e., 5^4 = 5 * 5 * 5 * 5. But the recursive algorithm says that, for example,
5^4\ is just 5 * (5^3), which is just 5 * (5 * (5^2) ), which is just 5 * (5 *
(5 * (5^1) ) ), which is just 5 * 5 * 5 * 5. So they really do the same thing
in different ways. Note again that the recursive call involves the function calling
itself on arguments which get closer to the base case--if you keep subtracting
1 from exponent you will eventually reach 1. Try this algorithm on
Power(2, 5).
Another recursive algorithm we could write would be for calculating the Nth Fibonacci number. Recall that the Fibonacci numbers form a series in which the first two values are both 1, and each successive value is the sum of the previous two values:
1 1 2 3 5 8 13 21 34 55 89 ....
Thus the third Fibonacci number is 2, the seventh is 13, and so on. Note how the
definition is phrased: ``the first two values are both 1" (an explicit answer
is given), ``and each successive value is the sum of the previous values"(the
rest are defined in terms of previous values in the series). This is clearly translatable
into a recursive algorithm with almost no effort:
int fibonacci( int n ) {
if ( n < 2 )
return 1;
else return fibonacci(n-2) + fibonacci(n-1);
}
This is obviously a Java version of the English definition above, but will it work?
After all, it calls itself not once but twice! The base case assures us, however,
that this must stop eventually, since we call the function on smaller
values each time. It must reach Fibonacci(1) or Fibonacci(2) eventually.
In fact, this is not a very efficient way to calculate the Fibonacci numbers,
since we must cover the same ground twice to get each number. It does work, however,
and is an exact translation of the English definition we started with. In other
words, it is a more natural expression of the original problem than an iterative
algorithm, because the original definition is recursive. Again, try this
on some small values to convince yourself that it works.
A slightly more difficult algorithm which can be written recursively is Euclid's Greatest Common Divisor algorithm, which has pride of place as the oldest recursive algorithm in existence. This ancient Greek mathematician discovered that we can find the largest integer which divides two given integers evenly if we generate a series of values a follows:
28 18 10 8 2 0.
Thus 2 is the greatest common divisor of 28 and 18. This method is essentially
a recursive algorithm, although it may not be obvious at first. Notice that we
perform the same action on each pair of numbers: we divide the first by the second
and write down the remainder, then continue with the second number and the remainder
just obtained, etc., until we reach 0. The recursive algorithm looks like this:
int gcd( int num1, int num2 ) {
{
if ( (num1 % num2) == 0 )
then gcd = num2;
else gcd = gcd( num2, (num1 % num2) );
}
This algorithm will implicitly create the list (except for the 0, which just indicates
that the previous number divides the number before it evenly) that we showed above
if you call gcd(28, 18). It's tricky, but it does nothing really different
than the recursive algorithms we have examined so far. It's worth tracing through
on some simple input.
We have presented here a number of recursive functions returning values, but it is important to realize that void functions (not returning values) can be written recursively as well. For example, many sorting algorithms are written as recursively.
Other recursive algorithms are presented below for singly-linked lists and for tree structures. These are important algorithms which show the advantages of recursion clearly. For some, like the printing procedures for singly-linked lists, the iterative and recursive versions are of about equal complexity. For others, like the cell deletion algorithm, the difference is more pronounced in favor of the recursive version. For another class of algorithms, such as the tree walk and insertion procedures, the recursive version is really the only reasonable solution. In general, when a data structure is defined recursively(like a tree or a linked list) the most natural algorithms are recursive as well. To use these advanced data structures one must have a firm understanding of recursion. Those interested in pursuing this topic should try writing the recursive algorithms suggested in the notes on singly-linked lists below and should look up other recursive algorithms, such as Quicksort, Mergesort, the Tower of Hanoi, or practically any algorithm which involves trees.
NOTE: In the recursive algorithms which follow, we do NOT use the Dummy Header Node technique described above---it is not necessary!
This is a simple algorithm, and good place to start. Recursion allows us flexibility in printing out a list forwards or in reverse (by exchanging the order of the recursive call):
void printList( Node p ) {
if (p != null) {
System.out.println(p.key);
printList( p.next );
}
}
void printReverseList( Node p ) {
if (p != null) {
printReverseList( p.next );
System.out.println(p.key);
}
}
// Example of use:
printList( head );
Another simple recursive function.
int length( Node p ) {
if (p == null) {
return 0
else
return 1 + length( p.next );
}
}
When changing the structure of a linked list by deleting to adding nodes, it is useful to think in terms of reconstructing the list. Suppose you wanted to trivially reconstruct a list by reassigning all the references. You could do this:
Node construct( Node p ) {
if( p == null )
return null;
else {
p.next = construct( p.next );
return p;
}
}
// Example of use:
head = construct( head );
Pretty silly, right? But if we use this as a basis for altering the list recursively, then it becomes a very useful paradigm. All you have to do is figure out when to interrupt the silliness and do something useful. Here is a simple example, still kind of silly:
Node addOne( Node p ) {
if( p == null )
return null;
else {
p.next = construct( p.next );
++p.key;
return p;
}
}
// Example of use:
head = construct( head );
This recursively traverses the list and adds one to every key in the list. Following are some definitely non-silly algorithms using the approach to traversing the list.
I'll repeat again that when using this "reconstruct the list" paradigm, we do NOT need to use a dummy header node to avoid the special case of the first node in the list.
Node insertInOrder( int k, Node p ) {
if( p == null || p.key >= k ) {
return new Node( k, p );
else {
p.next = insertInOrder( k, p.next );
return p;
}
}
// Example of use:
head = insertInOrder( 7, head );
This algorithm deletes the first occurrence of an item from a list. A simple change enables this algorithm to delete all occurrence of the item, by continuing to chain down the list after the key has been found. We assume that the list is unordered; you can easily change this to stop after finding a key beyond the search key by changing the first if condition.
Node deleteItem( int k, Node p ) {
if( p == null ) // if the list is ordered use: ( p == null || p.key > k )
return p;
else if ( p.key == k )
return p.next; // if you want to delete all instances, use: return deleteItem( k, p.next );
else {
p.next deleteItem( k, p.next );
return p;
}
}
deleteLast( Node p ) {
if( p == null || p.next == null )
return p;
else {
p.next deleteLast( k, p.next );
return p;
}
}
Appending two lists is a simple way of creating a single list from two. For this one, we'll only give the recursive algorithm, as we'll assume at this point that you are convinced that recursion is better than iteration. This function add the second list to the end of the first list:
Node append( Node p, Node q ) {
if ( p == null) {
return q;
else {
p.next = append( p.next, q )
return p;
}
}
Here is a more complex function to combine two lists; it simply zips up two lists, taking a node from one, then from the other. The first list in the original call now points to the new list.
Node zip( Node p, Node q ) {
if ( p == null) {
return q;
else if ( q == null) {
return p;
else {
p.next = zip( q, p.next );
return p;
}
Example of call:
head = zip( head, anotherlist );
If head points to 3 4 7 and anotherlist points to 2 5 6 8, then
at the end of this call to zip, head will point to 3 2 4 5 7 6 8.
Here is another more complex function to combine two lists; this one merges nodes from two sorted lists, preserving their order:
Node merge( Node p, Node q ) {
if ( p == null) {
return q;
else if ( q == null) {
return p;
else if (p.key < q.key) {
p.next = zip( p.next, q );
return p;
}
else {
q.next = zip( p, q.next );
return q;
}
}
Example of call:
head = zip( head, anotherlist );
If head points to 3 4 7 and anotherlist points to 2 5 6 8, then
at the end of this call to zip, head will point to 2 3 4 5 6 8.
Some other recursive algorithms(in increasing order of difficulty) you might want to try writing along the lines of those above are: