APPENDIX E
A Look at Linked Lists
On Day 13, “Managing Arrays and Strings,” you learned about arrays. You also
learned what a linked list is. A linked list is a data structure that consists of
small containers that are designed to link together as needed. The idea is to
write a class that holds one object of your data that can point at the next con-
tainer of the same type. You create one container for each object that you need
to store, and you chain them together as needed.
The 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 forward to the next one, but not back-
ward. To find a particular node, 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 more directions. Figure E.1
shows these three fundamental structures.
33 0672327112_app_e.qxd 11/19/04 12:30 PM Page 875