👉Singly Linked List

What is a Singly Linked List?

💡A data structure that consists of nodes, each with some value and a pointer to the next node in the linked list. A linked list node’s value and next node are typically stored in value and next properties, respectively.

💡A singly linked list is a linear data structure where elements, called nodes, are not stored contiguously in memory. Instead, each node contains the data (the actual information you want to store), and the pointer (a reference (like an address) to the next node in the list).

The first node in a linked list is referred to as the head of the linked list, while the last node in the linked list, whose next property points to the null value, is known as the tail of the linked list.

Key characteristics include:

Dynamic Size: Nodes can be added or removed as needed, making the list flexible in size.
Efficient Insertion/Deletion: Adding or removing nodes at any position typically takes constant time (), as you only need to update a few pointers.
No Random Access: Accessing a specific element requires traversing the list from the beginning, as there's no direct indexing like in arrays.
Sequential Access: Nodes are accessed sequentially, one after the other, following the pointers.

Common use cases:

Implementing stacks and queues
Representing graphs
Implementing undo/redo functionality
Dynamic memory allocation

Big O Notation of Singly Linked List Operations

Operation	Time Complexity	Explanation
Insertion (head)	$O(1)$	Only needs to update a few pointers. You only need to update the head pointer.
Insertion (tail)	$O(1)$ (average)	Assuming a tail pointer, it's also constant time. You can directly access the tail and update its next pointer.
Insertion (middle)	$O(n)$	Requires finding the insertion point by traversing nodes.
Deletion (head)	$O(1)$	Updating pointers for the first node is constant time.
Deletion (tail)	$O(n)$	Finding the tail node without a tail pointer requires traversal.
Deletion (middle)	$O(n)$	Finding the node to delete involves traversal.
Search	$O(n)$	Elements aren't indexed, so you need to check each one.
Access by index	$O(n)$	No direct access; you must traverse from the beginning.
Traversal	$O(n)$	Visiting each node takes time proportional to the list's length.

Operation

Time Complexity

Explanation

Insertion (head)

$O(1)$

Only needs to update a few pointers. You only need to update the head pointer.

Insertion (tail)

$O(1)$ (average)

Assuming a tail pointer, it's also constant time. You can directly access the tail and update its next pointer.

Insertion (middle)

$O(n)$

Requires finding the insertion point by traversing nodes.

Deletion (head)

$O(1)$

Updating pointers for the first node is constant time.

Deletion (tail)

$O(n)$

Finding the tail node without a tail pointer requires traversal.

Deletion (middle)

$O(n)$

Finding the node to delete involves traversal.

$O(n)$

Elements aren't indexed, so you need to check each one.

Access by index

$O(n)$

No direct access; you must traverse from the beginning.

Traversal

$O(n)$

Visiting each node takes time proportional to the list's length.

Implementation of Singly Linked List In JavaScript

implementation.js


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

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

  /**
   * This function adds a new node with a given value to the end of a linked list.
   *
   *  * Pseudocode - Push
   *
   * 1. This function should accept a value
   * 2. Create a new node using the value passed to the function
   * 3. If there is no head property on the list, set the head and tail to be the newly created node
   * 4. Otherwise, set the next property on the tail to be the new node and set the tail property on the list to be the newly created node
   * 5. Increment the length by one
   *
   * @param value - The value parameter represents the value of the node that needs to be added to the
   * end of the linked list.
   * @returns The updated linked list is being returned.
   */
  push(value) {
    const newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
    return this;
  }

  /**
   * This function removes the last element from a linked list and updates the tail pointer.
   *
   * Pseudocode - Popping
   *
   * 1. If there are no nodes in the list, return `undefined`
   * 2. Loop through the list until reach the tail
   * 3. Set the next property of the 2nd to last node to be `null`
   * 4. Set the tail to be the 2nd to last node
   * 5. Decrement the length of the list by 1
   * 6. Return the value of the node removed
   *
   * @returns The `pop()` method is returning the node that was removed from the end of the linked list.
   */
  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;
  }

  /**
   * This is a shift function that removes the first element from a linked list and returns it.
   *
   * Pseudocode - Shift
   *
   * 1. If there are no nodes, return undefined
   * 2. Store the current head property in a variable
   * 3. Set the head property to be the current head's next property
   * 4. Decrement the length by 1
   * 5. Return the value of the node removed
   *
   * @returns The method `shift()` is returning the node that was removed from the beginning of the
   * linked list. If the linked list is empty, it returns `undefined`.
   */
  shift() {
    if (!this.head) return undefined;

    let currentHead = this.head;
    this.head = currentHead.next;
    this.length--;

    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }

    return currentHead;
  }

  /**
   * This function adds a new node with the given value to the beginning of a linked list.
   *
   * Pseudocode - Unshift
   *
   * 1. This function should accept a value
   * 2. Create a new node using the value passed to the function
   * 3. If there is no head property on the list, set the head and tail to be the newly created node
   * 4. Otherwise, set the newly created node's next property to be the current head property on the list
   * 5. Set the head property on the list to be that newly created node
   * 6. Increment the length of the list by 1
   * 7. Return the linked list
   *
   * @param value - The value parameter represents the value of the node that we want to add to the
   * beginning of the linked list.
   * @returns The updated linked list is being returned.
   */
  unshift(value) {
    const newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.length++;
    return this;
  }

  /**
   * This function retrieves the node at a specified index in a linked list.
   *
   * Pseudocode - Get
   *
   * 1. This function should accept an index
   * 2. If the index is less than zero or greater than or equal to the length of the list, return null
   * 3. Loop through the list until reach the index and return the node at that specific index
   *
   * @param index - The index parameter is the position of the node that we want to retrieve from the
   * linked list. It starts from 0 for the first node and goes up to length-1 for the last node.
   * @returns The `get(index)` method returns the node at the specified index position in the linked
   * list. If the index is out of range (less than 0 or greater than or equal to the length of the list),
   * it returns `null`.
   */
  get(index) {
    if (index < 0 || index >= this.length) return null;

    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }

    return current;
  }

  /**
   * This function sets the value of a node at a specific index in a data structure.
   *
   * Pseudocode - Set
   *
   * 1. This function should accept a value and an index
   * 2. Use `get` method to find the specific node
   * 3. If the node is not found, return false
   * 4. If the node is found, set the value of that node to be the value which passed to the function and return true
   *
   * @param index - The index parameter is the position of the node in the linked list where the value
   * needs to be updated.
   * @param value - The new value that we want to set for the node at the specified index in the linked
   * list.
   * @returns The `set` method returns a boolean value. It returns `true` if the node at the specified
   * index is found and its value is updated successfully, and `false` if the node is not found.
   */
  set(index, value) {
    let foundNode = this.get(index);

    if (foundNode) {
      foundNode.value = value;
      return true;
    }

    return false;
  }

  /**
   * This function inserts a new node with a given value at a specified index in a linked list.
   *
   * Pseudocode - Insert At
   *
   * 1. This function should accept a value and an index
   * 2. If the index is less than 0 or greater than the length, return false
   * 3. If the index is the same as the length, push a new node to the end of the list
   * 4. If the index is 0, `unshift` a new node to start of the list
   * 5. Otherwise, using the `get` method, access the node at the index -1
   * 6. Set the next property on that node to be the new node
   * 7. Set the next property on the new node to be the previous next
   * 8. Increment the length and return true
   *
   * @param index - The index at which the new value should be inserted in the linked list.
   * @param value - The value to be inserted into the linked list.
   * @returns The method is returning a boolean value indicating whether the insertion was successful or
   * not. It returns `true` if the insertion was successful and `false` if the index is out of bounds.
   */
  insertAt(index, value) {
    if (index < 0 || index >= this.length) return undefined;

    if (index === this.length) return this.push(value);
    if (index === 0) return this.unshift(value);

    const newNode = new Node(value);
    let previous = this.get(index - 1);
    let temp = previous.next;
    previous.next = newNode;
    newNode.next = temp;
    this.length++;

    return this;
  }

  /**
   * This function removes a node from a linked list at a specified index.
   *
   * Pseudocode - Remove
   *
   * 1. If the index is less than zero or greater than the length, then return undefined
   * 2. If the index is the same as the length - 1, `pop`
   * 3. If the index is 0, `shift`
   * 4. Otherwise, using `get` method, access the node at the index `-1`
   * 5. Set the next property on that node to be the next of the next node
   * 6. Decrement the length
   * 7. Return the removed value
   *
   * @param index - The index parameter represents the index of the node to be removed from the linked
   * list.
   * @returns The method is returning the node that was removed from the linked list. If the index is
   * invalid (less than 0 or greater than or equal to the length of the list), the method returns
   * undefined. If the index is the last index of the list, the method removes and returns the last node
   * using the pop() method. If the index is the first index of the list, the method removes
   */
  remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === this.length) return this.shift();
    if (index === this.length - 1) return this.pop();

    let previousNode = this.get(index - 1);
    let removed = previousNode.next;
    previousNode.next = removed.next;
    this.length--;

    return removed;
  }

  /**
   * This function reverses the order of a linked list.
   *
   * Pseudocode - Reverse
   *
   * 1. Swap the head and tail
   * 2. Create a variable to keep track next value which is called `next`
   * 3. Create a variable to keep track previous value which is called `previous`
   * 4. Create a variable called node and initialize it to the head property
   * 5. Loop through the list
   * 6. Set next to be the `next` property on whatever node is
   * 7. Set the next property on the node to be whatever `previous` is
   * 8. Set `previous` to be the value of the node variable
   * 9. Set the node variable to be the value of the `next` variable
   *
   * @returns The updated linked list with its nodes reversed is being returned.
   */
  reverse() {
    let currentNode = this.head;
    this.head = this.tail;
    this.tail = currentNode;

    let next;
    let previous = null;

    for (let i = 0; i < this.length; i++) {
      next = currentNode.next;
      currentNode.next = previous;
      previous = currentNode;
      currentNode = next;
    }

    return this;
  }

  /**
   * The function prints the values of a linked list in an array format.
   */
  print() {
    let array = [];
    let current = this.head;

    while (current) {
      array.push(current.value);
      current = current.next;
    }

    return array;
  }
}

example.js

// Initialize a new food list using Singly Linked List
const foodList = new SinglyLinkedList();
console.log('Initial list: ', foodList);

// Push new items to the list
foodList.push('burger');
foodList.push('pizza');
foodList.push('sandwich');
foodList.push('steak');
foodList.push('hotpot');
console.log('New items added: ', foodList);
console.log('New items added as array: ', foodList.print());

// Remove the last item from the list
const lastItem = foodList.pop();
console.log('Last removed item: ', lastItem.value);
console.log(`New list after removing ${lastItem.value} item: `, foodList);
console.log(
  `New list after removing ${lastItem.value} item as array: `,
  foodList.print()
);

// Remove the first item from the list
const firstItem = foodList.shift();
console.log('First removed item: ', firstItem.value);
console.log(`New list after removing ${firstItem.value} item: `, foodList);
console.log(
  `New list after removing ${firstItem.value} item as array: `,
  foodList.print()
);

// Add a new item to the beginning of the list
const newBeginningItem = foodList.unshift('burger');
console.log('New added beginning item: ', newBeginningItem.head.value);
console.log(
  `New list after adding ${newBeginningItem.head.value} item: `,
  foodList
);
console.log(
  `New list after adding ${newBeginningItem.head.value} item as array: `,
  foodList.print()
);

// Get specific item with index
const getItem = foodList.get(2);
console.log('Get item of index 2: ', getItem.value);

// Set a new item value at specified index
const updatedItem = foodList.set(2, 'franchisee');
console.log('New updated item: ', updatedItem);
console.log(`New list after updating to franchisee item: `, foodList);
console.log(
  `New list after updating to franchisee item as array: `,
  foodList.print()
);

// Insert a new item at specified index
const newInsertedItem = foodList.insertAt(2, 'chicken');
console.log('New inserted item at index of 2: ', updatedItem);
console.log(`New list after inserting chicken item: `, foodList);
console.log(
  `New list after inserting chicken item as array: `,
  foodList.print()
);

// Remove a item at specified index
const removedItem = foodList.remove(2);
console.log('Removed item: ', removedItem.value);
console.log(`New list after removing ${removedItem.value} item: `, foodList);
console.log(
  `New list after removing ${removedItem.value} item as array: `,
  foodList.print()
);

// Reverse the order of the linked list
console.log('Food list before reversing: ', foodList.print());
foodList.reverse();
console.log('Food list after reversing: ', foodList.print());

PreviousLinked List NextDoubly Linked List

Last updated 5 months ago