Last summer, I was deep in a project, developing my own version of a graph store. One of the features that I had to implement was to introduce a list as an attribute of a node. It supported operations that allowed users to append and remove elements from the start and end of the list.

On the first pass of development, the list took the form of an interface for an internal array where users could query the data inside. From a functional standpoint, this was adequate. An array allowed all of these operations still while maintaining a relatively low storage profile.

However, initial benchmarks were disappointing, particularly under a stress test where we kept removing and appending elements at the beginning of the array. By the second phase of the project, the array implementation was replaced by a linked list.

But why? This task seemed to make good use of an array. Why was it replaced with another data structure?

In interviews, concepts like these are nuanced, but also critical in showcasing your knowledge in algorithm design. Typically, concepts like these are not asked as independent questions but are rather baked into many interview questions. Spotting when to use your knowledge here is key, and frankly, hard!

By the end of this course, you should be able to answer the following:

What is a Linked List?

A linked list is a linear data structure composed of nodes, where each node contains data and a reference to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations; instead, each node points to the next, allowing for dynamic memory allocation and efficient insertions and deletions.

At the heart of a linked list is the node, a construct that encapsulates both the data it holds and references to other nodes in the list (it often holds the reference of the next node). The following Python class ListNode illustrates a basic node structure:

class ListNode:
	data: any = None
	next: Node = None

Consider that you’re attending a neighborhood open house event, where each house on the tour is linked to the next by a guided path. You can only determine the next house to visit based on the address that’s written in the front lawn of the current house. In this scenario, each house represents a node in a linked list. The unique features and layout of each house corresponds to the data stored within a node, while the guided path to the next house on the tour acts as the next reference in a node.

This is, in practice, how a linked list works. As long as we know the start point, we can safely go through all the points of interest without a problem. That’s why most linked lists only need to know three things in order to work efficiently.

• The size of the linked list.
• The address to the first node (head).
• The address of the last node (tail).

Linked lists refer to the first node as the “head” node, while the last node is often referred to as the “tail” node.

Linked lists present a set of pain points that may make the concept hard to grasp at first. For example, unlike in an array where we can easily add and remove items without worrying about losing access to other elements, linked lists needs to ensure that the “links”, or references to the next node, maintain their integrity. Just like in a chain, one broken link can lead to the entire list failing.

Types of Linked Lists

Singly Linked Lists

A singly linked list consists of nodes that each contain data and a reference to the next node. This design facilitates efficient insertions and deletions at the beginning of the list, as it eliminates the need for element shifting. Each node points to the next, forming a sequential chain from the first (head) to the last (tail) node.

Doubly Linked Lists

Doubly linked lists extend the concept of singly linked lists by including an additional reference in each node that points to the previous node. This bidirectional linkage supports more complex operations, such as insertion and deletion from both ends of the list, with increased efficiency. It also allows for backward traversal, making operations like reverse traversal inherently simpler.