Typescript Data Structures: Linked List
Tags: typescript, beginners, tutorial, javascript
Published: 2020-07-24 15:14:02

In today's episode of Typescript 101, we continue talking about data structures and their implementation in Typescript. Our today's patient is the linked list. We will dive into creating generic, reusable linked lists and touch the topic of recursion in JS. Welcome and let's hack!

### Table of content
1. [What is a linked list?](#whatIsALinkedList)
2. [Nodes](#nodes)
3. [Linked list's methods](#methods)
4. [Full implementation](#implementation)

### <a name="whatIsALinkedList"></a> What is a linked list?
According to the [Wikipedia](https://en.wikipedia.org/wiki/Linked_list):
*In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.*

There are two main types of linked lists:
1. **Singly linked list**: a list where elements have only a reference to next element
2. **Doubly linked list**: a list where elements are linked to both next and previous elements

Today we will focus on the doubly linked list implementation.

### <a name="nodes"></a> Nodes
Every item of the linked list is a node. Let's create a `Node` class first.
```jsx
class Node<T> {
  public next: Node<T> | null = null;
  public prev: Node<T> | null = null;
  constructor(public data: T) {}
}
```
Since we are working on the *doubly linked list* our `Node` has `next` and `prev` fields, that point to another node or `null`. Also a `Node` contains our data, which has a generic type `T`. 
### <a name="methods"></a> Linked list's methods
Here is how the final version of the linked list will look like.
```jsx
interface ILinkedList<T> {
  insertInBegin(data: T): Node<T>;
  insertAtEnd(data: T): Node<T>;
  deleteNode(node: Node<T>): void;
  traverse(): T[];
  size(): number;
  search(comparator: (data: T) => boolean): Node<T> | null;
}
```
#### Insert
We will start by implementing insert functionality. There are multiple ways to insert data to the linked list. One might insert data after or before a certain node or based on the index, but in this example, we will focus on more generic cases - inserting nodes in the beginning or at the end of the list.
###### insertInBegin
```jsx
class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public insertInBegin(data: T): Node<T> {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      this.head.prev = node;
      node.next = this.head;
      this.head = node;
    }
    return node;
  }
}
```
Here we are handling two scenarios:
1. The list is empty - in that case, the newly added element becomes the head of the list.
2. The list is not empty - in that case newly added element becomes the head of the list and we update the links of the former head.
```text
1. list Before insertion:
A <-> B <-> ...
2. list after insertion:
New_Node <-> A <-> B <-> ...
```
###### insertAtEnd
```jsx
class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public insertAtEnd(data: T): Node<T> {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      const getLast = (node: Node<T>): Node<T> => {
        return node.next ? getLast(node.next) : node;
      };

      const lastNode = getLast(this.head);
      node.prev = lastNode;
      lastNode.next = node;
    }
    return node;
  }
}
```
Inserting, in the end, is a bit trickier, because we need to find the last node first, so let's look closer at what's happening. Similarly to the previous method, we have two scenarios:
1. The list is empty - in that case, the newly added element becomes the head of the list.
2. The list is not empty - we search for the last node and set it's `next` reference to the newly added element.

```text
A <-> B <-> New_Node
```
To find the last node we are using a recursive function, which traverses the list and return the node which does not have a reference to the `next` node:
```jsx
const getLast = (node: Node<T>): Node<T> => {
  return node.next ? getLast(node.next) : node;
};
```
#### Delete
Deleting a node is quite straightforward. All we need to do is updating the references for the next and previous items. If the node is the current head, we will have to shift our list.
```jsx
class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public deleteNode(node: Node<T>): void {
    if (!node.prev) {
      this.head = node.next;
    } else {
      const prevNode = node.prev;
      prevNode.next = node.next;
    }
  }
}
```
#### Traverse
`traverse` method will iterate over the linked list and return all nodes as JS Array. For this method we will also make use of a recursive function.
```jsx
class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public traverse(): T[] {
    const array: T[] = [];
    if (!this.head) {
      return array;
    }

    const addToArray = (node: Node<T>): T[] => {
      array.push(node.data);
      return node.next ? addToArray(node.next) : array;
    };
    return addToArray(this.head);
  }
}
```
Recursive functions are a great substitute of `while` loops for the tasks like traversing when we don't know the size of the list before we start iterating.

#### Size

To keep track of the size, we can store a current number of nodes in a class field and update it every time a node is added or removed. However, in this example, I will simply make use of the `traverse` function and return array length:
```jsx
...
  public size(): number {
    return this.traverse().length;
  }
...
```

#### Search
When you think about the final consumer of the `LinkedList` class, she'll be probably interested in searching for the node based on some data property. To make usage of our `search` method as flexible as possible, we'll be using the *inversion of control*. The consumer will be able to pass a callback function, which would implement the required search condition:
```jsx
class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public search(comparator: (data: T) => boolean): Node<T> | null {
    const checkNext = (node: Node<T>): Node<T> | null => {
      if (comparator(node.data)) {
        return node;
      }
      return node.next ? checkNext(node.next) : null;
    };

    return this.head ? checkNext(this.head) : null;
  }
}
```

### <a name="implementation"></a> Full implementation
```jsx
class LinkedList<T> implements ILinkedList<T> {
  private head: Node<T> | null = null;

  public insertAtEnd(data: T): Node<T> {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      const getLast = (node: Node<T>): Node<T> => {
        return node.next ? getLast(node.next) : node;
      };

      const lastNode = getLast(this.head);
      node.prev = lastNode;
      lastNode.next = node;
    }
    return node;
  }

  public insertInBegin(data: T): Node<T> {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      this.head.prev = node;
      node.next = this.head;
      this.head = node;
    }
    return node;
  }

  public deleteNode(node: Node<T>): void {
    if (!node.prev) {
      this.head = node.next;
    } else {
      const prevNode = node.prev;
      prevNode.next = node.next;
    }
  }

  public search(comparator: (data: T) => boolean): Node<T> | null {
    const checkNext = (node: Node<T>): Node<T> | null => {
      if (comparator(node.data)) {
        return node;
      }
      return node.next ? checkNext(node.next) : null;
    };

    return this.head ? checkNext(this.head) : null;
  }

  public traverse(): T[] {
    const array: T[] = [];
    if (!this.head) {
      return array;
    }

    const addToArray = (node: Node<T>): T[] => {
      array.push(node.data);
      return node.next ? addToArray(node.next) : array;
    };
    return addToArray(this.head);
  }

  public size(): number {
    return this.traverse().length;
  }
}

interface Post {
  title: string;
}
const linkedList = new LinkedList<Post>();

linkedList.traverse() // [];

linkedList.insertAtEnd({ title: "Post A" });
linkedList.insertAtEnd({ title: "Post B" });
linkedList.insertInBegin({ title: "Post C" });
linkedList.insertInBegin({ title: "Post D" });

linkedList.traverse() // [{ title : "Post D" }, { title : "Post C" }, { title : "Post A" }, { title : "Post B" }];
linkedList.search(({ title }) => title === "Post A") // Node { data: { title: "Post A" }, prev: Node, next: Node};
```
### <a name="summary"></a> Summary
Today we talked linked lists, and I hope you've found it useful. If you want to learn something specific about Typescript or willing to propose the next data structure, leave a comment and let's discuss it together.

If you liked my post, please spread a word and [follow me on Twitter](https://twitter.com/gleb_irovich) 🚀 for more exciting content about web development.