Problem

Create a data structure that maintains the following linked list of objects:

// node { value, next } -> node { value, next } -> null

/**
 * Linked list node
 */
export type LinkedListNode<T> = {
  value: T;
  next: LinkedListNode<T> | null;
}

Solution

/**
 * Linked list node
 */
export type LinkedListNode<T> = {
  value: T;
  next: LinkedListNode<T> | null;
}

/**
 * Linked list for items of type T
 */
export class LinkedList<T> {
  head: LinkedListNode<T> | null = null;
  tail: LinkedListNode<T> | null = null;

  /**
   * Adds an item in O(1)
   **/
  add(value: T) {
    const node: LinkedListNode<T> = {
      value,
      next: null,
    };
    if (!this.head) {
      this.head = node;
    }
    if (this.tail) {
      this.tail.next = node;
    }
    this.tail = node;
  }

  /**
   * FIFO removal in O(1)
   */
  dequeue(): T | null {
    if (!this.head) return null;
    const value = this.head.value;
    this.head = this.head.next;
    if (!this.head) {
      this.tail = null;
    }
    return value;
  }

  /**
   * Returns an iterator over the values
   */
  *values() {
    let current = this.head;
    while (current) {
      yield current.value;
      current = current.next;
    }
  }
}

Transcript

00:00

Creating your own Lin List data structure is a coding interview question as old as time. It was a part of my first coding interview 20 years ago, and it was a part of a coding interview that I witnessed in 2021. So in this session, I will demonstrate how you can create your link list data structure on the fly during a coding interview without having to memorize everything by using a few key tricks. So let's jump in and have a look. Here is the basic concept of a linked list. It is a list of nodes where each node links to the next one using its next member.

00:33

Each node also corresponds to a value that we want to store, which the node stores in the value member. So here's the first trick. Before we start thinking about the link list, we should think about the link list node. It can be represented as a generic type that takes a value of type T and then has a next member pointing to the next link list node. And if there is no next node, it'll point to now. Now once you have an understanding of the link list node, the link list class is simply a class that contains a pointer to the first link list node, which we store in a member called head.

01:06

Now when starting off, we don't have any values and therefore we don't have any nodes and therefore head is pointing to now. Now technically speaking, this is actually a complete implementation of Lin List, however, it leaves the burden of maintaining the various next pointers on the consumer of this particular link list class. Now, the first method that someone will ask you to support within your link list would be one to add additional values. Now, new values should go at the end of the link list and we could go from head do next, next, next till we arrive at the tail. However, here's another trick.

01:39

We can store the tail upfront as well. And again, of course initialize it to now. This allows us to add new members in constant time as we only need to update tail. Next. Now talking about tricks. Whenever you are going to be creating new methods within this class, make sure that the invariant, that the head points to the first member and the tail points to the last member continues to hold true after that method is complete. So here's our ad method that manages to add items to a link list in constant time. It takes an input value of type T, and the first thing that we do is we wrap it up

02:12

in a link list node. Next, we maintain the inva. That head should always point to the first node. So if we don't have any nodes right now, then we initialize head. Now, if we already have a tail, then we should update. Its next to point to this particular node. And finally this new node is going to be our new tail. And that's it for this constant time implementation of add. And now when in doubt, simply go through the in variance that you want to be true, which is head should be the first tail should be the last, and each item should point to the next using its next member. Now, another key method of a brother necklace

02:44

classes is the DQ method. It offers a first in first out removal of values in constant time. Fundamentally, we return the first value that got added to the head and then update our head to point to the next value. Now in code, if we don't have a head that implies we don't have any values and we simply return now, otherwise we capture the value from the head, but don't return it just yet. We have a few pointers to update. The new head is going to be the head next. And if this means that the head is now pointing to null, implying that the list is completely empty,

03:16

then we should update the tail to point to null as well. And finally, we return the value that we captured. Now this is a fairly sufficient implementation of the link list data structure, but sometimes you just want to look through the values without having to remove them AKA DQ them. So therefore, we have this function called values which returns a JavaScript iterator over the values of the link list. The implementation is pretty simple. We start at the head and store it in a variable called current. And as long as the current points to a valid node and not now we yield current value.

03:48

And then in the next iteration, update current to be current next and repeat the while loop. Implementing your own link list opens up a whole avenue of other programming interview questions and we will look at them in future lessons. But for now, let's just look at a simple example of using our link list in action to create a link list for numbers. We invoke our class constructor passing in the generic argument for number next. As an example, we take an array of numbers and then for each of them bite them to the list add method. Finally, to iterate over the values in the list,

04:21

we use the list of values method and use it with a JavaScript four of loop logging out each item. And of course, if you run this code, it'll work exactly as you would expect logging out 1, 3, 9, 12.

Account Required

Coding Interview Lessons

Create a Linked List

Sign in to access this content

Problem

Solution

Transcript

Coding Interview