Essential Algorithms, 2nd Edition

CHAPTER 3Linked Lists

Linked lists are probably the simplest data structures you'll build. However, some of the concepts you use to build them are also used to build the most sophisticated data structures described in this book. To use a linked list, you need to understand cells and links in addition to methods of finding, inserting, and deleting cells. You use those same concepts to build complicated networks, trees, and balanced trees, which can be extremely confusing.

This chapter explains the ideas you need to master to use linked lists. Later chapters (in particular, Chapters 4, 5, 8, and 10 through 14) revisit these ideas.

Basic Concepts

A linked list is built of objects that are often called cells. The cell's class contains whatever data the list must store plus a link to another cell. The link is simply a reference or pointer to another object of a cell's class. Often, the pointer field in the cell class is called Next.

For example, the following code shows the definition of an IntegerCell class in C#. The cell holds an integer value and a pointer to the next IntegerCell object in the linked list.

class IntegerCell
{
    public int Value;
    public IntegerCell Next;
} 

Linked lists are often represented graphically, with boxes representing cells and arrows representing links.

To indicate a link that doesn't point to anything, I use a small box with an X in it. (In a programming language, the value of the pointer corresponding to the link would be nothing, null, none, or ...