CMUQ 15-121 Linked Lists

1. Introduction

In a previous set of notes we looked at the ArrayList class and noticed that it solved the vast majority of our problems with standard arrays. The main strength of an ArrayList is that it grows as needed. One downside to an ArrayList, however, is the wasted space. The ArrayList typically allocates more space than is need in order to predict future growth. If you don’t use that space, it just sits empty. On modern computers, this isn’t a big deal: We have lots of memory and wasting some of it isn’t a problem. There was a time, however, when memory was more constrained and we wanted to eliminate that waste if we could.

In this set of notes we’ll introduce the linked list. A linked list is a data structure that implements our list ADT. Linked lists are one of the original data structures used to solve the dynamically growing array problem. Their simplistic, yet elegant, design also provides a programming foundation for working with other data structures (such as trees and graphs) that we’ll encounter later in the course.

2. The Linked List

A linked list is compromised of a set of nodes that each contain one item from the list as well as a pointer to the next node in the list. The last item in the list contains a pointer to null.

If we were to draw a picture of a linked list, it might look like this:

This list contains three integers: 12, 99, and 37 (in that order). There are three nodes, and each node contains exactly one of the integers as well as a reference pointing to the next node in the list. The last node points to null, represented by the X.

The beauty of the linked list is that it grows and shrinks as needed. Want to add more items? Just create more nodes and adjust the pointers appropriately. Want to remove an item? Just adjust the points to remove its node from the list.

3. Basic List Operations

3.1. Accessing a Single Item

In an array, if you want to access a specific item in the array (such as the 2nd item) then you can do so easily. All of the elements in the array are stored contiguously (meaning next to each other) in memory, so if you know the address of the start of the array you can quickly calculate the address of any item in the array. Java does this for you, in fact, when you access an array using the syntax of arr[i]. arr stores the address of the start of the array, and Java can calculate the address of the i’th item in the array. Accessing an item in an array is, therefore, \(O(1)\).

Nodes in a linked list are not stored contiguously. Instead, they could be scattered across memory. This means there is no easy way to quickly locate the i’th item in a linked list. Instead, you need to start at the beginning of the list and navigate all the nodes until you get to the node you are looking for. This is actually \(O(n)\).

3.2. Adding an Item

Adding an item to a linked list is fairly straight forward. You simply create a new node with the item you want to add, go to the place in the list you want to add it, and adjust the next pointers appropriately. The following picture illustrates this:

In this example we are adding the number 37 to a list that already contains 12 and 99. As you can see, we start by creating a new node containing 37, then we update the pointer of 12’s node to point to the new node, and we update the pointer of the new node to point to 99’s node. This adds the item to the list.

3.3. Removing an Item

Removing an item from the list is also fairly straightforward. We simply adjust the pointer of the element before the one we want to remove to point to the element after the one we want to remove. Consider this diagram illustrating this:

4. Doing This is Java

We’ll implement a linked list in class, and you can see an example of an implementation there. The goal of these notes is simply to provide you with an overview of the concept of a linked list.

5. Credits

All images are in the public domain and taken from the Wikipedia article on Linked Lists. (As of October 1, 2018).