Skip to content

Instantly share code, notes, and snippets.

@GreggSetzer
Last active July 27, 2018 13:42
Show Gist options
  • Save GreggSetzer/de417189b1a0e15e475dfff63be041bb to your computer and use it in GitHub Desktop.
Save GreggSetzer/de417189b1a0e15e475dfff63be041bb to your computer and use it in GitHub Desktop.
JavaScript Interview Question: Linked List
/*
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
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment