Classic Linked List

Pro Members Only

This lesson is available if you have an active subscription.

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

If you already have a subscription, you can sign in.

Classic Linked List

Subscription Required

You must have an active subscription to access this content.
If you already have a subscription, you can sign in.

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

00:02 how you can create a single link list in which you maintain

00:05 a reference to the tail load, allowing you to add new items

00:07 to the list in constant time.

00:09 This is how it is done in most runtime libraries,

00:12 for example, for Java and C.

00:14 However, just in case your interviewer asks you

00:16 to implement it without maintaining a reference

00:18 to the tail load, you can do that

00:20 and we will look at that in this lesson

00:22 and demonstrate its impact on the ad method.

00:25 So let's jump right

00:25 in Here.

00:30 We have the link list data structure

00:32 that we created in the previous lesson.

00:33 Fundamentally, we have the type defined

00:35 for the link list node,

00:37 and the entire responsibility

00:38 of the link list data structure is

00:40 to maintain the head node and the tail node.

00:43 Now the lazy implementation

00:44 of the link list data structure works without the tail node.

00:47 So let's just go ahead and delete that and see its impact.

00:50 Now the first impact that we see is within the ad method.

00:53 At any point when we were assigning to the tail node,

00:55 we were essentially ensuring the tail continues to point

00:58 to the last node in the link list,

01:00 and we can simply delete that

01:01 as we're not going to maintain it anymore.

01:04 Now, the other usage of the tail member over here is

01:06 to allow us to add the new node quickly

01:09 to the end of the link list.

01:11 Since we no longer have a reference to the tail,

01:14 we essentially have to start our search from head

01:17 and go from next, next to next.

01:19 Eventually till do next is null,

01:21 and then we have found our tail

01:23 and we can add the new node after it.

01:25 And this is the key reason why we were maintaining the tail.

01:27 So we don't have to do this search,

01:29 but now that the tail is gone, the runtime

01:31 of this function goes from O of one, which is constant time

01:35 to a full search, which is linear time or OFN.

01:39 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

01:44 that when we run out of items

01:45 because of D Qing, the last value, we also want

01:48 to set tail to now.

01:50 And since we are no longer maintaining the tail,

01:52 we can simply delete this line as well.

01:55 As you can see, there is not much code complexity difference

01:57 between maintaining or computing the tail.

02:00 However, there is a performance difference,

02:01 which is why I prefer the wit tail version.