Data Structure: Singly Linked List

// 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;