Linked Lists, revisited

In a previous post I discussed the linked list data structure, how linked lists differ from arrays, and provided a sample implementation of singly linked list.

Recall that a singly linked list allows nodes to be traversed in one direction:

Singly linked list

What if we want to be able to traverse the list in either direction? Presented with that requirement we can use a doubly linked list.

Doubly linked lists are a variant of linked lists that enable node traversal in either direction. While they do use more memory than singly linked listed (two pointers per node vs. one), they allow for easier node insertion and removal.

A doubly linked list can be visualised at follows:

Doubly linked list

An implementation of a doubly linked list

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

export class LinkedListNode<T> {
	public next: LinkedListNode<T>;
	public previous: LinkedListNode<T>;

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

export default LinkedListNode;

Note the addition of a previous property — this will be used to link a node to the previous node in the list (or be assigned null if the current node is the ‘head’).

The LinkedList<T> class specification remains the same:

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 DoublyLinkedList<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;

		// Link the nodes.
		this.head.next = originalHeadNode;
		originalHeadNode.previous = this.head;

		if (!this.tail) {
			// There is one node in the list, set the tail node 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) {
			// Link the nodes.
			this.tail.next = node;
			node.previous = this.tail;
		}
		// 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 node = this.head;
		let i = 0;

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

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

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

export default DoublyLinkedList;

Code on Github

26th May 2020 ・ 3 min readAlgorithms and Data Structures

An implementation of a doubly linked list