Singly Linked Lists

Background

During my time in college, I learned about many different data structures and algorithms through the core coursework. We additionally only worked in the C programming language. One limitation of C is that arrays are not resizable. That is, to declare an array, you either must either:

Know it’s size at compile time:

int arr[3];
// or
int arr[] = {1, 2, 3};

or dynamically allocate heap memory:

int num_elements = 4;
int *array = malloc(sizeof(int) * num_elements);

Each approach comes with trade-offs. Static arrays have a fixed size at compile time, are limited by the stack size, and cannot be returned from functions. Dynamic arrays must be manually freed and cannot be resized once allocated.

These limitations lead to the first non-trivial data structure I was introduced to: the Singly Linked List.

Singly Linked Lists

A singly linked list is a resizable collection of nodes. The list itself is just a pointer to the first node in the collection. Each node in the collection holds a value and a pointer to the next node, linking the whole thing together.

Key Characteristics:

  • Supports reading, inserting at, or deleting from the start of the list in O(1) time.
  • Reading, inserting at, or deleting from any other position takes O(n) time, where n is the number of elements.
  • Finding a specific value (e.g., “find the first 5”) also takes O(n) time, where n is the number of elements.
  • Singly linked lists are completely resizable — they grow or shrink as needed.

Design

Let’s start off by understanding how operations work from a high level. Say we have the following list:

Linked list of Foo -> Bar -> Baz

This can be though of as being equivalent to the array ["Foo", "Bar", "Baz"]. The first node, “Foo”, has a pointer to the next node in the collection, “Bar”. The same goes for “Bar” to “Baz”. The final node, “Baz” has a pointer to NULL, indicating that it is the last node in the collection.

Iterating/Reading

This intuitively tells us how we will iterate through the list, going to the first node, to the second, and so on. Additionally, this shows that O(1) indexing is impossible, as accessing an index x can take up to n iterations, n being the size of the collection.

Iterating from Foo to Bar to Baz

Inserting

Next, let’s look at inserting a new value into the collection. Say, for example, we want to insert a value “Qux” between “Bar” and “Baz”.

First, let’s create a Node with this new value.

Iterating from Foo to Bar to Baz

Next, lets have this new node point to “Baz”.

Iterating from Foo to Bar to Baz

Finally, lets have “Bar” point to our new node.

Iterating from Foo to Bar to Baz

(Simplifying)

Iterating from Foo to Bar to Baz

And we’ve done it! We have successfully inserted a new value into our list.

Removing

Now, lets look at the last operation: removing a value. Say we have our original collection, and we would like to remove “Bar” from the list. To do this, we will simply point “Foo” to “Baz” (and ensure to free up the memory allocated for “Bar”).

Linked list of Foo -> Bar -> Baz

For the C implementation of Singly Linked Lists, check out this repo.

While Singly Linked Lists are memory efficient and convenient, they have several drawbacks and aren’t commonly found in real-world codebases.

  • O(n) collection indexing is too slow in most scenarios.
  • Iterating in reverse order isn’t trivial.
  • Reading from, inserting at, and deleting the tail takes O(n) time.
  • Nodes are allocated on the heap, which is significantly slower than stack memory.

If we could solve the tail problem (and simultaneously solve the reverse-iteration problem), this could serve as an efficient Queue. Next time we’ll look at Doubly Linked Lists which do exactly this.