Introduction to Linked Lists w/ ES6

#javascript #interview

I've spent the past month or so working through coding challenges on sites like leetcode and codewars and have noticed that problems involving Linked Lists are quite popular. In fact, 6 of the top 25 most popular interview questions from leetcode involve link lists in some form. In this post, we will cover the basics of singly and doubly linked lists, and look at a simple implementation utilizing the popular Class keyword in Javascript ES6.

What is a Linked List?

A linked list is a linear data structure where each piece of data, referred to as a node, also contains a reference to the location of another node in memory. In plain english, each element of the list knows the location of the next. Linked lists are more common than you might think: music apps incorporate linked lists in song playlists, sites like ticketmaster use them to keep track of a virtual line of customers (ever seen the "you have 5 minutes remaining to complete your purchase"?).

Link lists come in two forms -- Singly and Doubly-linked lists. Let's look at a visual and code example of each:

Singly-linked-list

The beginning of the list is referred to as the head. Each subsequent node keeps a reference only to the location of the next. The node at the end of the list is called the tail. It does not contain any references to any other node.

ES6 allows us to use the class keyword to construct a basic singly-linked-list.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

We create our list by executing const SLL = new SinglyLinkedList() which creates a javascript object that has a head, tail and optional length property. In order to create the nodes, it is common to write another constructor function:

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

In order to add values to our linked list, we can add an instance method to our SinglyLinkedList class. Let's create an unshift method, which will add a node to the beginning of the list:

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  unshift(val) {
    const node = new Node(val)
    //if no head
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head = node;
    }
    this.length++;
    return this;
  }
}

Notice that in order to add a node to the beginning of our list, we first must create the node by invoking new Node(), passing in a value. This creates an object which inherits from our Node class. We must then make sure that we set the head and the tail to our new node if the node being created is the first in our list. If it is not the first, we only need to update the head, pointing the new node's next property to that of the old head. Last, we increment our count property to keep track of the total number of nodes in our list and optionally return are update list (represented by this). Unlike javascript arrays, adding to the front of our linked list takes constant (O(1)) time thus demonstrating one of the main benefits of using a linked list when adding to the back of line is desirable. Arrays, in contrast, unshift in linear (O(n)) time.

Doubly-Linked-Lists

Notice how each node in between the head and tail keep track of the nodes in the position immediately before and after. We only need to make a few modifications from our singly-linked-list code from before:

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  unshift(val) {
    const node = new Node(val)
    //if no head
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.head.previous = node;
      node.next = this.head;
      this.head = node;
    }
    this.length++;
    return this;
  }
}
//Node class constructor
class Node {
  constructor(val) {
    this.val = val;
    this.previous = null;
    this.next = null;
  }
}

Notice that when unshifting in our doubly-linked-list, we have to set the old head's previous property to point to the new node before updating the head property of the linked list to the new node. While this may seem like a bit more code, a doubly linked list can be traversed both forwards and backwards where as a singly linked list can only be traversed from the head. We use a doubly-linked-list type structure daily as we navigate back and forth in our browser with the forwards and backwards arrows.

Summing up

This post really just scratches the surface of what these data structures look like and how they function. I highly recommend checking out visualgo's animation on this any many other methods if you want to learn more. When you are ready to take on some interview questions, try out the following from leetcode's top 100 interview questions:
1.Add two numbers
2.Remove Nth Node From End of List
3.Merge two sorted lists
4.Merge k sorted lists
5.Swap nodes in pairs
6.Reverse nodes in k group