Linked Lists and Other Structures

Arrays are much like Tupperware. They are great containers, but they are of a fixed size. If you pick a container that is too large, you waste space in your storage area. If you pick one that is too small, its contents spill all over and you have a big mess.

One way to solve this problem is with a linked list. A linked list is a data structure that consists of small containers that “snap together.”

Containers, in this context, are classes that contain the objects to be held in the list. The idea is to write a class that holds one object of your data—such as one CAT or one Rectangle—and that can point at the next container in the list. You create one container for each object that you need to store, and you chain them together as needed.

These small containers are called nodes. The first node in the list is called the head, and the last node in the list is called the tail.

Lists come in three fundamental forms. From simplest to most complex, they are

Singly linked

Doubly linked

Trees

In a singly linked list, each node points to the next one forward, but not backward. To find a particular node, you start at the top and go from node to node, as in a treasure hunt (“The next node is under the sofa”). A doubly linked list enables you to move backward and forward in the chain. A tree is a complex structure built from nodes, each of which can point in two or three directions. Figure 19.1 shows these three fundamental structures.

Computer scientists have created even more complex and clever data structures, nearly all of which rely on interconnecting nodes.