Java Cookbook

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 one of the more common ones, the linked list. A linked list is commonly used when you have an unpredictably large number of data items, 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 ...