Problem

Create a linked list that allows easy traversal in both forward and back directions.

Hint: The nodes will look like this:

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

Solution

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

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

  /**
   * Adds an item in O(1)
   **/
  add(value: T) {
    const node: DoublyLinkedListNode<T> = {
      prev: null,
      value,
      next: null,
    };
    if (!this.head) {
      this.head = node;
    }
    if (this.tail) {
      this.tail.next = node;
      node.prev = this.tail;
    }
    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;
    } else {
      this.head.prev = null;
    }
    return value;
  }

  /**
   * LIFO removal in O(1)
   */
  pop(): T | null {
    if (!this.tail) return null;
    const value = this.tail.value;
    this.tail = this.tail.prev;
    if (!this.tail) {
      this.head = null;
    } else {
      this.tail.next = 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

In our last lesson we looked at the link list data structure and its key value proposition, which is its super fast DQ operation. In this lesson, we will look at a key limitation of the link list data structure along with how we can solve it by going w linked. So let's go. Here's the quick recap. Shown on screen is the DQ operation of the link list TETA structure. We can easily do a first in first out removal in constant time. This is because we can get the first added value using head dot value and then because we are going to be D Qing it,

00:32

we will update the head to the next using head do next. Beyond that, there's a simple slight maintenance of the invariant that when we run out of items that is head becomes null, then tail should also be set to null. Similar to the DQ operation, which is first and first out, we could also consider adding a last and first out operation, which is also commonly called pop in. The body of the function will be very similar. We have access to the tail of the link list so we can grab the last added value from this to tail value. And now after this value will be removed, we will need

01:06

to update the tail to be the second last value that was added, which we should be able to grab from tail or previous, but we are not storing previous because this is a single link list. Here's a quick comment explaining what our current node structure looks like. Each node has a value and a next member pointing to the next node in the chain. This means we can easily go in the forward direction with node next, next, but there is no way to quickly turn back with node previous. Now hopefully the solution to the problem is pretty obvious. In addition to storing next references like the single link

01:40

list, the W link list also stores reference to the previous element in a dot prev member. And with this people have the W link list data structure, which is capable of doing first in first out removal in OF one using DQ as well as last and first of removal in OF one using pop. Now you might recall that in the link list data structure, there are essentially two things, the link list node and the link list class. The first thing that we do is to modify the link list node to be the double link list node. And then just like the next member, we will also be persisting the prev member.

02:13

And beyond the name difference, the data type for the next and the prev members is exactly the same. Next we update the link, this class to be called the W link list. Now let's start modifying the methods of the W link list so that the next and the prev members are correctly maintained. First up, the ad method. When we create a new node, we will have to specify a previous member as well, just like we specify the next member and we will set it to now. And if our link list already has a tail, then this new node is going to have its previous member pointing to that tail, and that's the extent of the changes we

02:47

need for the add method. Next, let's jump into the DQ method. And again, the changes over here are going to be minimal When we remove the head, we have a new head, but this head Is going to point to the head that we just removed. That is the head of prev is going to point to that, so we have to set that to now, and that's it. The original methods are now modified and we can continue our journey on the method that we actually wanted to add, which was pop. Now that we have the next and the prev members, the error that we had previously on this ate prev has gone away. And in terms of function implementation, the DQ

03:22

and the POP methods are very similar. We could essentially copy the DQ method and paste it into pop and replace all instances of head with tail of tail, with head of next, with prev and of prev with next, and we'd be done, but the code is pretty simple anyways. If you don't have a tail, we immediately return now, then we grab the value that we have to return from tail value and this is what we will eventually return. Beyond that, there's a slight data structure maintenance. We update the tail to be the second last item, and if this means that we don't have a tail anymore,

03:55

then we should also set head to Now. Finally, if we do have a new tail, then we should set it next to now essentially popping the old tail and that's it for the pop operation. Let's jump to the bottom and do a quick demo. We create a new WD Ling list, add some items to it, which are 1, 3, 6, 9, and 12 in that order. And now if we dq the first item, we should get one, and if we pop the last item, we should get 12. And the remaining items in the link list should be 3, 6, 9. And of course, if we execute it,

04:27

it'll work exactly as expected. Now, just like we mentioned in the link list lesson, you don't actually have to memorize this code and you can instead focus on maintaining a F key In variance. The head and the tail need to be the first and the last nodes, and they both need to be set to null when there are no nodes, the next and the previous members need to point to vet elements, and with that you should be able to code it up during a coding interview.

Pro Members Only

This lesson is available if you have an active subscription.

Alternatively, some member might be able to gift it to you.

Coding Interview Lessons

Doubly Linked List

Subscription Required

Problem

Solution

Transcript

Coding Interview