Linked Lists and Their Operations

Suppose you are writing a program that must keep a list of names in alphabetical order. You need to add names, remove names, and check whether a name is present. A natural first question is where the names should live in memory and how the list should be arranged internally. This article asks a different question first: what exactly is the list, apart from the way it happens to be stored?

The answer leads to a central idea in software engineering, the abstract data type, usually written ADT. Once you see what an ADT is, you will also see why the same list of names can be stored in very different ways without changing the rest of the program. Linked lists are one of those ways, and they are the subject of the rest of this article.

The definition has two halves, and both matter. The first half names the values the type can take. The second half names the operations that act on those values. The definition is silent on everything else. It does not say whether the values sit in a chain of linked objects, in a fixed-size block, or somewhere else. It does not say how an operation works internally. It describes only what is possible and what can be done with it.

Take the ordered list of strings as an example. Any sequence of strings arranged in increasing order is a possible value of this type. The operations include inserting a new string, deleting a string, and finding a string in the list. Notice what is absent from that description: nothing in it mentions arrays, linked objects, or pointers. Those details belong to a later decision, the implementation.

The source makes a striking observation: the same list could just as easily have been stored in an array or an ArrayList, and the same operations could still have been implemented on it. A linked list is one implementation of the ordered list of strings. An array-based list is another. Both realize the same ADT.

The internal code for those operations would look different in each case. An array-based insert and a linked-list insert do not work the same way on the inside. Yet their interfaces and their logical behavior stay the same. Callers still ask for an insert, and the list still ends up in the same order. This is the core of what makes an ADT useful: one abstract type can have several implementations.

The source describes this idea as data abstraction: separating the interface of a data structure from its implementation. The interface is the set of operations a caller can use, along with their logical behavior. The implementation is the concrete way those operations are carried out. Data abstraction keeps these two apart on purpose.

Think of the calling program as sitting above the interface and depending only on it. The implementations sit beneath the interface, and either one can fill the role. Because the dependency stops at the interface, a change to the storage below it does not reach the program. If a team writes its program against the abstract definition, then switching the storage later is a change confined to the implementation.

In a linked list, the list is not stored as one continuous block. Instead, it is built from separate pieces that are tied together. Each piece knows where the next piece is. Once you understand that single idea, most of the behavior of a linked list follows from it.

Read the diagram as a set of arrows. Each arrow starts at one node's reference and lands on the next node. No node in the middle is reached directly from the list as a whole; every node is reached by leaving the node before it. This is the defining feature of the structure and the reason it is called a linked list. The chain has a beginning, which is the first node, and it ends when a node has no next node to point to.

To reach an element, a program starts at the first node and follows references one at a time. To find an element in a linked list, a program starts at the first node and examines its data. If that is not the element it wants, it follows the node's reference to the next node and repeats the check. The program never jumps directly to the third element. Each step depends on the reference stored in the node just visited.

In the after state, the first-node reference reaches only Dee, and Dee has no reference to Ana. Ana, Ben, and Cruz still exist as objects, but nothing in the list leads to them. The fix is to link Dee to Ana first, and only then move the first-node reference to Dee.

An implementation is only trustworthy once it has been tested. The source material pairs StringList.java, which implements a linked list of strings, with a separate program, ListDemo.java, whose job is to test the StringList class. Keeping the test in its own program separates the code that builds the list from the code that checks it.

It is worth thinking of a test as a second view of the same chain. You build a list, add or read strings, and confirm that the results match what the chain should contain. If the test finds a missing name after an insert, the likely cause is a broken or missing reference rather than a problem with the names themselves.