LinkedList

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}
 
class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
 
  // Insert node at the beginning of the list
  unshift(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    if (!this.tail) {
      this.tail = newNode;
    }
    this.size++;
  }
 
  // Insert node at the end of the list
  push(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }
    this.tail = newNode;
    this.size++;
  }
 
  // Remove and return the first node in the list
  shift() {
    if (!this.head) {
      return null;
    }
    const removedNode = this.head;
    this.head = this.head.next;
    if (!this.head) {
      this.tail = null;
    }
    this.size--;
    return removedNode.data;
  }
 
  // Remove and return the last node in the list
  pop() {
    if (!this.head) {
      return null;
    }
    let removedNode;
    if (this.head === this.tail) {
      removedNode = this.head;
      this.head = null;
      this.tail = null;
    } else {
      let current = this.head;
      while (current.next !== this.tail) {
        current = current.next;
      }
      removedNode = this.tail;
      this.tail = current;
      this.tail.next = null;
    }
    this.size--;
    return removedNode.data;
  }
 
  // Get the node at the given index (0-based)
  get(index) {
    if (index < 0 || index >= this.size) {
      return null;
    }
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    return current.data;
  }
 
  // Remove the node at the given index (0-based)
  remove(index) {
    if (index < 0 || index >= this.size) {
      return null;
    }
    let removedNode;
    if (index === 0) {
      removedNode = this.head;
      this.head = this.head.next;
      if (!this.head) {
        this.tail = null;
      }
    } else {
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
        current = current.next;
      }
      removedNode = current.next;
      current.next = current.next.next;
      if (!current.next) {
        this.tail = current;
      }
    }
    this.size--;
    return removedNode.data;
  }
 
  // Return the current size of the list
  getSize() {
    return this.size;
  }
 
  // Check if the list is empty
  isEmpty() {
    return this.size === 0;
  }
}