Doubly 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.

Doubly 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

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

00:02 structure and its key value proposition,

00:04 which is its super fast DQ operation.

00:07 In this lesson, we will look at a key limitation

00:09 of the link list data structure along with

00:11 how we can solve it by going w linked.

00:14 So let's go. Here's the quick recap.

00:17 Shown on screen is the DQ operation

00:20 of the link list TETA structure.

00:22 We can easily do a first in first out

00:24 removal in constant time.

00:26 This is because we can get the first added value using head

00:29 dot value and then

00:30 because we are going to be D Qing it,

00:32 we will update the head to the next using head do next.

00:36 Beyond that, there's a simple slight maintenance

00:39 of the invariant that when we run out of items

00:41 that is head becomes null,

00:43 then tail should also be set to null.

00:45 Similar to the DQ operation, which is first

00:48 and first out, we could also consider adding a last

00:51 and first out operation,

00:52 which is also commonly called pop in.

00:54 The body of the function will be very similar.

00:57 We have access to the tail of the link list

00:59 so we can grab the last added value from this to tail value.

01:03 And now after this value will be removed, we will need

01:06 to update the tail to be the second last value

01:08 that was added, which we should be able to grab from tail

01:12 or previous, but we are not storing previous

01:14 because this is a single link list.

01:17 Here's a quick comment explaining

01:19 what our current node structure looks like.

01:21 Each node has a value

01:23 and a next member pointing to the next node in the chain.

01:26 This means we can easily go in the forward direction

01:29 with node next, next,

01:30 but there is no way to quickly turn back with node previous.

01:35 Now hopefully the solution to the problem is pretty obvious.

01:37 In addition to storing next references like the single link

01:40 list, the W link list also stores reference

01:43 to the previous element in a dot prev member.

01:46 And with this people have the W link list data structure,

01:48 which is capable of doing first in first out removal in OF

01:52 one using DQ as well as last

01:54 and first of removal in OF one using pop.

01:57 Now you might recall that in the link list data structure,

02:00 there are essentially two things, the link list node

02:02 and the link list class.

02:04 The first thing that we do is to modify the link list node

02:07 to be the double link list node.

02:09 And then just like the next member,

02:11 we will also be persisting the prev member.

02:13 And beyond the name difference, the data type for the next

02:16 and the prev members is exactly the same.

02:18 Next we update the link, this class

02:20 to be called the W link list.

02:23 Now let's start modifying the methods of the W link list so

02:25 that the next and the prev members are correctly maintained.

02:29 First up, the ad method.

02:31 When we create a new node, we will have

02:33 to specify a previous member as well,

02:34 just like we specify the next member

02:36 and we will set it to now.

02:38 And if our link list already has a tail,

02:41 then this new node is going

02:42 to have its previous member pointing to that tail,

02:45 and that's the extent of the changes we

02:47 need for the add method.

02:49 Next, let's jump into the DQ method.

02:52 And again, the changes over here are going to be minimal

02:55 When we remove the head, we have a new head, but this head

02:58 Is going to point to the head that we just removed.

03:01 That is the head of prev is going to point to that,

03:03 so we have to set that to now, and that's it.

03:07 The original methods are now modified

03:09 and we can continue our journey on the method

03:11 that we actually wanted to add, which was pop.

03:13 Now that we have the next and the prev members, the error

03:16 that we had previously on this ate prev has gone away.

03:20 And in terms of function implementation, the DQ

03:22 and the POP methods are very similar.

03:24 We could essentially copy the DQ method

03:26 and paste it into pop

03:27 and replace all instances of head with tail of tail,

03:31 with head of next, with prev and of prev with next,

03:34 and we'd be done, but the code is pretty simple anyways.

03:38 If you don't have a tail, we immediately return now,

03:41 then we grab the value that we have

03:43 to return from tail value

03:45 and this is what we will eventually return.

03:48 Beyond that, there's a slight data structure maintenance.

03:50 We update the tail to be the second last item,

03:53 and if this means that we don't have a tail anymore,

03:55 then we should also set head to Now.

03:57 Finally, if we do have a new tail,

03:59 then we should set it next

04:01 to now essentially popping the old tail

04:04 and that's it for the pop operation.

04:06 Let's jump to the bottom and do a quick demo.

04:09 We create a new WD Ling list, add some items to it,

04:12 which are 1, 3, 6, 9, and 12 in that order.

04:15 And now if we dq the first item, we should get one,

04:18 and if we pop the last item, we should get 12.

04:21 And the remaining items in the link list should be 3, 6, 9.

04:25 And of course, if we execute it,

04:27 it'll work exactly as expected.

04:31 Now, just like we mentioned in the link list lesson,

04:33 you don't actually have to memorize this code

04:35 and you can instead focus on maintaining

04:38 a F key In variance.

04:39 The head and the tail need to be the first

04:41 and the last nodes,

04:42 and they both need to be set

04:43 to null when there are no nodes, the next

04:46 and the previous members need to point to vet elements,

04:49 and with that you should be able to code it up

04:51 during a coding interview.