// Implementation of single link list

// Author: Sheary Tan

class Node {

constructor(val) {

this.val = val;

this.next = null;

}

}

class SinglyList {

constructor() {

// Initializing...

// There is nothing at the beginning so

// the head & the tail should be empty,

// and the length should be zero too

this.head = null;

this.tail = null;

this.length = 0;

}

// 1st method: push (push the val into the end of the list)

push(val) {

// Firstly, we have to accept a new value

var newNode = new Node(val);

// If there is no head, means there is nothing on the list,

// set the head & tail pointers to this value.

if(!this.head) {

this.head = newNode;

this.tail = newNode;

} else {

// If there is value existed, assign the newNode to the next value

// of the current existing value

this.tail.next = newNode;

// Update the tail to it!

this.tail = newNode;

}

// Increment the length and return the newly created link-list

this.length++;

return this;

}

// 2nd method: pop (remove the last item)

pop() {

// If there is nothing on the list, return undefined

if (!this.head) return undefined;

// Loop through to find the last item

var current = this.head;

var newTail = current;

while(current.next) {

newTail = current;

current = current.next

}

// Set the found tail to tail

this.tail = newTail;

// The next one will be null since we

// would like to remove it

this.tail.next = null;

// Decrease the length

this.length--;

// If there is nothing left after removing

// set the head and tail to be null

if(this.length === 0) {

this.head = null;

this.tail = null;

}

return current;

}

// 3rd method: shift (remove the first item)

shift() {

// If there is no nothing on the list, return undefined

if(!this.head) return undefined;

// Store the current head in a new variable

var currentHead = this.head;

// Shift the head to the next value of the currentHead

this.head = currentHead.next;

// Decrement the length since we have removed the head

this.length--;

if(this.length === 0) {

this.head = null;

this.tail = null;

}

return currentHead;

}

// 4th method: unshift (add item to the beginning )

unshift(val) {

// Initialize the value to a new node;

var newNode = new Node(val);

// If there is nothing on the list, set the head and tail

// point to that new node

if(!this.head) {

this.head = newNode;

this.tail = newNode;

} else {

// In order to set the head value points to the head,

// we have to set the current head to the next item of newNode

newNode.next = this.head;

// and now we can assign the head to newNode!

this.head = newNode

}

// Increment the length after adding the new head

this.length++;

return this;

}

// 5th method: get

get(i) {

// get accepts an index in and find the specific value

// If i is less than zero, or greater and equal to the length

// of the current link list, return null;

if(i < 0 || i >= this.length) return null;

// Use the counter to find the value

var counter = 0;

var current = this.head;

while(counter !== i) {

current = current.next;

counter++

}

// Found it and return

return current

}

// 6th method: set

// Use the given index to find the target value and change it with the new

// given value

set(i, val) {

var targetNode = this.get(i);

if(targetNode) {

targetNode.val = val;

return true;

}

return false;

}

// 8th method: remove (from any index)

remove(i) {

// Check if there's anything on the list

if(i < 0 || i >= this.length) return undefined;

if(i === 0) return this.shift();

if(i === this.length - 1) return this.pop();

// Get the previous item of the target

var previousTarget = this.get(i - 1);

// Since we've got the previous item of the target,

// we now can remove the target by setting the next item of previousTarget

// to the next item of "removed"

var removed = previousTarget.next;

previousTarget.next = removed.next

// Decrease the length

this.length--;

return removed;

}

// 9th method: reverse

reverse() {

// Firstly we have to set the head to the tail,

// and the tail to the head

var target = this.head;

this.head = this.tail;

this.tail = target;

// Now we have to re-arrange those next & previous

// items of the list

var next;

var prev = null;

// Loop through every single item on the list

for(let i = 0; i < this.length; i++) {

// This part is a bit confusing, let's take an example

// Example = [1, 2, 3, 4, 5], T = target, P = previous, N = next

next = target.next;

// Firstly, the target is 1

// [1, 2, 3, 4, 5]

// T

// And target.next is 2

// [1, 2, 3, 4, 5]

// T N

target.next = prev;

// Remember our target is 1 & prev is null? Now it said the next item of

// 1 is null,

// 1 -> null

prev = target;

// Now we're setting the "prev = null" to the target value

// which now equals to "prev = 1"

// [1, 2, 3, 4, 5]

// P N

target = next;

// And lastly we set the "next" value to be T

// [1, 2, 3, 4, 5]

// P T

// So the cycle repeats again, now let's go through 1 more cycle

// [1, 2, 3, 4, 5]

// P T

// next = target.next

// [1, 2, 3, 4, 5]

// P T N

// target.next = prev

// Remember we have the list (1 -> null)?

// now target.next = prev means the next item of 2 is 1

// 2 -> 1 -> null

// prev = target

// Now 2 is prev

// [1, 2, 3, 4, 5]

// P N

// target = next

// And 3 is now the target

// [1, 2, 3, 4, 5]

// P T

// And the cycle repeats again until the target reach the end of the list...

}

return this;

}

// 10th method: insert

insert(i, val) {

// Check the requirements

if(i < 0 || i >= this.length) return false;

if(i === this.length) return !!this.push(val);

if(i === 0) return !!this.unshift(val);

// Initialize a new node

var newNode = new Node(val);

// Get the previous node of newNode

var prevNode = this.get(i - 1);

// Remember we haven't insert the newNode into the list!

// And also store the next item of prevNode in a temporary variable

// because we are going to set it to the next item of newNode later

var temp = prevNode.next;

// Now we can set the next item of prevNode to newNode

prevNode.next = newNode;

// Then the next item of newNode will be the temporary item we store

newNode.next = temp;

// Increment the length

this.length++;

return true;

}

}