Problem

Build a classic linked list data structure, that

doesn't maintain a reference to the tail
only stores the head
explain the impact on its runtime complexity

Solution

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

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

  /**
   * Adds an item in O(n)
   **/
  add(value: T) {
    const node = {
      value,
      next: null,
    };
    if (!this.head) {
      this.head = node;
    } else {
      let currentTail = this.head;
      while (currentTail.next != null) {
        currentTail = currentTail.next;
      }
      currentTail.next = node;
    }
  }

  /**
   * FIFO removal in O(1)
   */
  dequeue(): T | null {
    if (!this.head) return null;
    const value = this.head.value;
    this.head = this.head.next;
    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 how you can create a single link list in which you maintain a reference to the tail load, allowing you to add new items to the list in constant time. This is how it is done in most runtime libraries, for example, for Java and C. However, just in case your interviewer asks you to implement it without maintaining a reference to the tail load, you can do that and we will look at that in this lesson and demonstrate its impact on the ad method. So let's jump right in Here. We have the link list data structure

00:32

that we created in the previous lesson. Fundamentally, we have the type defined for the link list node, and the entire responsibility of the link list data structure is to maintain the head node and the tail node. Now the lazy implementation of the link list data structure works without the tail node. So let's just go ahead and delete that and see its impact. Now the first impact that we see is within the ad method. At any point when we were assigning to the tail node, we were essentially ensuring the tail continues to point to the last node in the link list, and we can simply delete that as we're not going to maintain it anymore. Now, the other usage of the tail member over here is

01:06

to allow us to add the new node quickly to the end of the link list. Since we no longer have a reference to the tail, we essentially have to start our search from head and go from next, next to next. Eventually till do next is null, and then we have found our tail and we can add the new node after it. And this is the key reason why we were maintaining the tail. So we don't have to do this search, but now that the tail is gone, the runtime of this function goes from O of one, which is constant time to a full search, which is linear time or OFN. And now the other error that we see is on the DQ function.

01:42

And the only thing that we are maintaining over here is that when we run out of items because of D Qing, the last value, we also want to set tail to now. And since we are no longer maintaining the tail, we can simply delete this line as well. As you can see, there is not much code complexity difference between maintaining or computing the tail. However, there is a performance difference, which is why I prefer the wit tail version.

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

Classic Linked List

Subscription Required

Problem

Solution

Transcript

Coding Interview