Singly Linked Lists

                   -Intro to Singly Linked List 
                   -Singly Linked List: Push
                   -Singly Linked List: Pop
                   -Singly Linked List: Shift
                   -Singly Linked List: Unshift
                   -Singly Linked List: Get Intro
                   -Singly Linked List: Set Intro
                   -Singly Linked List: Insert Intro
                   -Singly Linked List: Remove Intro
                   -Singly Linked List: Reverse Intro
                   -Singly Linked List: BIG O Complexity

Intro to Singly Linked List

Linked List is a data structure that contains a head, tail and length property. Linked Lists consists of nodes, and each node has a value and a pointer to another node or null.

Always asking for the next item in the list.

A bunch of nodes pointing to other nodes.

Singly linked list are only connected in a single direction.

A fun resource to see algorithm and data structures
https://visualgo.net/en

Linked List Compared to Arrays

List

Do not have indexes
Connected via nodes with a next pointer 
Random access is not allowed

Arrays

Indexed in order
Insertion and deletion can be expensive 
Can quickly be accessed at a specific index

Singly Linked List: Push

The push() method adds new items to the end of an array and returns the new length.

Push Pseudocode

Function should accept a value
Create a new node using the value passed to the function
If there is no head property on the list, set the head and tail to be the newly created node
Otherwise set the next property on the tail to be the new node
and set the tail property on the list to be the newly created node
Increment the length by one


class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
}

var list = new SinglyLinkedList()
// list.push("HELLO")
// list.push("GOODBYE")

Singly Linked List: Pop

The pop() method removes the last element of an array and returns that element.

Pop Pseudocode
If there are no nodes in the list, return undefined
Loop through the list until you reach the tail
Set the next property of the 2nd to last node to be null
Set the tail to be the 2nd to last node
Decrement the length of the list by 1
Return the value of the node removed




    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }

Singly Linked List: Shift

The shift() removes a new node from the beginning of the Linked List.

Shift Pseudocode
If there are no nodes, return undefined
Store the current head property in a variable
Set the head property to be the current head next property
Decrement the length by 1
Return the value of the node removed


   shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
}

Singly Linked List: Unshift

The unshift() adds a new node to the beginning of the Linked List.

Unshift Pseudocode
Function should accept a value
Create a new node using the value passed to the function
If there is no head property on the list, set the head and tail to be the newly created node
Otherwise set the newly created node next property to be the current head property on the list
Set the head property on the list to be that newly created node
Increment the length of the list by 1
Return the linked list


    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        this.length++;
        return this;
    }
}

Singly Linked List: Get Intro

The get() retrieves a node by its position in the Linked List.
Get Pseudocode

Function should accept an index
If the index is less than zero or greater than or equal to the length of the list, return null
Loop through the list until you reach the index and return the node at that specific index


get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }

Singly Linked List: Set Intro

The set() changes the value of a node based on its position in the Linked List.

Set Pseudocode

Function should accept a value and an index
Use get function to find specific node
If the node is not found, return false
If the node is found, set the value of that node to be the value passed to the function and return true


  set(index, val){
        var foundNode = this.get(index);
        if(foundNode){
            foundNode.val = val;
            return true;
        }
        return false;
    }

Singly Linked List: Insert Intro

The insert() adds a node to the Linked List at a specific position.

Insert Pseudocode

If the index is less than zero or greater than the length, return false
If the index is the same as the length, push a new node to the end of the list
If the index is 0, unshift a new node to the start of the list
Otherwise, using the get method, access the node at the index -1
Set the next property on that node to be the new node
Set the next property on the new node to be the previous next


    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);

        var newNode = new Node(val);
        var prev = this.get(index - 1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }

Singly Linked List: Remove Intro

The remove() removes a node from the Linked List at a specific position

Remove Pseudocode

If the index is less than zero or greater than the length, return undefined
If the index is the same as the length - 1, pop
If the index is 0, shift
Otherwise, using the get method, access the node at the index -1
Set the next property on that node to be the next of the next node
Decrement the length
Return the value of the node removed


    remove(index){
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length - 1) return this.pop();
        var previousNode = this.get(index - 1);
        var removed = previousNode.next;
        previousNode.next = removed.next;
        this.length--;
        return removed;
    }

Singly Linked List: Reverse Intro

The reverse() reveres the Linked List



   reverse(){
      var node = this.head;
      this.head = this.tail;
      this.tail = node;
      var next;
      var prev = null;
      for(var i = 0; i < this.length; i++){
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
      }
      return this;
    }

Final Code


class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.head){
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
        return this;
    }
    pop(){
        if(!this.head) return undefined;
        var current = this.head;
        var newTail = current;
        while(current.next){
            newTail = current;
            current = current.next;
        }
        this.tail = newTail;
        this.tail.next = null;
        this.length--;
        if(this.length === 0){
            this.head = null;
            this.tail = null;
        }
        return current;
    }
    shift(){
        if(!this.head) return undefined;
        var currentHead = this.head;
        this.head = currentHead.next;
        this.length--;
        if(this.length === 0){
            this.tail = null;
        }
        return currentHead;
    }
    unshift(val){
        var newNode = new Node(val);
        if(!this.head) {
            this.head = newNode;
            this.tail = this.head;
        }
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return this;
    }
    get(index){
        if(index < 0 || index >= this.length) return null;
        var counter = 0;
        var current = this.head;
        while(counter !== index){
            current = current.next;
            counter++;
        }
        return current;
    }
    set(index, val){
        var foundNode = this.get(index);
        if(foundNode){
            foundNode.val = val;
            return true;
        }
        return false;
    }
    insert(index, val){
        if(index < 0 || index > this.length) return false;
        if(index === this.length) return !!this.push(val);
        if(index === 0) return !!this.unshift(val);

        var newNode = new Node(val);
        var prev = this.get(index - 1);
        var temp = prev.next;
        prev.next = newNode;
        newNode.next = temp;
        this.length++;
        return true;
    }
    remove(index){
        if(index < 0 || index >= this.length) return undefined;
        if(index === 0) return this.shift();
        if(index === this.length - 1) return this.pop();
        var previousNode = this.get(index - 1);
        var removed = previousNode.next;
        previousNode.next = removed.next;
        this.length--;
        return removed;
    }
    reverse(){
      var node = this.head;
      this.head = this.tail;
      this.tail = node;
      var next;
      var prev = null;
      for(var i = 0; i < this.length; i++){
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
      }
      return this;
    }
    print(){
        var arr = [];
        var current = this.head
        while(current){
            arr.push(current.val)
            current = current.next
        }
        console.log(arr);
    }
}

var list = new SinglyLinkedList()

list.push(100)
list.push(201)
list.push(250)
list.push(350)
list.push(999)