Back in Part 1 we got a birds-eye look at what linked lists are and why they’re necessary for creating more advanced data structures. Now we can learn how to start implementing a fully-featured doubly linked list in JavaScript.

Singly linked lists and implementations in other data structures will generally just be more barebones versions of what we’ll cover here, so this would be good to bookmark as a general reference.

## Structure

Like any other class, we can store whatever we want in each node, the only important parts are the `next`

and `prev`

pointers, which should be `null`

by default.

Likewise the only things our list needs are its `tail`

, `head`

, and `length`

. We’ll need to manually manipulate the length since, unlike arrays, it won’t be calculated for us and will be necessary for searching for items.

```
class Node {
constructor(val) {
this.val = val;
this.next = null;
this.prev = null;
};
};
class linkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
};
};
```

#### — Sorry to interrupt this program! 📺

Are you interested in learning React? If so, I highly recommend you try Wes Bos' React for Beginners or Fullstack Advanced React & GraphQL course.

Given the current situation with COVID-19, times are hard for most of us, but if you're stuck at home you can perhaps use that extra time to work on your front-end skills. Wes put all of his courses at 50% off to help out with the current challenge we're facing.

Plus, these are affiliate links, so if you purchase a course you help Alligator.io continue to exist at the same time! 🙏

## Create

Now we can start setting up all of our methods inside our `linkedList`

class. Since we don’t have any of our normal goodies like `push`

or `shift`

we’ll have to create our own versions.

### Head and Tail

Most of our operations are based more on manipulating the pointers in the surrounding nodes than on the item we want to change. To add something isn’t just shoving a new node where we want, like with an array, but changing the pointers on the items before or after to point to our new item, then manually incrementing the list’s length.

If there isn’t anything in the list, we want to set the new item as both the head and tail, since it’s the only item. To add or remove from the end of the list we’ll take the current head/tail we want to replace and set its pointer to our new item or null, change the list’s head/tail to our new node or null, then increment the length.

```
addHead(val) {
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
};
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
addTail(val) {
let newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
};
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
this.length++;
return this;
}
removeHead() {
let removed = this.head;
if (!this.head) return undefined;
this.head = this.head.next;
this.head.prev = null;
this.length--;
return removed;
}
removeTail() {
let removed = this.tail;
if (!this.tail) return undefined;
if (this.length === 1) {
this.head = null;
this.tail = null;
};
this.tail = removed.prev;
this.tail.next = null;
this.length--;
return removed;
}
```

## Find

Since we don’t have an index to get our item by we’re going to have some problems with inserting/removing in the middle of the list, so we’re going to need our own utility function.

It’s very simple, we just need to store the current item and use a `for`

or `while`

loop to use our pointers to update `current`

until we’re at the item we want.

Of course, this gives us an `O(n)`

search time, but since we’re using a doubly linked list we can just start from the tail if what we want is past the middle of the list, giving us `O(n / 2)`

.

```
find(index) {
let current
if (index < 0 || index >= this.length) return undefined;
if (index <= this.length / 2) {
current = this.head;
for (let i = 0; i < index; i++) current = current.next;
} else {
current = this.tail;
for (let i = this.length; i > index; i--) current = current.prev;
}
return current;
}
```

## Insert and Remove

Now that we have our little utility in place we can use it to find the item in the index we want then set the pointers on it and the item before and after it to our new node, thus “stitching” it into place.

If the index is on the head or tail, we can just reuse our previous methods.

```
insert(val, index) {
if (index < 0 || index > this.length) return null;
if (index === this.length) return this.addTail(val);
if (index === 0) return this.addHead(val);
let prev = this.find(index - 1),
newNode = new Node(val),
temp = prev.next;
prev.next = newNode;
newNode.next = temp;
newNode.prev = prev;
this.length++;
return true;
}
```

Removing is obviously just the inverse of inserting and a bit simpler. Find the node we want to remove and set the pointers on the surrounding nodes to each other, leaving nothing that references the removed node.

```
remove(index) {
if (index < 0 || index >= this.length) return null;
if (index === this.length) return this.removeTail();
if (index === 0) return this.removeHead();
let removed = this.find(index);
removed.prev.next = removed.next;
removed.next.prev = removed.prev;
this.length--;
return removed;
}
```

## Update

This one is so simple it’s almost no even worth mentioning, just find the item and reset it’s value.

```
update(val, index) {
let node = this.find(index);
if (node) node.val = val;
return node;
}
```

## Conclusion

While this may have seemed like a lot of work, it’s good to keep in mind that in many cases you won’t need all of it.

I really recommend checking out Buckets.js for when you don’t feel like manually making one, although it’s always good to understand the concept on a deeper level.