Linked lists. The interview topic every software developer will be quizzed on at some point in their career.

Historically, this was perhaps because linked lists conveyed knowledge of pointers and memory allocation and usage in languages like C on the part of the interviewee. Available memory was also at a premium on the constrained systems of the past and efficient use of resources was not only desirable, but frequently critical.

While many of us work with higher-level languages such as Java and C# (managed runtimes) or JavaScript (intepreted), knowledge of data structures for efficiently storing and retrieving data in memory is still entirely useful to possess.

What about arrays?

Consider the main characteristics of arrays:

• Allocated a contiguous block of memory
• Cannot be resized^*
• Accessing an array element is Θ(1)
• Insertion or removal of array elements is Θ(n)

Strings are perhaps the most common example of fixed size arrays in use (this is why strings are considered immutable).

* While many languages provide dynamic arrays, these are constructs that wrap arrays and allow resizing by allocating a new contiguous block of memory behind the scenes and copying the original array contents across.

Linked lists

Linked lists differ from arrays in that they can utilise non-contiguous blocks of memory, with each data element (or ‘node’) pointing to the next in the list. Characteristics include:

• Memory allocation can be non-contiguous
• Can be easily resized, there is no copy penalty
• Accessing a node is Θ(n)
• Insertion or removal of nodes is Θ(1)

While accessing a node is Θ(n) as the list must be traversed, insertion and removal are Θ(1). Given it is frequently impossible to know how the ‘correct’ amount of memory to reserve for data in advance, linked lists offer greater efficiency in terms of memory (re)allocation.

🔔 Remember, use the data structure that is more appropriate for your circumstance.

An implementation of a singly linked list

A singly linked list allows traversal of nodes in one direction, and can be visualised as follows:

First, define a class to encapsulate a node. Here, our LinkedListNode can hold a value of type T:

// TypeScript
export class LinkedListNode<T> {
	public next: LinkedListNode<T>;

	public constructor(public readonly value: T) {}
}

export default LinkedListNode;

The next property is the mechanism we can use to link one node to another.

Next, define a LinkedList<T> class with methods for manipulating and traversing the list:

• add - adds a node to the list
• addFirst - adds a node to the beginning of the list
• addLast - adds a node to the end of the list
• interator - interates the list (implemented here as a JavaScript iterator for extra interview points)
• removeAt - removes the node at the specified index

// TypeScript
import { LinkedListNode } from "./linked-list-node";

export class SinglyLinkedList<T> {
	public head: LinkedListNode<T> = null;
	public tail: LinkedListNode<T> = null;

	public constructor() {
	}

	public add(value: T) {
		this.addLast(value);
	}

	public addFirst(value: T): void {
		const node = new LinkedListNode(value);

		const originalHeadNode = this.head;
		this.head = node;

		// Insert the rest of the list behind the head.
		this.head.next = originalHeadNode;

		if (!this.tail) {
			// There is one node in the list, set the tail to the head.
			this.tail = this.head;
		}
	}

	public addLast(value: T): void {
		const node = new LinkedListNode(value);

		if (!this.head) {
			this.head = node;
		}
		if (this.tail) {
			this.tail.next = node;
		}
		// Set the new tail.
		this.tail = node;
	}

	public *iterator() {
		let node = this.head;
		while (node) {
			yield node.value;
			node = node.next;
		}
	}

	public removeAt(index: number): void {
		let previous: LinkedListNode<T> = null;
		let node = this.head;
		let i = 0;

		while (node && i++ < index) {
			previous = node;
			node = node.next;
		}

		// Bounds checking.
		if (index >= i) { return; }

		if (!previous) {
			this.head = node.next;
		} else {
			previous.next = node.next;
		}
	}
}

export default SinglyLinkedList;

Code on Github