Create a Linked List

Account Required

This lesson is available if you sign in.
If you don't have an account, you can sign up for free.

Create a Linked List

Sign in to access this content

You must sign in to access this content.
If you don't have an account you can sign up for free!

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

00:02 interview question as old as time.

00:04 It was a part of my first coding interview 20 years ago,

00:07 and it was a part of a coding interview

00:09 that I witnessed in 2021.

00:11 So in this session, I will demonstrate

00:12 how you can create your link list data structure on the fly

00:15 during a coding interview without having

00:16 to memorize everything by using a few key tricks.

00:20 So let's jump in and have a look.

00:25 Here is the basic concept of a linked list.

00:28 It is a list of nodes where each node links

00:31 to the next one using its next member.

00:33 Each node also corresponds to a value that we want to store,

00:36 which the node stores in the value member.

00:39 So here's the first trick.

00:41 Before we start thinking about the link list,

00:43 we should think about the link list node.

00:45 It can be represented as a generic type that takes a value

00:48 of type T and then has a next member pointing

00:51 to the next link list node.

00:53 And if there is no next node, it'll point to now.

00:57 Now once you have an understanding of the link list node,

00:59 the link list class is simply a class

01:01 that contains a pointer to the first link list node,

01:04 which we store in a member called head.

01:06 Now when starting off, we don't have any values and

01:09 therefore we don't have any nodes and

01:10 therefore head is pointing to now.

01:13 Now technically speaking,

01:14 this is actually a complete implementation of Lin List,

01:17 however, it leaves the burden

01:18 of maintaining the various next pointers on the consumer

01:21 of this particular link list class.

01:23 Now, the first method that someone will ask you

01:25 to support within your link list would be one

01:27 to add additional values.

01:29 Now, new values should go at the end of the link list

01:32 and we could go from head do next, next,

01:35 next till we arrive at the tail.

01:37 However, here's another trick.

01:39 We can store the tail upfront as well.

01:41 And again, of course initialize it to now.

01:43 This allows us to add new members in constant time

01:46 as we only need to update tail.

01:48 Next. Now talking about tricks.

01:51 Whenever you are going to be creating new methods within

01:53 this class, make sure that the invariant,

01:55 that the head points to the first member

01:57 and the tail points to the last member continues

02:00 to hold true after that method is complete.

02:03 So here's our ad method that manages to add items

02:06 to a link list in constant time.

02:08 It takes an input value of type T,

02:10 and the first thing that we do is we wrap it up

02:12 in a link list node.

02:14 Next, we maintain the inva.

02:16 That head should always point to the first node.

02:18 So if we don't have any nodes right now,

02:20 then we initialize head.

02:21 Now, if we already have a tail, then we should update.

02:24 Its next to point to this particular node.

02:26 And finally this new node is going to be our new tail.

02:30 And that's it for this constant time implementation of add.

02:33 And now when in doubt, simply go through the in variance

02:35 that you want to be true, which is head should be the first

02:37 tail should be the last, and each item should point

02:40 to the next using its next member.

02:42 Now, another key method of a brother necklace

02:44 classes is the DQ method.

02:46 It offers a first in first out removal

02:48 of values in constant time.

02:50 Fundamentally, we return the first value that got added

02:53 to the head and then update our head

02:55 to point to the next value.

02:56 Now in code, if we don't have a head

02:58 that implies we don't have any values

03:00 and we simply return now,

03:02 otherwise we capture the value from the head,

03:05 but don't return it just yet.

03:06 We have a few pointers to update.

03:09 The new head is going to be the head next.

03:12 And if this means that the head is now pointing to null,

03:14 implying that the list is completely empty,

03:16 then we should update the tail to point to null as well.

03:20 And finally, we return the value that we captured.

03:23 Now this is a fairly sufficient implementation

03:25 of the link list data structure,

03:26 but sometimes you just want to look

03:28 through the values without having

03:29 to remove them AKA DQ them.

03:32 So therefore, we have this function called values which

03:34 returns a JavaScript iterator over the

03:37 values of the link list.

03:39 The implementation is pretty simple.

03:40 We start at the head and store it

03:42 in a variable called current.

03:43 And as long as the current points to a valid node

03:46 and not now we yield current value.

03:48 And then in the next iteration, update current

03:51 to be current next and repeat the while loop.

03:54 Implementing your own link list opens up a whole avenue

03:57 of other programming interview questions

03:59 and we will look at them in future lessons.

04:01 But for now, let's just look at a simple example

04:03 of using our link list in action

04:06 to create a link list for numbers.

04:08 We invoke our class constructor passing in the generic

04:10 argument for number next.

04:12 As an example, we take an array of numbers

04:15 and then for each of them bite them to the list add method.

04:18 Finally, to iterate over the values in the list,

04:21 we use the list of values method

04:22 and use it with a JavaScript four

04:24 of loop logging out each item.

04:27 And of course, if you run this code, it'll work exactly

04:29 as you would expect logging out 1, 3, 9, 12.