Linked List Operations

Before learn about linked list operations, make sure to know about Linked List first.

Things to remember

head points to the first node of the linked list
next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.

Node structure -

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

All operations

Traverse - Display all elements
Insert - At the beginning, end, and a given position
Delete - From the beginning, end, and a given position
Search - Find a value in the list
Sort - Sort the linked list using Merge Sort

class LinkedList {
  constructor() {
    this.head = null;
  }
 
  // ...all operations here
}

Traverse a Linked List

// display all elements
traverse = () => {
  let current = this.head;
  let result = [];
 
  while (current) {
    result.push(current.data);
    current = current.next;
  }
 
  console.log(result.join(" -> "));
};

Insert elements to a Linked List

We can add elements to either the beginning, middle, end or a specific position.

1. Insert at the beginning

insertAtBeginning = (data) => {
  let newNode = new Node(data);
  newNode.next = this.head;
  this.head = newNode;
};

2. Insert at the end

insertAtEnd = (data) => {
  let newNode = new Node(data);
 
  if (!this.head) {
    this.head = newNode;
    return;
  }
 
  let current = this.head;
  while (current.next) {
    current = current.next;
  }
  current.next = newNode;
};

3. Insert at the middle

insertAtMiddle = (data) => {
  let newNode = new Node(data);
 
  if (!this.head) {
    this.head = newNode;
    return;
  }
 
  // count total nodes
  let count = 0;
  let current = this.head;
 
  while (current.next) {
    current = current.next;
    count++;
  }
 
  // find middle position
  let middle = Math.floor(count / 2);
  let index = 0;
  current = this.head;
 
  // traverse to the middle
  while (current && index < middle) {
    current = current.next;
    index++;
  }
 
  // insert node at middle position
  newNode.next = current.next;
  current.next = newNode;
};
 
// Time complexity: O(N + N/2) ~ O(N)
// Space complexity: O(1)

4. Insert at a Specific Position

insertAtPosition = (data, position) => {
  if (position < 0) return;
  let newNode = new Node(data);
 
  if (position === 0) {
    newNode.next = this.head;
    this.head = newNode;
    return;
  }
 
  let current = this.head;
  let prev = null;
  let index = 0;
 
  while (current && index < position) {
    prev = current;
    current = current.next;
    index++;
  }
 
  if (!prev) return;
  prev.next = newNode;
  newNode.next = current;
};

Delete from a Linked List

We can delete either from the beginning, end or from a specific position.

1. Delete from beginning

deleteFromBeginning = () => {
  if (!this.head) return;
  this.head = this.head.next;
};

2. Delete from end

deleteFromEnd = () => {
  if (!this.head) return;
 
  if (!this.head.next) {
    this.head = null;
    return;
  }
 
  let current = this.head;
  let prev = null;
 
  while (current.next) {
    prev = current;
    current = current.next;
  }
 
  prev.next = null;
};

3. Delete from a specific position

deleteFromPosition = (position) => {
  if (!this.head) return;
 
  if (position === 0) {
    this.head = this.head.next;
    return;
  }
 
  let current = this.head;
  let prev = null;
  let index = 0;
 
  while (current && index < position) {
    prev = current;
    current = current.next;
    index++;
  }
 
  prev.next = current.next;
};

Search an element on a Linked List

search = (data) => {
  let current = this.head;
  let index = 0;
 
  while (current.next) {
    if (current.data === data) {
      console.log(`Value ${data} found at position ${index}`);
      return index;
    }
 
    current = current.next;
    index++;
  }
 
  console.log(`Value ${data} not found`);
  return null;
};

Sort elements of a Linked List

sort = () => {
  if (!this.head || !this.head.next) return this.head;
 
  let arr = [];
  let current = this.head;
 
  // 1. store node values into the arr
  while (current) {
    arr.push(current.data);
    current = current.next;
  }
 
  // 2. sort the arr
  arr.sort();
 
  // 3. convert sorted arr back to a linked list
  let prev = null;
  arr.forEach((el, index) => {
    let newNode = new Node(el);
 
    if (index === 0) {
      this.head = newNode;
      prev = this.head;
    } else {
      prev.next = newNode;
      prev = newNode;
    }
  });
};
 
// Time complexity: O(n) + O(nlogn) + O(n) = O(nlogn)
// Space complexity: O(n)

Linked List Operations

On this page