JavaScript Interview Question: Linked List

linked-list.js

/*
Linked List example.
*/

/**
 * Node class
 * Contains two properties and no methods.
 * data - The data to be stored in a single node.
 * next - The reference to the next node in the chain.
 */
class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

/**
 * LinkedList class
 * Contains a single property to hold the first node in the chain.
 * Contains all methods to operate on the node chain.
 */
class LinkedList {
  
  //The constructor should accept no args. The head property should be initialized to null.
  constructor() {
    this.head = null;
  }
  
  //Insert a node at the beginning of the chain. 
  insertFirst(data) {
    this.insertAt(data, 0);
  }
  
  //Insert a node at the end of the chain.
  insertLast(data) {
    this.insertAt(data, this.size());
  }
  
  //Count the number of nodes in the chain.
  size() {
    let node = this.head;
    let counter = 0;
    while (node !== null) {
      node = node.next;
      counter++;
    }
    
    return counter;
  }
  
  //Clear the reference to the chain from the Linked List.
  clear() {
    this.head = null;
  }
  
  //Remove the first node in the chain.
  removeFirst() {
    this.removeAt(0);
  }
  
  //Remove last
  removeLast() {
    this.removeAt(this.size() - 1);
  }
  
  //Return the first node in the chain.
  getFirst() {
    return this.getAt(0);
  }
  
  //Return the last node in the chain.
  getLast() {
    return this.getAt(this.size() - 1);
  }
  
  //Get a node at a specified index.
  getAt(index) {
    let counter = 0;
    let node = this.head;
    
    while (node) {
      if (counter === index) {
        return node;
      }
      
      counter++;
      node = node.next;
    }
    
    return null;
  }
  
  //Remove a node at a specified index.
  removeAt(index) {
    
    //No nodes exist.
    if (!this.head) {
      return;
    }
    
    //Remove the first node in the chain.
    if (index === 0) {
      this.head = this.head.next;
      return;
    }
    
    //Remove the node at index provided.
    const previous = this.getAt(index - 1);
    
    //Exit function if the index is out of bounds.
    if (!previous || !previous.next) {
      return;
    }
    
    //Remove the node at the specified index.
    previous.next = previous.next.next;
    
  }
  
  //Insert a node at a specified index.
  insertAt(data, index) {
    
    //No nodes exist. Add as first node.
    if (!this.head) {
      this.head = new Node(data);
      return;
    }
    
    //Insert this as the first node.
    if (index === 0) {
      this.head = new Node(data, this.head);
      return;
    }
    
    //Insert the node at some point in the chain.
    const previous = this.getAt(index - 1) || this.getLast();
    previous.next = new Node(data, previous.next);
  }
  
  //Iterator
  forEach(fn) {
    let node = this.head;
    let counter = 0;
    
    while(node) {
      fn(node, counter++);
      node = node.next;
    }
  }
  
  //For...of Iterator.
  *[Symbol.iterator]() {
    let node = this.head;
    
    while(node) {
      yield node;
      node = node.next;
    }
  }
  
  //Find the midpoint without using a counter.
  midPoint() { 
    let fast = this.head;
    let slow = this.head;
    
    while (fast.next && fast.next.next) {
      fast = fast.next.next;
      slow = slow.next;
    }
    
    return slow;
  }
}

function circular(list) {
  let slow = list.getFirst();
  let fast = list.getFirst();
  
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
    
    if (slow === fast) {
      return true;
    }
  }
  
  return false;
}

function fromLast(list, n) {
    let slow = list.getFirst();
    let fast = list.getFirst();

    while (n > 0) {
        fast = fast.next;
        n--;
    }

    while (fast.next) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}

(() => {
  //Create a linked list.
  let linkedList = new LinkedList();
  
  //Insert several nodes.
  linkedList.insertFirst('E');
  linkedList.insertFirst('D');
  linkedList.insertFirst('C');
  linkedList.insertFirst('B');
  linkedList.insertFirst('A');
  
  //Get the first node.
  console.log('GET FIRST', linkedList.getFirst()); //Node with "A"
  
  //Get the first node.
  console.log('GET THIRD', linkedList.getAt(2)); //Node with "C"
  
  //Get the last node.
  console.log('GET LAST', linkedList.getLast()); //Node with "E"
  
  //Test Insert Last.
  linkedList.insertLast('F');
  console.log('TEST INSERT LAST', linkedList.getLast()); //Node with "F"
  
  //Test Remove Last.
  linkedList.removeLast();
  console.log('TEST REMOVE LAST', linkedList.getLast()); //No longer "F", now "E"
  
  //Test forEach.
  linkedList.forEach((element, index) => {
    console.log('The element data at position ' + index + ' is: ' + element.data);
  });
  
  //Test for...of.
  for (let element of linkedList) {
    console.log('FOR OF: ', element.data);
  }
  
  //Test Remove First
  linkedList.removeFirst();
  console.log('TEST REMOVE FIRST', linkedList.getFirst()); //No longer "A", "now "B"
  
  //Test clear.
  linkedList.clear();
  console.log('TEST CLEAR', linkedList.getFirst()); //Should be null
})();