Implementing Linked-Lists with NodeJS and Javascript

Let's dive into the Linked Lists with NodeJS / Javascript

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.

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:

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:

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:

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…:

node linked-list.js

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

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.

Jon, what about double linked lists?

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.

Where can We Use Linked Lists?

Collections in General

Linked Lists are good for dealing with collections in general, I mean if you need to implement queues, stacks with a lot of insert and remove operations you can use linked lists on the implementation instead of common arrays, this will improve the performance.

Real-Time Applications

Usually in real-time applications, we try to have the best efficiency regarding memory usage and proccessing speed to deliver on fetch content. Linked Lists (not alone but with other solutions) can help us improve performance and can do better than common arrays.

Best Practices

Even though the code above may be improved, the intention here is to have a code easy to understand and this could make it more verbose. When you're dealing with production and bigger applications you need to have a clean code, with well defined classes, functions, etc.

Remember that the code should be easy to maintain and easy to include future features if needed.

Challenge

Try to implement the removeFirst, removeLast, e find functions to cover more common cases of dealing with collections, put your results and doubts in the comments bellow.

In Summary

If you're looking for linked lists to pass a test, or an interview, it is important that you remember that not only in NodeJS/JavaScript but also in other languages, we devs must seek and create efficient and dynamic applications, that are easy to maintain and scale and data structures in general are concepts that help us to accomplish that. These concepts don't change over time and you can always rely on them to improve something, maybe you can solve a performance problem just by changing the structure you are using.

Finally, do you have any tips, tricks or questions about using linked lists in JavaScript/NodeJS? Share it and let's learn together!