Re-implementing single and double linked lists in Javascript

Many new developers come to programming through Javascript because it is ubiquitous on the web and can be used for basically anything. As a high-level scripting language, it has many built-in functions and available libraries that mean many developers never need to dive into special data structures.

It’s also the entry point for a lot of self-taught developers who have not been exposed to computer science topics like data structures. This included me.

Why re-implement linked lists?

Linked lists are one of the simplest data structures and many advanced data structures use similar techniques but more complex behavior. This is the easiest starting point.

In this post, we’re going to re-create single and double linked lists. We’re going to start from a really basic implementation and then improve it step by step so that it’s really clear what we’re doing and why.

Linked List vs Array

Quick note: Linked lists are similar to arrays but not the same. We’ll go over some differences, but the key most of the time is speed of insertions/deletions vs random access reads. There are also some cool things you can do with linked lists that arrays don’t do as elegantly.

Single Linked List — a prototype

Here’s a visual representation of what we’re going for. It’s a piece of data combined with a pointer to the next data item.

We’re going to start as simple as possible, a basic prototype that allows us to link one item to another in a single direction.

Single linked list prototype:

const link3 = {
data: "how data structures work!",
next: null
}
const link2 = {
data: "is it to know ",
next: link3
}
const link1 = {
data: "How sweet ",
next: link2
}
let current = link1;
let output = "";
while (current)  {
output += current.data;
current = current.next;
}
console.log(output);

If you run this code, you will see the text “How sweet is it to know how data structures work!”.

Limitations

A single linked list has a pretty obvious limitation: No going backward! At the same time, it takes very little memory. It’s also easy to insert items at the end.

I also want to highlight another issue: consistency. As a non-static typed language, there is no guarantee that each item in the list is another list item. But that’s a separate issue that we will address later.

Double linked list

A double linked list is similar but now each item comes with another property “prev”.

const link3 = {
data: "how data structures work!",
next: null,
prev: null
}
const link2 = {
data: "is it to know ",
next: null,
prev: null
}
const link1 = {
data: "How sweet ",
next: null,
prev: null
}
link1.next = link2;
link2.next = link3;
link2.prev = link1;
link3.prev = link2;
let output = "";
let current = node1;
while (current)  {
output += current.data;
current = current.next;
}
console.log(output);
let outputBack = "";
current = link3;
while (current)  {
outputBack += current.data;
current = current.prev;
}
console.log(outputBack);

Now it’s possible to traverse from link to link both directions. And while this is the simplest possible implementation of a list-like structure, it obviously does not scale.

For now, our list kinda sucks. Adding items is a pain and we can’t query its length or anything. What we have is a set of items that reference each other, but we don’t have a consistent and scalable data structure yet. Let’s fix it.

Taking the prototype to a real structure

We now have a way of going forward and backward across our list but our prototype is still very limited. There’s no easy way to add, remove, or sort items in our list.

How can we make this better? Let’s give ourselves some basic goals for now:

  • Get the first and last items of the list.
  • Get the size of the list
  • Add items to the list.

Those look good. First, we should formalize our items to ensure consistency. Each list item will be called a ‘node’ and can be represented like so:

class Node {
constructor(data, next = null, prev = null) {
this.data = data;
this.next = next;
this.prev = prev;
}
}

Next, we need a container — the list abstraction itself.

class List {
   constructor() {
this.length = 0;
this.head = null;
this.tail = null;
   }
   append(data) {
const node = new Node(data);

this.length++;
      if(!this.head) {
this.head = node;
this.tail = node;
return this;
}
      this.tail.next = node;
node.prev = this.tail;
this.tail = node;

return this;
}
}

Progress!

Now we’re getting somewhere. While still limited, this is a data structure you could actually use.

You can add a lot more functionality (adding to the front of the list vs the bottom, deletion, etc). There are lots of sources for that.

Special cases

Linked lists still look a lot like Arrays to most people. Conceptually they are similar in that they are both single dimensional collections of data. However their performance characteristics are quite different. With linked lists, you cannot access an item in the middle directly. You can only go to the next or previous item. It’s easier and faster to insert an item in a linked list than an array.

Linked lists also allow special structure. For instance, there is a special case, the looped-list, that you should be aware of.

Check this out:

const list = new List();
list.append("First");
list.append("Second");
list.append("Third");
list.tail.next = list.head;
let current = list.head;
while (current.next) {
console.log(current.data);
current = current.next;
}
// will loop forever

Here we have a list that will constantly cycle.

Advantages of linked lists:

Behind the scenes, Arrays have a specific number of allowed items. Adding or removing items can quite expensive for a computer. In a linked list, adding or removing items is very cheap and fast.

Disadvantages of linked lists

No random access. As you can see in the code, lists can only be accessed in order. This means that searching, sorting, and other such operations on a list are very expensive.

Ask Questions

I hope this is helpful. I’d love to know if you have questions about this structure, what it can be used for, anything.

What would you like to learn next?