DEV Community

Cover image for Typescript Data Structures: Linked List
Gleb Irovich
Gleb Irovich

Posted on • Updated on

Typescript Data Structures: Linked List

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?
  2. Nodes
  3. Linked list's methods
  4. Full implementation

What is a linked list?

According to the Wikipedia:
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.

Nodes

Every item of the linked list is a node. Let's create a Node class first.

class Node<T> {
  public next: Node<T> | null = null;
  public prev: Node<T> | null = null;
  constructor(public data: T) {}
}
Enter fullscreen mode Exit fullscreen mode

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.

Linked list's methods

Here is how the final version of the linked list will look like.

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;
}
Enter fullscreen mode Exit fullscreen mode

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
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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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.
1. list Before insertion:
A <-> B <-> ...
2. list after insertion:
New_Node <-> A <-> B <-> ...
Enter fullscreen mode Exit fullscreen mode
insertAtEnd
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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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.
A <-> B <-> New_Node
Enter fullscreen mode Exit fullscreen mode

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:

const getLast = (node: Node<T>): Node<T> => {
  return node.next ? getLast(node.next) : node;
};
Enter fullscreen mode Exit fullscreen mode

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.

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;
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

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.

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);
  }
}
Enter fullscreen mode Exit fullscreen mode

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:

...
  public size(): number {
    return this.traverse().length;
  }
...
Enter fullscreen mode Exit fullscreen mode

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:

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

Full implementation

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};
Enter fullscreen mode Exit fullscreen mode

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 πŸš€ for more exciting content about web development.

Top comments (21)

Collapse
 
matvs profile image
Mateusz Swiatkowski

Hi Gleb, nice and clear article :)

Could you elaborate on "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."?

I don't see what prior knowledge of the list size has to do with substituting while loop for a recursive call.

Traverse method could be easily implemented with while loop and it has an advantage of not worrying about exceeding a call stack.

public traverse(): T[] {
    const array: T[] = [];
    let currentNode = this.head;
    while(currentNode) {
        array.push(currentNode.data);
        currentNode = currentNode.next;
    }
    return array;
  }
Enter fullscreen mode Exit fullscreen mode

Also traverse method is a good candidate for using a technique called "tail recursion", but for JavaScript tail call is currently supported only by Safari/WebKit.

Collapse
 
glebirovich profile image
Gleb Irovich

Hey Mateusz, thanks for your feedback! Probably, the sentence is not very well structured. What I meant is that in the traverse example we don’t have prior knowledge of the size and therefore we cannot use for loops. However we can use a while loop or alternatively a recursive function.
It’s a great input regarding the call stack overflow πŸ‘πŸ‘πŸ‘, I definitely missed it out of sight, since I alway tend to be biased toward functional approaches.

Collapse
 
zilti_500 profile image
Daniel Ziltener

Here's the thing with double linked lists: they are just shitty vectors/"arraylists"/you-name-it. With double linked lists, you throw away all advantages you get with single linked lists, which is being able to add elements to the list at pretty much zero cost and having it be immutable on top of it, at the cost of random access being expensive.

With double linked lists, you still have the high cost of random access, but you are going to modify the list when adding elements.

It is definitely a neat idea in theory if what you want is a single linked list that is, well, linked in both directions, but other than that, I always felt a double-linked list is not something to be used in real-world scenarios (maybe except some fringe scenarios?).

And linked lists are definitely a very good example when making one's first steps in functional programming, and this blog post neatly demonstrates that. It is, I'd say, the data structure where even an object-oriented programmer will likely naturally resort to functional "patterns".

Good post, I just wanted to chime in with some considerations for real-world use.

Collapse
 
glebirovich profile image
Gleb Irovich

Hey Daniel thanks for your feedback! Actually writing those articles about data structures is a way to research on that topics. I also must admit, I don’t have any real scenarios where I would need a linked list, so I would be curious to know if you are using it in production and how.
Could you also elaborate on the idea of β€œimmutable lists” I find it very interesting, but I am not quite sure how it is supposed to work. Don’t you have to mutate at least the β€˜next’ field?

Collapse
 
zilti_500 profile image
Daniel Ziltener

So the way this immutability works in a single linked list is that when you have a list B-C-D, B points to C, and C points to D. C doesn't know about B at all, all it knows is its own value, and where C is! So when you want to "add" to the list you simply create a "cell" that contains the value of A and has "next" point to B. The original list doesn't know anything about being longer now. It is the simplest extensible immutable data structure possible.

As you can see, a major downside of this is that you can only prepend to the list, and not append. Doing the latter would mean that either the list has to be mutable and you can change the last cell to point to the new value instead of to nothing; or to copy the entire list with a different last cell; or do some "black magic" with complicated-but-fast tree structures that make it seem like you copied the entire collection without actually doing the full thing (Clojure does the latter with all its collections).

A good use case - and the only one I can think of off the top of my head - of single linked lists are lazy sequences. Many functional programming languages make use of that. To make an example from your post, the search function (often called filter in functional programming). It would return a lazy sequence and only continue to search/filter as you continue to consume the sequence. Accessing the "next" field then just triggers the next filtering step. That only really works with single-linked lists because they don't have true random access.

Thread Thread
 
glebirovich profile image
Gleb Irovich

Daniel, thanks for the detailed response! That was very insightful. Do you think one could achieve a behaviour similar to the lazy sequence by using JS generators, that yield next item from the list, when called?

Collapse
 
glebirovich profile image
Gleb Irovich

As guess you can keep track of the tail instead of the head and linking new items to prev, so that the added ones remain unchanged. Reverse linking, is it something you had in mind?

Collapse
 
prakashreddy profile image
Prakash-Reddy08

Delete method should look like this

if (!node.prev) {
            this.head = node.next;
        } else {
            const prevNode = node.prev;
            prevNode.next = node.next;
            if (node.next && node.next.prev) {
                node.next.prev = prevNode;
            }
        }
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mlynchdev profile image
mlynchdev

I think your delete method is missing some steps.

public deleteNode(node: Node<T>): void {
    if (!node.prev) {
      this.head = node.next;
// Here node.next will still point at the deleted node (doubly linked list)
// suggest node.next.prev = null or something like this.
    } else {
      const prevNode = node.prev;
      prevNode.next = node.next;
// Here node.next will still point at the deleted node (doubly linked list)
// suggest node.next.prev = node.prev    
    }
  }
Enter fullscreen mode Exit fullscreen mode
Collapse
 
cihatsaman profile image
Cihat Saman

Hi Gleb , article was clear and so useful :)
May I know how can I use the deleteNode function ? Because I can see , you did not use on end of the whole code with example. How can I call that function I mean which arguments should I use with that deleteNode(node) function? May I know what is a sample node ?
Thanks :)

Collapse
 
glebirovich profile image
Gleb Irovich • Edited

Hey Cihat! Thank you for the feedback.
deleteNode as you can see from the type definition requires reference to the node stored in the list. Here is an example of searching and deleting a particular node:

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

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

const node = linkedList.search(({ title }) => title === 'Post A');
linkedList.deleteNode(node);
console.log(linkedList.traverse()); // [{ title : "Post D" }, { title : "Post C" }, { title : "Post B" }];
Enter fullscreen mode Exit fullscreen mode
Collapse
 
cihatsaman profile image
Cihat Saman

Thanks @glebirovich for quick answer :)

Collapse
 
barzilaysapir profile image
Sapir Barzilay • Edited

Hi, great article.
I don't get it, why on insertToBegin of a double linked list,
if the list is empty you're using :
this.head = new Node(),
and on the same condition when insertAtEnd, you're using:
this.head = node.
or maybe it's just an example you can do it both ways?
Thought I got it at first but then I got a little confused, would like to clear this up!
Thanks.

Collapse
 
glebirovich profile image
Gleb Irovich

Hey Sapir,

Thanks for pointing out this method. You are right, I should have assigned node, instead of instantiating a new class in the if clause:

  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;
  }
Enter fullscreen mode Exit fullscreen mode

It's a correct way because it also ensures that we return a reference to the node, which is assigned to the head. Thanks, I updated the code!

Collapse
 
barzilaysapir profile image
Sapir Barzilay • Edited

Got it! thank you.

Collapse
 
chukwuemekaigbokwe profile image
Chukwuemeka Igbokwe

Nice article πŸ‘πŸ‘

Collapse
 
glebirovich profile image
Gleb Irovich

Thanks Alex!

Collapse
 
nsholmes profile image
NsHolmes

Hi Gleb,
Thanks for the article. I like the recursive function in the insertAtEnd. Shouldn't the recursive call to getLast(node) be getLast(node.next)? So that the next node will be checked?

Collapse
 
glebirovich profile image
Gleb Irovich

Hey! You are totally right, nice catch. I will update the code!

Collapse
 
rapdash profile image
Frederick "Fritz" Johnson

Created an account just to thank you for posting this. Fantastic stuff.

Collapse
 
glebirovich profile image
Gleb Irovich

Hey Frederick! Thank you a lot!