Data Structure: Singly Linked List in JavaScript and TypeScript

A singly linked list is a list of items, where each element has reference to the next element. Elements do not have info on the previous element. So we can only go to the next element while traversing a singly linked list.

NOTE

In this article, we are discussing in detail, the implementation of Singly Linked List in JavaScript and TypeScript.

Check the link below to check the details of Linked List and Singly Linked List-

Linked List Details

Singly Linked List Details

Implementation

Here is the detailed implementation of Singly Linked List in JavaScript and TypeScript, step-by-step –

Step #1: Node Class

The purpose of the Node class is to store information on a single node. It stores data and references to the next node.

Declare a class named “Node“. You can name this class anything based on what data are you saving in the list.

Create “constructor” and accept “data”. Set the “data” value to class property “data”.

In the constructor set a class property “next” and assign a value “null“. As initially it will be null when the node is first created and pushed at the end.

JavaScript
TypeScript

// Node class for storing data and reference to the next node
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}


// Node class for storing data and reference to the next node
class Node<T> {
  data: T;
  next: Node<T> | null;

  constructor(data: T) {
    this.data = data;
    this.next = null;
  }
}

NOTE

For TypeScript we are using a generic and passing the type as <T>. This “T” type will be the type of data.

This is used to provide the flexibility of storing any type of data in the list.

You can assign a fixed type to the data, if you are going to use the list implementation for a specific single purpose.

Step #2: Linked List Class

The lined list class is the place where are implementing the actual linked list-

Create a class named “SinglyLinkedList“. You can name this class according to the purpose of the implementation.

Define a constructor.

In the constructor set – head=null, tail=null, length=0. This way we have initialized 3 properties of this class head, tail, and length.

JavaScript
TypeScript

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

// Singly Linked List class
class SinglyLinkedList<T> {
  public head: Node<T> | null;
  public tail: Node<T> | null;
  public length: number;

  constructor() {
    // Initialize head, tail, and length
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

NOTE

For TypeScript we are using a generic and passing the type as <T>. We need to pass this type <T> to the “Node” item.

Step #3: Push (Node to the end)

Create the function “push” and accept “data” as a parameter.

Create a new “Node” object using “data“.

If there is no head in the current list, then make this current node as head. If there is existing data, then make this the next node of the current tail.

Finally, make this node as tail.

Increate the length by one, as a new node is added to the list.

JavaScript

TypeScript

class SinglyLinkedList {
   //...

  // Push item at the end of the list
  push(data) {
    const node = new Node(data);

    // If the list is empty
    // then make this node as head and tail
    if (!this.head) {
      this.head = node;
    } else {
      // set the current tail's next value to new node
      this.tail.next = node;
    }

    // Set the tail to this new node
    this.tail = node;

    // Increase the length by 1
    this.length++;

    // Return the SinglyLinkedList
    return this;
  }
  
  // ...
}

class SinglyLinkedList<T> {
    //...

  push(data: T): SinglyLinkedList<T> {
    // Add data at the end of the list
    const node = new Node(data);

    if (!this.head) {
      // If list is empty, set head and tail to new node
      this.head = node;
    } else {
      // Otherwise, set the next of current tail to new node
      this.tail!.next = node;
    }

    // Set new node as the tail
    this.tail = node;
    // Increase the length
    this.length++;
    return this;
  }
    //...
}

Step #4: Pop (Last Node)

Create a function named “pop“.

If there is no element then return null.

If there are elements then start traversing from the head, and go to the second last element.

Make the second last element as the head.

Get the last element and save that in some variable.

Make the “next” pointer of that as null.

Return the last element that was saved in some variable.

JavaScript
TypeScript

class SinglyLinkedList {
  //...

  // Pop the last item
  pop() {
    // If there is no head
    // then the list does not exist
    if (!this.head) {
      return null;
    }

    let current = this.head;
    let newTail = current;

    // Traverse through the list
    // and get the second last item as newTail
    while (current.next) {
      newTail = current;
      current = current.next;
    }

    // Assign the newTail to the tail
    this.tail = newTail;

    // Delete the next pointer of the tail
    this.tail.next = null;

    this.length--;

    // Reset head and tail if it was the last item
    if (this.length == 0) {
      this.head = null;
      this.tail = null;
    }

    // Return the popped item
    return current;
  }

   //...
}

class SinglyLinkedList<T> {
    //...

  pop(): Node<T> | null {
    // Remove and return the last element from the list
    if (!this.head) {
      // If list is empty, return null
      return null;
    }

    let current = this.head;
    let newTail = current;

    while (current.next) {
      // Traverse the list to find the second last node
      newTail = current;
      current = current.next;
    }

    // Update tail and remove the last node
    this.tail = newTail;
    this.tail.next = null;
    this.length--;

    if (this.length === 0) {
      // If list becomes empty, reset head and tail
      this.head = null;
      this.tail = null;
    }

    return current;
  }
    //...
}

Step #5: Traverse all Nodes

Create method “traverse”, which is responsible of going through all the linked list nodes.

Start from the HEAD and go to TAIL

Print node information one by one.

JavaScript
TypeScript

class Node {
  //...

  // Traverse the list
  traverse() {
    let current = this.head;

    while (current) {
      console.log(current.data);

      // Change current to the next node
      current = current.next;
    }
  }

   //...
}

class SinglyLinkedList<T> {
    //...

  traverse(): void {
    // Traverse the list and log the data of each node
    let current = this.head;

    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

    //...
}

Step #6: Shift Head

Create method “shift”.

Store the current head in a variable/constant.

Make the “next” node of the current head, as the head.

Decrease the “length” by one.

Return the old head(saved in some variable) at the end.

JavaScript

TypeScript

class SinglyLinkedList {
  //...

  // Shift head
  // and make the second item as head
  // also return the first item
  shift() {
    // If there is no head then return null
    if (!this.head) {
      return null;
    }

    const currHead = this.head;

    // Set the second item as head
    this.head = currHead.next;

    // Reduce the length by one
    this.length--;

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

    // Return the head item
    return currHead;
  }

  //...
}

class SinglyLinkedList<T> {
    //...

  shift(): Node<T> | null {
    // Remove and return the first element from the list
    if (!this.head) {
      // If list is empty, return null
      return null;
    }

    const currHead = this.head;
    // Move head to the next node
    this.head = currHead.next;
    this.length--;

    if (this.length === 0) {
      // If list becomes empty, reset head and tail
      this.head = null;
      this.tail = null;
    }

    return currHead;
  }

    //...
}

Step #7: Unshift Head

Create method “unsihft” and accept a “value“

Create a new node from this “value“.

Set the “next” of this new node to the current head of the list.

Make this new node, the head of the list.

JavaScript
TypeScript

class SinglyLinkedList {
   //...

  // Unshift head
  // Create new node and set that as head
  unshift(value) {
    // Create new Node from value
    let newHead = new Node(value);

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

    // Set the new node as head
    this.head = newHead;

    // Increase length by one
    this.length++;

    return this;
  }

   //...
}

class SinglyLinkedList<T> {
    //...

  unshift(value: T): SinglyLinkedList<T> {
    // Add data at the beginning of the list
    let newHead = new Node(value);

    if (!this.head) {
      // If list is empty, set head and tail to new node
      this.tail = newHead;
    } else {
      // Otherwise, set the next of new node to current head
      newHead.next = this.head;
    }

    // Set new node as the head
    this.head = newHead;
    // Increase the length
    this.length++;
    return this;
  }

    //...
}

Step #8: Get Node by Index

We want to pass some index and want to get the node at that index-

Create a function named “get” and accept a parameter “index“.

If the index is out of range then return null.

If the index is in range then start from the head, and go to the node at the specified index.

Return the node at the end of the function.

JavaScript
TypeScript

class SinglyLinkedList {
   //...

  // Get node by index(sequence numbers)
  // 0 based index (index starts from 0)
  get(index) {
    // Check if the index is valid
    if (index < 0 || index >= this.length) {
      return null;
    }

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

    return selectedNode;
  }

   //...
}

class SinglyLinkedList<T> {
    //...

  get(index: number): Node<T> | null {
    // Get node at a specified index
    if (index < 0 || index >= this.length) {
      // If index is out of range, return null
      return null;
    }

    let selectedNode = this.head;

    for (let i = 1; i <= index; i++) {
      // Traverse the list to find the node at the given index
      selectedNode = selectedNode!.next;
    }

    return selectedNode;
  }

    //...
}

Step #9: Search by data

Here we want to search for specific data. Whichever node has the data, we want to get that index.

Create a function named “search” and accept the parameter “data“.

Start traversing the nodes one by one, starting from the HEAD.

When we find the node with that specific data, we return the index of the node.

JavaScript
TypeScript

class SinglyLinkedList {
   //...

    // Search the list for specific data
  search(data) {
    let current = this.head;
    let index = 0;

    while (current) {
      if (current.data === data) {
        return index;
      }

      current = current.next;
      index++;
    }

    return null;
  }

   //...
}

class SinglyLinkedList<T> {
    //...

  search(data: T): number | null {
    // Search for the index of a specific data in the list
    let current = this.head;
    let index = 0;

    while (current) {
      // Traverse the list and check data of each node
      if (current.data === data) {
        // If data is found, return its index
        return index;
      }

      current = current.next;
      index++;
    }

    // If data is not found, return null
    return null;
  }

    //...
}

Step #10: Set data at Node by Index

Here we want to set the data of an existing, at a specific index.

Create a function named “set”, and accept 2 parameters- “index” and “data”.

Either start from the head and go through the node one by one and get the node at the specified index. Or just use the existing “get” function, and get the index.

Set the data of the node that we got.

JavaScript
TypeScript

class SinglyLinkedList {
   //...

  // Set data of a specific node at specific index
  // 0 based index(index starts from 0)
  set(index, data) {
    let nodeAtIndex = this.get(index);

    if (nodeAtIndex) {
      nodeAtIndex.data = data;
      return true;
    }

    return false;
  }

   //...
}

class SinglyLinkedList<T> {
    //...

  set(index: number, data: T): boolean {
    // Set data of a specific node at a given index
    let nodeAtIndex = this.get(index);

    if (nodeAtIndex) {
      // If node at given index exists, update its data
      nodeAtIndex.data = data;
      return true;
    }

    // If node at given index does not exist, return false
    return false;
  }

    //...
}

Step #11: Insert Data at Specific Index

We want to create a new node with data, and add that to some specific index.

Create function “insert” and accept param “index” and “data“.

Create a new node from the “data“.

Get the node at the node before the “index” (at index – 1).

Set the newly created node as the next node of the (index – 1) node.

Set the node after that as the “next” of the new node.

JavaScript
TypeScript

class SinglyLinkedList {
   //...

  // Insert new node at a specific index
  // 0 based index(index starts at 0)
  insert(index, data) {
    if (index < 0 || index > this.length) {
      return false;
    }

    if (index === this.length) {
      this.push(data);
      return true;
    }

    if (index === 0) {
      this.unshift(data);
      return true;
    }

    let newNode = new Node(data);
    let prevNode = this.get(index - 1);
    newNode.next = prevNode.next;
    prevNode.next = newNode;

    // Increase length
    this.length++;

    return true;
  }

   //...
}

class SinglyLinkedList<T> {
    //...

  insert(index: number, data: T): boolean {
    // Insert new node at a specific index
    if (index < 0 || index > this.length) {
      // If index is out of range, return false
      return false;
    }

    if (index === this.length) {
      // If index is at the end, use push method
      this.push(data);
      return true;
    }

    if (index === 0) {
      // If index is at the beginning, use unshift method
      this.unshift(data);
      return true;
    }

    // Otherwise, insert new node at the specified index
    let newNode = new Node(data);
    let prevNode = this.get(index - 1);
    newNode.next = prevNode!.next;
    prevNode!.next = newNode;

    // Increase length
    this.length++;
    return true;
  }

    //...
}

Step #12: Remove Item from Specific Index

Create the function “remove” and accept “index” parameter.

Go to the node which is at (index – 1).

Change the “next” pointer of the node at (index – 1), and set the pointer to the node at (index + 1).

JavaScript
TypeScript

class SinglyLinkedList {
   //...

  // Remove item at index
  remove(index) {
    // Return false if index is out of range
    if (index < 0 || index >= this.length) {
      return undefined;
    }

    if (index === 0) {
      return this.shift();
    }

    if (index === this.length - 1) {
      return this.pop();
    }

    let prevNode = this.get(index - 1);
    const removedNode = prevNode.next;
    prevNode.next = prevNode.next.next;

    this.length--;
    return removedNode;
  }

   //...
}

class SinglyLinkedList<T> {
    //...

  remove(index: number): Node<T> | null {
    // Remove node at a specific index
    if (index < 0 || index >= this.length) {
      // If index is out of range, return undefined
      return null;
    }

    if (index === 0) {
      // If index is at the beginning, use shift method
      return this.shift();
    }

    if (index === this.length - 1) {
      // If index is at the end, use pop method
      return this.pop();
    }

    // Otherwise, remove node at the specified index
    let prevNode = this.get(index - 1);
    const removedNode = prevNode!.next;
    prevNode!.next = prevNode!.next!.next;

    // Decrease length
    this.length--;
    return removedNode;
  }

    //...
}

Step #13: Reverse a Singly Linked List

Create a function named “reverse“.

Traverse through the full list.

Change the “next” pointer of each node to the previous node.

JavaScript

TypeScript

class SinglyLinkedList {
   //...

  // Reverse a linked list
  reverse() {
    let currentNode = this.head;
    let prevNode = null;
    let nextNode = null;

    while (currentNode) {
      nextNode = currentNode.next;
      currentNode.next = prevNode;

      prevNode = currentNode;
      currentNode = nextNode;
    }

    this.tail = this.head;
    this.head = prevNode;

    return this;
  }

   //...
}

class SinglyLinkedList<T> {
    //...


  reverse(): SinglyLinkedList<T> {
    // Reverse the linked list
    let currentNode = this.head;
    let prevNode = null;
    let nextNode = null;

    while (currentNode) {
      // Traverse the list and reverse each node
      nextNode = currentNode.next;
      currentNode.next = prevNode;

      prevNode = currentNode;
      currentNode = nextNode;
    }

    // Update head and tail references
    this.tail = this.head;
    this.head = prevNode;

    return this;
  }

    //...
}

Full Implementation Code

Here is the full implementation of Singly Linked List, with all the functionality.

JavaScript

TypeScript

// sll.js
// Singly linked list in JavaScript

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

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

  // Push item at the end of the list
  push(data) {
    const node = new Node(data);

    // If the list is empty
    // then make this node as head and tail
    if (!this.head) {
      this.head = node;
    } else {
      // set the current tail's next value to new node
      this.tail.next = node;
    }

    // Set the tail to this new node
    this.tail = node;

    // Increase the length by 1
    this.length++;

    // Return the SinglyLinkedList
    return this;
  }

  // Pop the last item
  pop() {
    // If there is no head
    // then the list does not exist
    if (!this.head) {
      return null;
    }

    let current = this.head;
    let newTail = current;

    // Traverse through the list
    // and get the second last item as newTail
    while (current.next) {
      newTail = current;
      current = current.next;
    }

    // Assign the newTail to the tail
    this.tail = newTail;

    // Delete the next pointer of the tail
    this.tail.next = null;

    this.length--;

    // Reset head and tail if it was the last item
    if (this.length == 0) {
      this.head = null;
      this.tail = null;
    }

    // Return the popped item
    return current;
  }

  // Traverse the list
  traverse() {
    let current = this.head;

    while (current) {
      console.log(current.data);

      // Change current to the next node
      current = current.next;
    }
  }

  // Shift head
  // and make the second item as head
  // also return the first item
  shift() {
    // If there is no head then return null
    if (!this.head) {
      return null;
    }

    const currHead = this.head;

    // Set the second item as head
    this.head = currHead.next;

    // Reduce the length by one
    this.length--;

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

    // Return the head item
    return currHead;
  }

  // Unshift head
  // Create new node and set that as head
  unshift(value) {
    // Create new Node from value
    let newHead = new Node(value);

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

    // Set the new node as head
    this.head = newHead;

    // Increase length by one
    this.length++;

    return this;
  }

  // Get node by index(sequence numbers)
  // 0 based index (index starts from 0)
  get(index) {
    // Check if the index is valid
    if (index < 0 || index >= this.length) {
      return null;
    }

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

    return selectedNode;
  }

  // Set data of a specific node at specific index
  // 0 based index(index starts from 0)
  set(index, data) {
    let nodeAtIndex = this.get(index);

    if (nodeAtIndex) {
      nodeAtIndex.data = data;
      return true;
    }

    return false;
  }

}

export default SinglyLinkedList;

// sll.ts
// Singly linked list in TypeScript

class Node<T> {
  // Node class for storing data and reference to the next node
  data: T;
  next: Node<T> | null;

  constructor(data: T) {
    this.data = data;
    this.next = null;
  }
}

class SinglyLinkedList<T> {
  // Singly Linked List class
  public head: Node<T> | null;
  public tail: Node<T> | null;
  public length: number;

  constructor() {
    // Initialize head, tail, and length
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(data: T): SinglyLinkedList<T> {
    // Add data at the end of the list
    const node = new Node(data);

    if (!this.head) {
      // If list is empty, set head and tail to new node
      this.head = node;
    } else {
      // Otherwise, set the next of current tail to new node
      this.tail!.next = node;
    }

    // Set new node as the tail
    this.tail = node;
    // Increase the length
    this.length++;
    return this;
  }

  pop(): Node<T> | null {
    // Remove and return the last element from the list
    if (!this.head) {
      // If list is empty, return null
      return null;
    }

    let current = this.head;
    let newTail = current;

    while (current.next) {
      // Traverse the list to find the second last node
      newTail = current;
      current = current.next;
    }

    // Update tail and remove the last node
    this.tail = newTail;
    this.tail.next = null;
    this.length--;

    if (this.length === 0) {
      // If list becomes empty, reset head and tail
      this.head = null;
      this.tail = null;
    }

    return current;
  }

  traverse(): void {
    // Traverse the list and log the data of each node
    let current = this.head;

    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

  shift(): Node<T> | null {
    // Remove and return the first element from the list
    if (!this.head) {
      // If list is empty, return null
      return null;
    }

    const currHead = this.head;
    // Move head to the next node
    this.head = currHead.next;
    this.length--;

    if (this.length === 0) {
      // If list becomes empty, reset head and tail
      this.head = null;
      this.tail = null;
    }

    return currHead;
  }

  unshift(value: T): SinglyLinkedList<T> {
    // Add data at the beginning of the list
    let newHead = new Node(value);

    if (!this.head) {
      // If list is empty, set head and tail to new node
      this.tail = newHead;
    } else {
      // Otherwise, set the next of new node to current head
      newHead.next = this.head;
    }

    // Set new node as the head
    this.head = newHead;
    // Increase the length
    this.length++;
    return this;
  }

  get(index: number): Node<T> | null {
    // Get node at a specified index
    if (index < 0 || index >= this.length) {
      // If index is out of range, return null
      return null;
    }

    let selectedNode = this.head;

    for (let i = 1; i <= index; i++) {
      // Traverse the list to find the node at the given index
      selectedNode = selectedNode!.next;
    }

    return selectedNode;
  }

  search(data: T): number | null {
    // Search for the index of a specific data in the list
    let current = this.head;
    let index = 0;

    while (current) {
      // Traverse the list and check data of each node
      if (current.data === data) {
        // If data is found, return its index
        return index;
      }

      current = current.next;
      index++;
    }

    // If data is not found, return null
    return null;
  }

  set(index: number, data: T): boolean {
    // Set data of a specific node at a given index
    let nodeAtIndex = this.get(index);

    if (nodeAtIndex) {
      // If node at given index exists, update its data
      nodeAtIndex.data = data;
      return true;
    }

    // If node at given index does not exist, return false
    return false;
  }

  insert(index: number, data: T): boolean {
    // Insert new node at a specific index
    if (index < 0 || index > this.length) {
      // If index is out of range, return false
      return false;
    }

    if (index === this.length) {
      // If index is at the end, use push method
      this.push(data);
      return true;
    }

    if (index === 0) {
      // If index is at the beginning, use unshift method
      this.unshift(data);
      return true;
    }

    // Otherwise, insert new node at the specified index
    let newNode = new Node(data);
    let prevNode = this.get(index - 1);
    newNode.next = prevNode!.next;
    prevNode!.next = newNode;

    // Increase length
    this.length++;
    return true;
  }

  remove(index: number): Node<T> | null {
    // Remove node at a specific index
    if (index < 0 || index >= this.length) {
      // If index is out of range, return undefined
      return null;
    }

    if (index === 0) {
      // If index is at the beginning, use shift method
      return this.shift();
    }

    if (index === this.length - 1) {
      // If index is at the end, use pop method
      return this.pop();
    }

    // Otherwise, remove node at the specified index
    let prevNode = this.get(index - 1);
    const removedNode = prevNode!.next;
    prevNode!.next = prevNode!.next!.next;

    // Decrease length
    this.length--;
    return removedNode;
  }

  reverse(): SinglyLinkedList<T> {
    // Reverse the linked list
    let currentNode = this.head;
    let prevNode = null;
    let nextNode = null;

    while (currentNode) {
      // Traverse the list and reverse each node
      nextNode = currentNode.next;
      currentNode.next = prevNode;

      prevNode = currentNode;
      currentNode = nextNode;
    }

    // Update head and tail references
    this.tail = this.head;
    this.head = prevNode;

    return this;
  }
}

export default SinglyLinkedList;

Demo

Here is the demo code for using the implemented functionality of Singly Linked List-

JavaScript

TypeScript

// demo.js
import SinglyLinkedList from "./sll.js";

// Create a new Singly Linked List
let bigboxList = new SinglyLinkedList();

console.log("\n\n----------- Singly Linked List Push example -----------\n");

// Push items
console.log('Push - "Big" | Result: ', bigboxList.push("Big"));
console.log('Push - "Box" | Result: ', bigboxList.push("Box"));
console.log('Push - "Code" | Result: ', bigboxList.push("Code"));

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Pop example -----------\n");

console.log("Popped Item: ", bigboxList.pop());
console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

// Push items again
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");

console.log("\n\n----------- Singly Linked List Shift example -----------\n");

console.log("Shift head from list: ", bigboxList.shift());

console.log("List value: ", bigboxList);

console.log("Shift head from list: ", bigboxList.shift());

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Unshift example -----------\n");

console.log("Unshift - 'Box' | Result: ", bigboxList.unshift("Box"));

console.log("List value: ", bigboxList);

console.log("Unshift - 'Big' | Result: ", bigboxList.unshift("Big"));

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Get example -----------\n");

console.log(`Get - at index: 0 | result:`, bigboxList.get(0));
console.log(`Get - at index: 2 | result:`, bigboxList.get(2));
console.log(`Get - at index: 99 | result:`, bigboxList.get(99));

console.log("\n\n----------- Singly Linked List Set example -----------\n");

console.log(
  `Set - "New Val" at index: 0 | result: ${bigboxList.set(0, "New Val")}`
);
console.log(
  `Set - "Second" at index: 2 | result: ${bigboxList.set(2, "Second")}`
);
console.log(
  `Set - "Out bound" at index: 99 | result: ${bigboxList.set(99, "Out bound")}`
);

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Insert example -----------\n");

console.log(
  `Insert - "New Val 1" at index: 0 | result: ${bigboxList.insert(
    0,
    "New Val 1"
  )}`
);
console.log(
  `Insert - "New Val" at index: 2 | result: ${bigboxList.insert(
    2,
    "New Val 2"
  )}`
);
console.log(
  `Insert - "Out bound" at index: 99 | result: ${bigboxList.insert(
    99,
    "Out bound"
  )}`
);

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Remove example -----------\n");

// Reinitialize the list
bigboxList = new SinglyLinkedList();
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");

console.log(`Remove - form index: 2 | result:`, bigboxList.remove(2));
console.log(`Remove - from index: 0 | result:`, bigboxList.remove(0));
console.log(`Remove - form index: 99 | result:`, bigboxList.remove(99));

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Reverse example -----------\n");

// Reinitialize the list
bigboxList = new SinglyLinkedList();
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");
bigboxList.push("Singly");
bigboxList.push("Linked");
bigboxList.push("List");

console.log("List value: ");
bigboxList.traverse();

bigboxList.reverse();

console.log("List value after reverse: ");
bigboxList.traverse();

console.log("List value: ", bigboxList);

// demo.ts
import SinglyLinkedList from "./sll";

// Create a new Singly Linked List
let bigboxList = new SinglyLinkedList<string>();

console.log("\n\n----------- Singly Linked List Push example -----------\n");

// Push items
console.log('Push - "Big" | Result: ', bigboxList.push("Big"));
console.log('Push - "Box" | Result: ', bigboxList.push("Box"));
console.log('Push - "Code" | Result: ', bigboxList.push("Code"));

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Pop example -----------\n");

console.log("Popped Item: ", bigboxList.pop());
console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

console.log("Popped Item: ", bigboxList.pop());

console.log("List value: ", bigboxList);

// Push items again
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");

console.log("\n\n----------- Singly Linked List Shift example -----------\n");

console.log("Shift head from list: ", bigboxList.shift());

console.log("List value: ", bigboxList);

console.log("Shift head from list: ", bigboxList.shift());

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Unshift example -----------\n");

console.log("Unshift - 'Box' | Result: ", bigboxList.unshift("Box"));

console.log("List value: ", bigboxList);

console.log("Unshift - 'Big' | Result: ", bigboxList.unshift("Big"));

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Get example -----------\n");

console.log(`Get - at index: 0 | result:`, bigboxList.get(0));
console.log(`Get - at index: 2 | result:`, bigboxList.get(2));
console.log(`Get - at index: 99 | result:`, bigboxList.get(99));

console.log("\n\n----------- Singly Linked List Search example -----------\n");

console.log(`Search - item "Big" | result:`, bigboxList.search("Big"));
console.log(`Search - item "Code" | result:`, bigboxList.search("Code"));
console.log(
  `Search - item "Non exiting" | result:`,
  bigboxList.search("Non exiting")
);

console.log("\n\n----------- Singly Linked List Set example -----------\n");

console.log(
  `Set - "New Val" at index: 0 | result: ${bigboxList.set(0, "New Val")}`
);
console.log(
  `Set - "Second" at index: 2 | result: ${bigboxList.set(2, "Second")}`
);
console.log(
  `Set - "Out bound" at index: 99 | result: ${bigboxList.set(99, "Out bound")}`
);

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Insert example -----------\n");

console.log(
  `Insert - "New Val 1" at index: 0 | result: ${bigboxList.insert(
    0,
    "New Val 1"
  )}`
);
console.log(
  `Insert - "New Val" at index: 2 | result: ${bigboxList.insert(
    2,
    "New Val 2"
  )}`
);
console.log(
  `Insert - "Out bound" at index: 99 | result: ${bigboxList.insert(
    99,
    "Out bound"
  )}`
);

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Remove example -----------\n");

// Reinitialize the list
bigboxList = new SinglyLinkedList<string>();
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");

console.log(`Remove - form index: 2 | result:`, bigboxList.remove(2));
console.log(`Remove - from index: 0 | result:`, bigboxList.remove(0));
console.log(`Remove - form index: 99 | result:`, bigboxList.remove(99));

console.log("List value: ", bigboxList);

console.log("\n\n----------- Singly Linked List Reverse example -----------\n");

// Reinitialize the list
bigboxList = new SinglyLinkedList<string>();
bigboxList.push("Big");
bigboxList.push("Box");
bigboxList.push("Code");
bigboxList.push("Singly");
bigboxList.push("Linked");
bigboxList.push("List");

console.log("List value: ");
bigboxList.traverse();

bigboxList.reverse();

console.log("List value after reverse: ");
bigboxList.traverse();

console.log("List value: ", bigboxList);

Output:

Output of the demo code will look like below-

----------- Singly Linked List Push example -----------

Push - "Big" | Result:  SinglyLinkedList {
  head: Node { data: 'Big', next: null },
  tail: Node { data: 'Big', next: null },
  length: 1
}
Push - "Box" | Result:  SinglyLinkedList {
  head: Node { data: 'Big', next: Node { data: 'Box', next: null } },
  tail: Node { data: 'Box', next: null },
  length: 2
}
Push - "Code" | Result:  SinglyLinkedList {
  head: Node { data: 'Big', next: Node { data: 'Box', next: [Node] } },
  tail: Node { data: 'Code', next: null },
  length: 3
}
List value:  SinglyLinkedList {
  head: Node { data: 'Big', next: Node { data: 'Box', next: [Node] } },
  tail: Node { data: 'Code', next: null },
  length: 3
}


----------- Singly Linked List Pop example -----------

Popped Item:  Node { data: 'Code', next: null }
Popped Item:  Node { data: 'Box', next: null }
List value:  SinglyLinkedList {
  head: Node { data: 'Big', next: null },
  tail: Node { data: 'Big', next: null },
  length: 1
}
Popped Item:  Node { data: 'Big', next: null }
List value:  SinglyLinkedList { head: null, tail: null, length: 0 }
Popped Item:  null
List value:  SinglyLinkedList { head: null, tail: null, length: 0 }


----------- Singly Linked List Shift example -----------

Shift head from list:  Node {
  data: 'Big',
  next: Node { data: 'Box', next: Node { data: 'Code', next: null } }
}
List value:  SinglyLinkedList {
  head: Node { data: 'Box', next: Node { data: 'Code', next: null } },
  tail: Node { data: 'Code', next: null },
  length: 2
}
Shift head from list:  Node { data: 'Box', next: Node { data: 'Code', next: null } }
List value:  SinglyLinkedList {
  head: Node { data: 'Code', next: null },
  tail: Node { data: 'Code', next: null },
  length: 1
}


----------- Singly Linked List Unshift example -----------

Unshift - 'Box' | Result:  SinglyLinkedList {
  head: Node { data: 'Box', next: Node { data: 'Code', next: null } },
  tail: Node { data: 'Code', next: null },
  length: 2
}
List value:  SinglyLinkedList {
  head: Node { data: 'Box', next: Node { data: 'Code', next: null } },
  tail: Node { data: 'Code', next: null },
  length: 2
}
Unshift - 'Big' | Result:  SinglyLinkedList {
  head: Node { data: 'Big', next: Node { data: 'Box', next: [Node] } },
  tail: Node { data: 'Code', next: null },
  length: 3
}
List value:  SinglyLinkedList {
  head: Node { data: 'Big', next: Node { data: 'Box', next: [Node] } },
  tail: Node { data: 'Code', next: null },
  length: 3
}


----------- Singly Linked List Get example -----------

Get - at index: 0 | result: Node {
  data: 'Big',
  next: Node { data: 'Box', next: Node { data: 'Code', next: null } }
}
Get - at index: 2 | result: Node { data: 'Code', next: null }
Get - at index: 99 | result: null


----------- Singly Linked List Set example -----------

Set - "New Val" at index: 0 | result: true
Set - "Second" at index: 2 | result: true
Set - "Out bound" at index: 99 | result: false
List value:  SinglyLinkedList {
  head: Node { data: 'New Val', next: Node { data: 'Box', next: [Node] } },
  tail: Node { data: 'Second', next: null },
  length: 3
}


----------- Singly Linked List Insert example -----------

Insert - "New Val 1" at index: 0 | result: true
Insert - "New Val" at index: 2 | result: true
Insert - "Out bound" at index: 99 | result: false
List value:  SinglyLinkedList {
  head: Node {
    data: 'New Val 1',
    next: Node { data: 'New Val', next: [Node] }
  },
  tail: Node { data: 'Second', next: null },
  length: 5
}


----------- Singly Linked List Remove example -----------

Remove - form index: 2 | result: Node { data: 'Code', next: null }
Remove - from index: 0 | result: Node { data: 'Big', next: Node { data: 'Box', next: null } }
Remove - form index: 99 | result: undefined
List value:  SinglyLinkedList {
  head: Node { data: 'Box', next: null },
  tail: Node { data: 'Box', next: null },
  length: 1
}


----------- Singly Linked List Reverse example -----------

List value:
Big
Box
Code
Singly
Linked
List
List value after reverse:
List
Linked
Singly
Code
Box
Big
List value:  SinglyLinkedList {
  head: Node { data: 'List', next: Node { data: 'Linked', next: [Node] } },
  tail: Node { data: 'Big', next: null },
  length: 6
}

Testing

Let’s test the functionality using automated testing. Use the following code for testing.

JavaScript
TypeScript

// sll.test.js

import SinglyLinkedList from "./sll";

describe("SinglyLinkedList", () => {
  describe("Push item to SinglyLinkedList", () => {
    let singlyLinkedList;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList();
    });

    test("Should have correct head and tail", () => {
      // Initially head and tails should be null
      expect(singlyLinkedList.head).toBeNull();
      expect(singlyLinkedList.tail).toBeNull();

      singlyLinkedList.push("Big");

      expect(singlyLinkedList.head.data).toBe("Big");
      expect(singlyLinkedList.tail.data).toBe("Big");

      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");

      expect(singlyLinkedList.head.data).toBe("Big");
      expect(singlyLinkedList.tail.data).toBe("Code");
    });

    test("Should have correct length", () => {
      expect(singlyLinkedList.length).toBe(0);

      singlyLinkedList.push("Big");

      expect(singlyLinkedList.length).toBe(1);

      singlyLinkedList.push("Box");

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.push("Code");

      expect(singlyLinkedList.length).toBe(3);
    });
  });

  describe("Pop item from SinglyLinkedList", () => {
    let singlyLinkedList;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    test("Should pop item propertly", () => {
      const pop1 = singlyLinkedList.pop();

      expect(pop1.data).toBe("Code");

      const pop2 = singlyLinkedList.pop();

      expect(pop2.data).toBe("Box");

      const pop3 = singlyLinkedList.pop();

      expect(pop3.data).toBe("Big");

      const pop0 = singlyLinkedList.pop();

      expect(pop0).toBeNull();
    });

    test("Should have correct head and tail", () => {
      expect(singlyLinkedList.head.data).toBe("Big");
      expect(singlyLinkedList.tail.data).toBe("Code");

      singlyLinkedList.pop();

      expect(singlyLinkedList.head.data).toBe("Big");
      expect(singlyLinkedList.tail.data).toBe("Box");

      singlyLinkedList.pop();

      expect(singlyLinkedList.head.data).toBe("Big");
      expect(singlyLinkedList.tail.data).toBe("Big");

      singlyLinkedList.pop();

      expect(singlyLinkedList.head).toBeNull();
      expect(singlyLinkedList.tail).toBeNull();
    });

    test("Should have correct length", () => {
      const pop1 = singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(2);

      const pop2 = singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(1);

      const pop3 = singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(0);

      const pop0 = singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(0);
    });
  });

  describe("Shift item from SinglyLinkedList", () => {
    let singlyLinkedList;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    test("Should shift head propertly", () => {
      const shift1 = singlyLinkedList.shift();

      expect(shift1.data).toBe("Big");

      const shift2 = singlyLinkedList.shift();

      expect(shift2.data).toBe("Box");

      const shift3 = singlyLinkedList.pop();

      expect(shift3.data).toBe("Code");

      const shift0 = singlyLinkedList.pop();

      expect(shift0).toBeNull();
    });

    test("Should have correct head and tail", () => {
      singlyLinkedList.shift();

      expect(singlyLinkedList.head.data).toBe("Box");
      expect(singlyLinkedList.tail.data).toBe("Code");

      singlyLinkedList.shift();

      expect(singlyLinkedList.head.data).toBe("Code");
      expect(singlyLinkedList.tail.data).toBe("Code");

      singlyLinkedList.shift();

      expect(singlyLinkedList.head).toBeNull();
      expect(singlyLinkedList.tail).toBeNull();
    });

    test("Should have correct length", () => {
      singlyLinkedList.shift();

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.shift();

      expect(singlyLinkedList.length).toBe(1);

      singlyLinkedList.shift();

      expect(singlyLinkedList.length).toBe(0);

      // Try to pop one more time
      singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(0);
    });
  });

  describe("Unhift item from SinglyLinkedList", () => {
    let singlyLinkedList;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList();
    });

    test("Should unhift head propertly", () => {
      const unshift1 = singlyLinkedList.unshift("Code");

      expect(unshift1).not.toBeNull();

      const unshift2 = singlyLinkedList.unshift("Box");

      expect(unshift2).not.toBeNull();
    });

    test("Should have correct head and tail", () => {
      singlyLinkedList.unshift("Code");

      expect(singlyLinkedList.head.data).toBe("Code");
      expect(singlyLinkedList.tail.data).toBe("Code");

      singlyLinkedList.unshift("Box");

      expect(singlyLinkedList.head.data).toBe("Box");
      expect(singlyLinkedList.tail.data).toBe("Code");

      singlyLinkedList.unshift("Big");

      expect(singlyLinkedList.head.data).toBe("Big");
      expect(singlyLinkedList.tail.data).toBe("Code");
    });

    test("Should have correct length", () => {
      singlyLinkedList.unshift("Code");

      expect(singlyLinkedList.length).toBe(1);

      singlyLinkedList.unshift("Box");

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.unshift("Big");

      expect(singlyLinkedList.length).toBe(3);
    });
  });

  describe("Get item from SinglyLinkedList by index", () => {
    let singlyLinkedList;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    test("Should return node at specific index", () => {
      const node0 = singlyLinkedList.get(0);

      expect(node0.data).toBe("Big");

      const node2 = singlyLinkedList.get(2);

      expect(node2.data).toBe("Code");
    });

    test("Should return null for invalid index", () => {
      const nodenve = singlyLinkedList.get(-1);

      expect(nodenve).toBeNull();

      const nodelarge = singlyLinkedList.get(999999);

      expect(nodelarge).toBeNull();
    });
  });

  describe("Set item to SinglyLinkedList by index", () => {
    let singlyLinkedList;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    test("Should set value at node properly", () => {
      const set0 = singlyLinkedList.set(0, "New Val");

      expect(set0).toBeTruthy();

      const get0 = singlyLinkedList.get(0);

      expect(get0.data).toBe("New Val");

      const set2 = singlyLinkedList.set(2, "Second");

      expect(set2).toBeTruthy();

      const get2 = singlyLinkedList.get(2);

      expect(get2.data).toBe("Second");

      const setN = singlyLinkedList.set(99, "Out Bound");

      expect(setN).toBeFalsy();
    });

    test("Should handle empty list without any exception", () => {
      singlyLinkedList = new SinglyLinkedList();

      const set0 = singlyLinkedList.set(0, "Out Bound");

      expect(set0).toBeFalsy();
    });
  });

  describe("Insert item to SinglyLinkedList by index", () => {
    let singlyLinkedList;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList();
    });

    test("Should insert data at index", () => {
      const insert0 = singlyLinkedList.insert(0, "Big");

      expect(insert0).toBeTruthy();

      const get0 = singlyLinkedList.get(0);

      expect(get0.data).toBe("Big");

      const insert1 = singlyLinkedList.insert(1, "Code");

      expect(insert1).toBeTruthy();

      const get1 = singlyLinkedList.get(1);

      expect(get1.data).toBe("Code");

      const insert1_1 = singlyLinkedList.insert(1, "Box");

      expect(insert1_1).toBeTruthy();

      const get1_1 = singlyLinkedList.get(1);

      expect(get1_1.data).toBe("Box");

      const get1_2 = singlyLinkedList.get(2);

      expect(get1_2.data).toBe("Code");

      const setN = singlyLinkedList.insert(99, "Out Bound");

      expect(setN).toBeFalsy();
    });

    test("Should have proper length after insert", () => {
      singlyLinkedList.insert(0, "Big");

      expect(singlyLinkedList.length).toBe(1);

      singlyLinkedList.insert(1, "Code");

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.insert(1, "Box");

      expect(singlyLinkedList.length).toBe(3);

      singlyLinkedList.insert(99, "Out Bound");

      expect(singlyLinkedList.length).toBe(3);
    });
  });

  describe("Remove item from SinglyLinkedList by index", () => {
    let singlyLinkedList;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    test("Should remove data at index", () => {
      const remove2 = singlyLinkedList.remove(2);

      expect(remove2.data).toBe("Code");

      const get2 = singlyLinkedList.get(2);

      expect(get2).toBeNull();

      const remove0 = singlyLinkedList.remove(0);

      expect(remove0.data).toBe("Big");

      const get0 = singlyLinkedList.get(0);

      expect(get0.data).toBe("Box");

      const removeN = singlyLinkedList.remove(99);

      expect(removeN).toBeFalsy();
    });

    test("Should have proper length after remove", () => {
      singlyLinkedList.remove(1);

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.remove(99);

      expect(singlyLinkedList.length).toBe(2);
    });
  });

  describe("Reverse SinglyLinkedList", () => {
    let singlyLinkedList;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
      singlyLinkedList.push("Singly");
      singlyLinkedList.push("Linked");
      singlyLinkedList.push("List");
    });

    test("Should set head properly", () => {
      singlyLinkedList.reverse();

      expect(singlyLinkedList.head.data).toBe("List");
    });

    test("Should set tail properly", () => {
      singlyLinkedList.reverse();

      expect(singlyLinkedList.tail.data).toBe("Big");
    });

    test("Should set all elements properly", () => {
      singlyLinkedList.reverse();

      const get1 = singlyLinkedList.get(1);

      expect(get1.data).toBe("Linked");

      const get2 = singlyLinkedList.get(2);

      expect(get2.data).toBe("Singly");

      const get4 = singlyLinkedList.get(4);

      expect(get4.data).toBe("Box");
    });

    test("Should not change the length", () => {
      singlyLinkedList.reverse();

      expect(singlyLinkedList.length).toBe(6);
    });
  });
});

// sll.test.ts
import { describe, it, beforeEach, expect } from 'vitest';
import SinglyLinkedList from "./sll";

describe("SinglyLinkedList", () => {
  describe("Push item to SinglyLinkedList", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
    });

    it("Should have correct head and tail", () => {
      // Initially head and tails should be null
      expect(singlyLinkedList.head).toBeNull();
      expect(singlyLinkedList.tail).toBeNull();

      singlyLinkedList.push("Big");

      expect(singlyLinkedList.head!.data).toBe("Big");
      expect(singlyLinkedList.tail!.data).toBe("Big");

      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");

      expect(singlyLinkedList.head!.data).toBe("Big");
      expect(singlyLinkedList.tail!.data).toBe("Code");
    });

    it("Should have correct length", () => {
      expect(singlyLinkedList.length).toBe(0);

      singlyLinkedList.push("Big");

      expect(singlyLinkedList.length).toBe(1);

      singlyLinkedList.push("Box");

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.push("Code");

      expect(singlyLinkedList.length).toBe(3);
    });
  });

  describe("Pop item from SinglyLinkedList", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    it("Should pop item properly", () => {
      const pop1 = singlyLinkedList.pop();

      expect(pop1!.data).toBe("Code");

      const pop2 = singlyLinkedList.pop();

      expect(pop2!.data).toBe("Box");

      const pop3 = singlyLinkedList.pop();

      expect(pop3!.data).toBe("Big");

      const pop0 = singlyLinkedList.pop();

      expect(pop0).toBeNull();
    });

    it("Should have correct head and tail", () => {
      expect(singlyLinkedList.head!.data).toBe("Big");
      expect(singlyLinkedList.tail!.data).toBe("Code");

      singlyLinkedList.pop();

      expect(singlyLinkedList.head!.data).toBe("Big");
      expect(singlyLinkedList.tail!.data).toBe("Box");

      singlyLinkedList.pop();

      expect(singlyLinkedList.head!.data).toBe("Big");
      expect(singlyLinkedList.tail!.data).toBe("Big");

      singlyLinkedList.pop();

      expect(singlyLinkedList.head).toBeNull();
      expect(singlyLinkedList.tail).toBeNull();
    });

    it("Should have correct length", () => {
      const pop1 = singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(2);

      const pop2 = singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(1);

      const pop3 = singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(0);

      const pop0 = singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(0);
    });
  });

  describe("Shift item from SinglyLinkedList", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    it("Should shift head properly", () => {
      const shift1 = singlyLinkedList.shift();

      expect(shift1!.data).toBe("Big");

      const shift2 = singlyLinkedList.shift();

      expect(shift2!.data).toBe("Box");

      const shift3 = singlyLinkedList.pop();

      expect(shift3!.data).toBe("Code");

      const shift0 = singlyLinkedList.pop();

      expect(shift0).toBeNull();
    });

    it("Should have correct head and tail", () => {
      singlyLinkedList.shift();

      expect(singlyLinkedList.head!.data).toBe("Box");
      expect(singlyLinkedList.tail!.data).toBe("Code");

      singlyLinkedList.shift();

      expect(singlyLinkedList.head!.data).toBe("Code");
      expect(singlyLinkedList.tail!.data).toBe("Code");

      singlyLinkedList.shift();

      expect(singlyLinkedList.head).toBeNull();
      expect(singlyLinkedList.tail).toBeNull();
    });

    it("Should have correct length", () => {
      singlyLinkedList.shift();

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.shift();

      expect(singlyLinkedList.length).toBe(1);

      singlyLinkedList.shift();

      expect(singlyLinkedList.length).toBe(0);

      // Try to pop one more time
      singlyLinkedList.pop();

      expect(singlyLinkedList.length).toBe(0);
    });
  });

  describe("Unshift item from SinglyLinkedList", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
    });

    it("Should unshift head properly", () => {
      const unshift1 = singlyLinkedList.unshift("Code");

      expect(unshift1).not.toBeNull();

      const unshift2 = singlyLinkedList.unshift("Box");

      expect(unshift2).not.toBeNull();
    });

    it("Should have correct head and tail", () => {
      singlyLinkedList.unshift("Code");

      expect(singlyLinkedList.head!.data).toBe("Code");
      expect(singlyLinkedList.tail!.data).toBe("Code");

      singlyLinkedList.unshift("Box");

      expect(singlyLinkedList.head!.data).toBe("Box");
      expect(singlyLinkedList.tail!.data).toBe("Code");

      singlyLinkedList.unshift("Big");

      expect(singlyLinkedList.head!.data).toBe("Big");
      expect(singlyLinkedList.tail!.data).toBe("Code");
    });

    it("Should have correct length", () => {
      singlyLinkedList.unshift("Code");

      expect(singlyLinkedList.length).toBe(1);

      singlyLinkedList.unshift("Box");

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.unshift("Big");

      expect(singlyLinkedList.length).toBe(3);
    });
  });

  describe("Get item from SinglyLinkedList by index", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    it("Should return node at specific index", () => {
      const node0 = singlyLinkedList.get(0);

      expect(node0!.data).toBe("Big");

      const node2 = singlyLinkedList.get(2);

      expect(node2!.data).toBe("Code");
    });

    it("Should return null for invalid index", () => {
      const nodenve = singlyLinkedList.get(-1);

      expect(nodenve).toBeNull();

      const nodelarge = singlyLinkedList.get(999999);

      expect(nodelarge).toBeNull();
    });
  });

  describe("Search item in SinglyLinkedList", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    it("Should return correct index of the item", () => {
      const search0 = singlyLinkedList.search("Big");

      expect(search0).toBe(0);

      const search2 = singlyLinkedList.search("Code");

      expect(search2).toBe(2);
    });

    it("Should return null for non existing item", () => {
      const searchResult = singlyLinkedList.search("Non existing item");

      expect(searchResult).toBeNull();
    });
  });

  describe("Set item to SinglyLinkedList by index", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    it("Should set value at node properly", () => {
      const set0 = singlyLinkedList.set(0, "New Val");

      expect(set0).toBeTruthy();

      const get0 = singlyLinkedList.get(0);

      expect(get0!.data).toBe("New Val");

      const set2 = singlyLinkedList.set(2, "Second");

      expect(set2).toBeTruthy();

      const get2 = singlyLinkedList.get(2);

      expect(get2!.data).toBe("Second");

      const setN = singlyLinkedList.set(99, "Out Bound");

      expect(setN).toBeFalsy();
    });

    it("Should handle empty list without any exception", () => {
      singlyLinkedList = new SinglyLinkedList<string>();

      const set0 = singlyLinkedList.set(0, "Out Bound");

      expect(set0).toBeFalsy();
    });
  });

  describe("Insert item to SinglyLinkedList by index", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
    });

    it("Should insert data at index", () => {
      const insert0 = singlyLinkedList.insert(0, "Big");

      expect(insert0).toBeTruthy();

      const get0 = singlyLinkedList.get(0);

      expect(get0!.data).toBe("Big");

      const insert1 = singlyLinkedList.insert(1, "Code");

      expect(insert1).toBeTruthy();

      const get1 = singlyLinkedList.get(1);

      expect(get1!.data).toBe("Code");

      const insert1_1 = singlyLinkedList.insert(1, "Box");

      expect(insert1_1).toBeTruthy();

      const get1_1 = singlyLinkedList.get(1);

      expect(get1_1!.data).toBe("Box");

      const get1_2 = singlyLinkedList.get(2);

      expect(get1_2!.data).toBe("Code");

      const setN = singlyLinkedList.insert(99, "Out Bound");

      expect(setN).toBeFalsy();
    });

    it("Should have proper length after insert", () => {
      singlyLinkedList.insert(0, "Big");

      expect(singlyLinkedList.length).toBe(1);

      singlyLinkedList.insert(1, "Code");

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.insert(1, "Box");

      expect(singlyLinkedList.length).toBe(3);

      singlyLinkedList.insert(99, "Out Bound");

      expect(singlyLinkedList.length).toBe(3);
    });
  });

  describe("Remove item from SinglyLinkedList by index", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
    });

    it("Should remove data at index", () => {
      const remove2 = singlyLinkedList.remove(2);

      expect(remove2!.data).toBe("Code");

      const get2 = singlyLinkedList.get(2);

      expect(get2).toBeNull();

      const remove0 = singlyLinkedList.remove(0);

      expect(remove0!.data).toBe("Big");

      const get0 = singlyLinkedList.get(0);

      expect(get0!.data).toBe("Box");

      const removeN = singlyLinkedList.remove(99);

      expect(removeN).toBeFalsy();
    });

    it("Should have proper length after remove", () => {
      singlyLinkedList.remove(1);

      expect(singlyLinkedList.length).toBe(2);

      singlyLinkedList.remove(99);

      expect(singlyLinkedList.length).toBe(2);
    });
  });

  describe("Reverse SinglyLinkedList", () => {
    let singlyLinkedList: SinglyLinkedList<string>;

    beforeEach(() => {
      singlyLinkedList = new SinglyLinkedList<string>();
      singlyLinkedList.push("Big");
      singlyLinkedList.push("Box");
      singlyLinkedList.push("Code");
      singlyLinkedList.push("Singly");
      singlyLinkedList.push("Linked");
      singlyLinkedList.push("List");
    });

    it("Should set head properly", () => {
      singlyLinkedList.reverse();

      expect(singlyLinkedList.head!.data).toBe("List");
    });

    it("Should set tail properly", () => {
      singlyLinkedList.reverse();

      expect(singlyLinkedList.tail!.data).toBe("Big");
    });

    it("Should set all elements properly", () => {
      singlyLinkedList.reverse();

      const get1 = singlyLinkedList.get(1);

      expect(get1!.data).toBe("Linked");

      const get2 = singlyLinkedList.get(2);

      expect(get2!.data).toBe("Singly");

      const get4 = singlyLinkedList.get(4);

      expect(get4!.data).toBe("Box");
    });

    it("Should not change the length", () => {
      singlyLinkedList.reverse();

      expect(singlyLinkedList.length).toBe(6);
    });
  });
});

Time Complexity

The time complexity of operation on a Singly Linked List is as below-

Operation	Complexity
Insertion	O(1)
Removal	O(N)
Search	O(N)
Access element	O(N)

Source Code

Use the following links to get the source code used in this article-

Source Code of	Implementation Code	Demo Code	Test Code
JavaScript Implementation	GitHub	GitHub	GitHub
TypeScript Implementation	GitHub	GitHub	GitHub

Related Data Structures

Command	Details
Doubly Linked List	Doubly Linked List Detail

Other Code Implementations

Use the following links to check the Singly Link List implementation in other programming languages-

Implementation

Step #1: Node Class

Step #2: Linked List Class

Step #3: Push (Node to the end)

Step #4: Pop (Last Node)

Step #5: Traverse all Nodes

Step #6: Shift Head

Step #7: Unshift Head

Step #8: Get Node by Index

Step #9: Search by data

Step #10: Set data at Node by Index

Step #11: Insert Data at Specific Index

Step #12: Remove Item from Specific Index

Step #13: Reverse a Singly Linked List

Full Implementation Code

Demo

Testing

Time Complexity

Source Code

Related Data Structures

Other Code Implementations

Leave a Comment Cancel reply