Linked Lists

A linked list is a recursive data structure that is either empty (null) or a reference to a node have a data item and a reference to a linked list. Through this structure, a linked list creates a sequence of nodes chained together, where each node contains a data item and a reference to the next node.

Below is an example of a node class for a linked list:

class Node {
   Item item;
   Node next;
}

Note, the node class is self-referential. That is to say, the node class contains a reference to itself.

Also, a reference to a linked list can simply be a reference to the first node of that list. That said, one often encapsulates the reference to the first node of a given linked list as an instance variable in some enclosing linked list class.

Linked lists and arrays are the two fundamental ways in which sequential data can be stored. There are advantages and disadvantages to both:

  • Arrays store elements continuously in memory and support indexed access to the items they contain, but suffer from a fixed size.

  • Linked lists don't have the advantages of their items being stored continuously in memory or supporting indexed access, but the do support dynamic sizing (i.e., we can create and insert additional nodes as needed). Related to this, they also have extremely efficient means for inserting or removing elements. These advantages come at a cost, however. Linked lists incur additional memory overhead due to the need to store so many references.

Building and Traversing Linked Lists

To build a linked list, we start with a link (i.e., "reference to a node") that is null. This node is often called first, root, or head. Then, we create a node for each item we need to store, set the item field to the desired value, and then set the next field to the net node. The following gives an example of this process, storing strings "one", "two" and "three":

Node first = new Node();   //create first node
first.item = "one";

Node second = new Node();  //create second node
second.item = "two";
first.next = second;

Node third = new Node();   // create third node
third.item = "three";
second.next = third;

If we should need to process the elements of a list in some way -- for example, suppose we need to print the list elements -- we can traverse the list with a loop not unlike the following:

for (Node n = first; n != null; n = n.next) {
   // process n.item
}
Notice how similar this is to how one processes the elements of an array:
for (int i = 0; i < a.length; i++) {
   // process a[i]
}

Some efficiencies can be added by not only maintaining a reference to the first node of the list, but also by maintaining a reference to the last node of the list. This comes at a cost, however, in that all of the methods that change the list in any way must now check whether this additional reference needs to be modified -- and make these modifications, as necessary.

To see how some additional methods can be implemented with the addition of a reference to the last node of the list, see Linked List (Double Ended)