CSC-207 Data Structures
Chapter 4 – Linked Lists – the last part
There are only a
few more miscellaneous topics to discuss concerning linked lists in Java.
1.
Processing
a linked list recursively
I suppose you
thought you were done with recursion. Not quite! Consider the following two
recursive methods.
private static
void writeList(Node nextNode) {
//
---------------------------------------------------------
// Writes a list
of objects.
// Precondition:
The linked list is referenced by nextNode.
//
Postcondition: The list is displayed. The linked list
// and nextNode
are unchanged.
//
---------------------------------------------------------
if (nextNode != null) {
// write the first data object
System.out.println(nextNode.getItem());
// write the list minus its first node
writeList(nextNode.getNext());
} //
end if
} // end writeList
private static
void writeListBackward2(Node nextNode) {
//
----------------------------------------------------
// Writes a list
of objects backwards.
// Precondition:
The linked list is referenced by
// nextNode.
//
Postcondition: The list is displayed backwards. The
// linked list
and nextNode are unchanged.
//
----------------------------------------------------
if (nextNode != null) {
// write the list minus its first node
backward
writeListBackward2(nextNode.getNext());
// write the data object in the first node
System.out.println(nextNode.getItem());
} // end if
} // end writeListBackward2
One of these
methods prints the data items in a linked list in a forward manner and one
prints them in a backward manner. Let’s draw a list on the board and follow the
code to see what happens.
2.
Variations
on a linked list – a circular linked list.
There are many
applications that require what are known as circular linked lists. For example,
suppose you have a computer that has a number of terminals hooked to it (like a
server) and you need to give each person at each terminal a “slice” of time. A
circular list would be nice. Also in operating systems, we say that many tasks
(programs) can run at the same time. This is really misleading because the CPU
can only handle one instruction at a time. Therefore some operating systems use
a time-sharing technique where they keep tasks in a circular list and run each
task for a period of time or until the task does an input/output operation.
Then the OS forces the CPU to switch to the next task in the list.
A circular linked list is almost the same as a regular linked list
except the pointer in the last node points back to the first node. You can
still have sorted circular linked lists, such as 5, 8, 10, in which case there
is a first and a last element. But you could also have unsorted linked lists,
such as dog, cat, canary, fish, in which there is really no first or last
element. It’s up to you.
As an example, here
is code that could be used to display the data from a circularly linked list.
// display the
data in a circular linked list;
// list
references its last node
Node list =
null;
if (list !=
null) {
// list is not empty
Node first = list.getNext(); // reference
first node
Node curr = first; // start at first node
// Loop invariant: curr references next node
to
// display
do {
// write data portion
System.out.println(curr.getItem());
curr = curr.getNext(); // reference next node
} while (curr != first); // list traversed?
} // end if
3.
Variations
on a linked list – a linked list with a dummy head node.
Remember when we were adding and removing
the nodes from a list. There was a special case if we were adding or removing
the first node of the list. Some folks decide to do away with that problem by
always including a “dummy” node as the first node in the list. Actually we
could get very fancy about this and make the dummy node be somewhat different
than the other nodes. There is an example like this is your textbook where the
dummy node actually has another object in the data item position. This object
contains things like length, smallest number and largest number for the list.
Thus you could build:
public
class ListInfo {
private
int length;
private
Object smallestItem, largestItem;
…
}
and initialize a dummy node like this:
Node head = new
Node(new ListInfo(3, 5, 10, listNode));
But I think this is a little bit of overkill. We could just as easily
keep all of that data in the list class as separate data items rather than
sticking them in a dummy node.
4.
Variations
on a linked list – a doubly linked list.
Suppose you were processing a list as
usual and you get to the end, but then you need to go back to the next to the
last item in the list. In a regular list you would have no option but to start
at the beginning of the list again and then loop thru the nodes until you got
to the next to the last one. Why? Because there is no pointer from the last
node to the next to the last node! But we could change that by adding another
pointer to our definition of a node. For example:
public class Node {
private
Object item;
private
Node next;
private
Node prev;
…
}
At any given node
the “prev” pointer points to the previous node. Just as the “next” pointer is
null for the last node in a list, the “prev” pointer is null for the first node
in a list.
Let’s try to
rewrite the “add” method for a linked list if the linked list is doubly linked.
OK, that is the end of our discussion on
linked lists. Your textbook has a neat problem at the end of the chapter to
explain how a linked list may be used in a real life situation, maintaining an
inventory for a video store. It would be good for you to read that section.
This really gets into what data structures are all about.