Recipe 7.5 Structuring Data in a Linked List

Problem

Your data isn't suitable for use in an array.

Solution

Write your own data structure(s).

Discussion

Anybody who's taken Computer Science 101 (or any computer science course) should be familiar with the concepts of data structuring, such as linked lists, binary trees, and the like. While this is not the place to discuss the details of such things, I'll give a brief illustration of the common linked list. A linked list is commonly used when you have an unpredictably large number of data items, you wish to allocate just the right amount of storage, and usually want to access them in the same order that you created them. Figure 7-1 is a diagram showing the normal arrangement.

Figure 7-1. Linked list structure

Here is code that implements a simple linked list:

/**  * Linked list class, written out in full using Java.  */ public class LinkList {     public static void main(String argv[]) {         System.out.println("Here is a demo of a Linked List in Java");         LinkList l = new LinkList( );         l.add(new Object( ));         l.add("Hello");         System.out.println("Here is a list of all the elements");         l.print( );         if (l.lookup("Hello"))             System.err.println("Lookup works");         else             System.err.println("Lookup does not work");     }     /* A TNode stores one node or item in the linked list. */     class TNode {         TNode next;         Object data;         TNode(Object o) {             data = o;             next = null;         }     }     protected TNode root;     protected TNode last;     /** Construct a LinkList: initialize the root and last nodes. */     LinkList( ) {         root = new TNode(this);         last = root;     }      /** Add one object to the end of the list. Update the "next"       * reference in the previous end, to refer to the new node.       * Update "last" to refer to the new node.       */     void add(Object o) {         last.next = new TNode(o);         last = last.next;     }     public boolean lookup(Object o) {         for (TNode p=root.next; p != null; p = p.next)             if (p.data==o || p.data.equals(o))                 return true;         return false;     }     void print( ) {         for (TNode p=root.next; p != null; p = p.next)             System.out.println("TNode" + p + " = " + p.data);     } }

This approach works reasonably well. But it turns out that many applications use linked lists. Why should each programmer have to provide his or her own linked list class, each with a slightly different set of bugs? You don't have to provide your own square root function or write your own Remote Method Invocation services. Accordingly, Java has a LinkedList class; here is a similar program that uses it:

import java.util.*; /**  * Demo 1.2 java.util.LinkedList; same example as my older LinkList class.  */ public class LinkedListDemo {     public static void main(String argv[]) {         System.out.println("Here is a demo of Java 1.2's LinkedList class");         LinkedList l = new LinkedList( );         l.add(new Object( ));         l.add("Hello");         System.out.println("Here is a list of all the elements");         // ListIterator is discussed shortly.         ListIterator li = l.listIterator(0);         while (li.hasNext( ))             System.out.println(li.next( ));         if (l.indexOf("Hello") < 0)             System.err.println("Lookup does not work");         else             System.err.println("Lookup works");     } }

As you can see, it does pretty much the same thing as my LinkList but uses the existing class java.util.LinkedList instead of having you roll your own. The ListIterator used here is a subinterface of an Iterator, which was discussed in Recipe 7.4.