Implementing Linked-Lists with NodeJS and Javascript

Linked lists in JavaScript from scratch: nodes, insert/remove, and when they beat arrays. Practical Node.js tutorial with examples.

Inserting in the middle of a large array is expensive — the runtime shifts indices. A linked list trades O(1) index access for O(1) insert/remove when you already hold the node. Episode 3.

What you'll learn:

Nodes with data and next
addFirst, addLast, traversal
Arrays vs linked lists in practice
Doubly linked lists (previous)

Prerequisites: arrays (ep. 2) and the series overview.

Linked lists in JavaScript: nodes and pointers

When we talk about Linked Lists we need to keep in mind that they are a fundamental data structure, offering a flexible and efficient way to store and manipulate collections.

In NodeJS and/or JavaScript it is interesting for those who understand and know how to implement linked lists, this can optimize some data operations, especially when inserting and removing items all the time (often) is necessary.

Here we will see the implementation and some benefits of linked lists in JavaScript, with important insights to develop dynamic applications.

implementing-linked-lists-with-nodejs-and-javascript

Fundamentals of Linked Lists

A linked list is composed of nodes, where each node contains data and a reference (or a “link”) to the next node in the sequence. This is slightly different from the usual arrays. Also, linked lists do not require a continuous block of memory, allowing efficient insertions and removals of elements without the need to reorganize the entire collection.

Implementing Linked Lists in JavaScript / NodeJS

So let's get right into it, linked lists, here's the code (simple version), for us to create a linked-list, so create a linked-list.js file and paste the code bellow in it:

code

class ListNode {
  constructor(data) {
    this.data = data
    this.next = null
  }
}
 
class LinkedList {
  constructor() {
    this.head = null
  }
 
  // Func to add elements in the "top" or the start of the list
  addFirst(data) {
    let newNode = new ListNode(data)
    newNode.next = this.head
    this.head = newNode
  }
 
  // Func to add elements at the end of the list
  addLast(data) {
    let newNode = new ListNode(data)
    if (!this.head) {
      this.head = newNode
      return
    }
    let tail = this.head
    while (tail.next !== null) {
      tail = tail.next
    }
    tail.next = newNode
  }
 
  // Here you can try out other functions
}

Now, let's test it out, put this code right after the addLast func:

code

printList() {
    let current = this.head;
    while (current !== null) {
      console.log({ current: current.data, next: current.next });
      current = current.next;
    }
  }

Then, let's populate this list and print it out, put this code outside the linked-list class:

code

const testList = () => {
  const list = new LinkedList()
  list.addFirst(1)
  list.addFirst(2)
  list.addFirst(3)
  list.addLast(4)
  list.addLast(5)
  list.addLast(6)
  list.printList()
}
 
testList()

Running the code in 3, 2, 1…:

code

node linked-list.js

This should be the output (or something pretty similar):

code

node linked-list.js
 
{
  current: 3,
  next: ListNode { data: 2, next: ListNode { data: 1, next: [ListNode] } }
}
{
  current: 2,
  next: ListNode { data: 1, next: ListNode { data: 4, next: [ListNode] } }
}
{
  current: 1,
  next: ListNode { data: 4, next: ListNode { data: 5, next: [ListNode] } }
}
{
  current: 4,
  next: ListNode { data: 5, next: ListNode { data: 6, next: null } }
}
{ current: 5, next: ListNode { data: 6, next: null } }
{ current: 6, next: null }

AWESOME!

If you got here, that's awesome, look at what we printed in the console. The head printed the number 3 which is the last execution of addFirst function. And the last number printed was the number 6, and this was the last addLast function executed, so it's working mate, now you can play around with adding first and last elements to the list.

What about doubly linked lists?

implementing-double-linkedlist-with-nodejs-javascript

Basically the difference between the basic and double linked list is that we include a previous information. People, you don't need to call it next and previous, you can call it bananas and apples the key here is that you can understand that you will have a current node, and at this current node you will have information that will point you to the next and previous node (the nodes right in side of the current one) if they exist.

Now, let's challenge you, can you implement the previous one and turn this example in a double linked list?

If you need help on that, put in the comment section bellow and I will make a post for us to turn this in to a double linked list.

Edge cases: losing `head` and accidental cycles

Forgetting to update head on addFirst or when removing the first node orphans the rest of the list.

How do I know I created a cycle? Two nodes share the same next, or the tail points backward — traversal never ends. In debug, track visited nodes in a Set.