Singly Linked List in JavaScript

A singly linked list is a collection of nodes where each node contains a value and a reference (or pointer) to the next node in the sequence. The list maintains a reference to the first node head and the last node tail, and it keeps track of the number of nodes, length.

Theory

Arrays and objects are excellent data structures for most applications. However, when you start dealing with large datasets (in the order of hundreds of thousands or more) having the right data structure becomes crucial.

Singly linked lists serve as the foundation for other data structures like stacks, queues, graphs, and trees.

Implementation

Node Class

Now that we've talked about the why and the when I guess we should go into the how.

First, let's define the Node class, which will represent each element in the linked list.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

SinglyLinkedList Class

Next, we'll define the SinglyLinkedList class, which will manage the nodes and provide methods to manipulate the list.

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

Adding a Node to the End

function push(value) {
  const newNode = new Node(value);
  if (this.length === 0) {
    this.head = newNode;
    this.tail = this.head;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.length++;
  return this;
}

Explanation: The push method creates a new node with the given value. If the list is empty, we set both the head and tail to the new node. Otherwise, we append the new node to the end of the list by updating the next property of the current tail and then setting the new node as the tail. The length is incremented, and the updated list is returned.

Removing a Node from the End

function pop() {
  if (!this.head) return undefined;
  let current = this.head;
  let newTail = current;
  while (current.next) {
    newTail = current;
    current = current.next;
  }
  this.tail = newTail;
  this.tail.next = null;
  this.length--;
  if (this.length === 0) {
    this.head = null;
    this.tail = null;
  }
  return current;
}

Explanation: The pop method first checks if the list is empty and returns undefined if it is. Otherwise, it traverses the list to find the second-to-last node which we set as the tail and updates its next property to null, effectively unlinking the previous tail, allowing it to be garbage collected. The length is decremented, and in case the list became empty, the head and tail are set to null. The removed node is returned.

Removing a Node from the Beginning:

As for array, the shift method is used to remove a node from the beginning of the list. Unlike with arrays this process doesn't involves reassign every node's index so here it's pretty much where linked list excels:

function shift() {
  if (!this.head) return undefined;
  let current_head = this.head;
  this.head = current_head.next;
  this.length--;
  if (this.length === 0) {
    this.tail = null;
  }
  return current_head;
}

See how few operations there are?

Explanation: We first check if the list is empty and returns undefined if it is. Otherwise, we store the head before overriding it with its next node then we decrement the length and finally we return the node we removed. Also don't forget to clean up the tail if there is no more items as we only took care of the head by setting it to current_head.next which is null when there is only one element.

Adding a Node to the Beginning

Next stop unshift, the opposite of shift, adding a new node to the beginning of the list, again this is where linked list excel, let's see how:

function unshift(value) {
  let new_node = new Node(value);
  if (!this.head) {
    this.head = new_node;
    this.tail = this.head;
  } else {
    new_node.next = this.head;
    this.head = new_node;
  }

  this.length++;
  return this;
}

Explanation: Quite simple again, we create a new node with the given value. If the list is empty, we set both the head and tail to the new node. Otherwise, we set the next property of the new node to the current head and update the head to be the new node. The length is incremented, and the updated list is returned.

Getting a Node by Index:

How about the get method? With arrays we can easily get an item by its index arrindex but with a linked list it's a little harder as nodes are not referenced by index, they're like free agents linked to each other.

function get(index) {
  if (index < 0 || index >= this.length) {
    return undefined;
  }
  let item = this.head;
  for (let i = 0; i < index; i++) {
    item = item.next;
  }
  return item;
}

Explanation: Because nodes are not indexed we need to traverse the whole list to find our node and to prevent our traversal to run out of the list we need a guard clause, returning undefined if the index parameter is out of bounds. Otherwise we will define a variable item starting from the head (which will be returned if the index parameter is 0) then we will loop through the list going from item.next to item.next until the index parameter is superior to the current iterator i meaning our item variable is currently storing the desired item.

Setting a Node Value by Index

function set(index, value) {
  const item = this.get(index);
  if (!item) return false;
  item.value = value;
  return true;
}

Explanation: Here it's quite simple we use our previously defined get method to find the item, if the item is undefined we return false otherwise we update the value of the item and return true.

Inserting a Node at a Specific Index:

function insert(value, index) {
  if (index >= this.length) {
    return !!this.push(value);
  } else if (index <= 0) {
    return !!this.unshift(value);
  }

  const previous_item = this.get(index - 1);
  const next_item = previous_item.next;
  const new_item = new Node(value);
  previous_item.next = new_item;
  new_item.next = next_item;
  this.length++;
  return true;
}

Explanation: Let's recap, there are a few scenarios we need to handle:

• First if the index parameter is equal or superior to the length, we can insert at the end so we just use the push function.
• Second if the index parameter is less than or equal to 0 we can insert at the beginning so we just use the unshift function.
• For each case we return the double banged result, I guess it sounds weird but it just means it returns the boolean value of the list, always true.
• Otherwise we get the previous_item compared to the index we want to insert at, we store it's next value before overriding it. Then we create a new node, and inserts it between the previous node and the next node. The length is incremented, and true is returned!

Removing a Node at a Specific Index

function remove(index) {
  if (index < 0 || index >= this.length) return undefined;
  else if (index === 0) return this.shift();
  else if (index === this.length - 1) return this.pop();

  const previous = this.get(index - 1);
  const next_item = previous.next;
  previous.next = next_item.next;
  this.length--;
  return next_item;
}

Explanation: So here again we have some edge cases to handle:

• if the index is out of bounds we return undefined
• if the index is 0 then we can reuse our shift function to remove the head.
• if the index is equal to the length - 1 it means we want to remove the tail so we reuse our pop function.
• Otherwise, we find the node at the index before the specified index, store the node to be removed, and update the next property of the previous node to unlink the node to be removed.

The length is decremented, and the removed node is returned.

Reversing the List:

Last but not least, the reverse function this one is totally optional and is mostly good to know for interviews as it could randomly show up.

function reverse() {
  let temp = null;
  let current = this.head;
  let prevNode = null;

  while (current != null) {
    temp = current.next;
    current.next = prevNode;
    prevNode = current;
    current = temp;
  }
  this.head = prevNode;
  return this;
}

This is a tough one so I'll try my best to guide you through:

1. We define a current variable starting from the head — the element we're currently looping over.
2. We initialize prevNode to null (the previous node in the reversed order) and temp as a working variable.
3. On each iteration:

Now that we have everything set up we traverse the list, reversing each node's next pointer to point to the previous node: 4. Store current.next in temp so we don't lose the rest of the list. 5. Set current.next = prevNode — this is the reversal step. On the first iteration, the head becomes the tail so it points to null. 6. Advance prevNode = current and current = temp to move forward. 7. After the loop, prevNode holds the new head. We assign it to this.head and return the list.

Performance considerations

Time Complexity

• Insertion: O(1) for push and unshift, O(n) for insert (remember we have to traverse the list unless inserting at the beginning or end).
• Removal: O(1) for pop and shift, O(n) for remove (remember we have to traverse the list unless removing from the beginning or end).
• Search: O(n), we still have to traverse the list
• Access: O(n), we still have to traverse the list

Practical Use Cases

• Frequent Insertions/Deletions: Linked lists are ideal when you need to frequently insert or delete elements at the beginning or end of the list.
• Dynamic Size: Linked lists can easily grow or shrink in size, making them suitable for applications where the size of the data structure is not known in advance.
• Memory Management: In lower-level languages, linked lists allow for storing memory in a non-contiguous way, which can be more efficient in certain scenarios.

Example use cases

• Browser History: Managing the history of visited web pages where new pages are added to the end and the most recent pages are accessed frequently.
• Music Playlist: Managing a playlist where songs can be added or removed from the beginning or end.

Congrats 🎉 you made it through I hope you learned a lot, I certainly did and if you have any suggestions, improvements or anything that comes to your mind don't hesitate to write! I'll reply as soon as possible!

Happy coding! 🚀