Linked Lists, revisited
Tags: algorithms, datastructures
Published: 2020-05-26 00:00:00

---
title: "Linked Lists, revisited"
date: "2020-05-26T00:00:00.000Z"
tags: ["algorithms", "datastructures"]
---

In a [previous post](https://dereklawless.ie/linked-lists/) 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](https://dereklawless.ie/7869e3f864ebcc952323290ef545afbd/singly-linked-list.svg)

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](https://en.wikipedia.org/wiki/Doubly_linked_list) 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](https://dereklawless.ie/0b089dcab6ba82ba9d95d8ea9f7f6414/doubly-linked-list.svg)

## 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`:

~~~typescript
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
// 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;
~~~

[The above code is available on Github](https://github.com/dereklawless/algorithms-and-data-structures-katas/tree/master/src/data-structures/linked-lists)