Singly Linked Lists
Tags: javascript, html, css, webdev
Published: 2021-02-11 07:08:05

---
title: Singly Linked Lists 
published: true
description: 
tags: javascript, html, css, webdev
//cover_image: https://direct_url_to_image.jpg
---

                       -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. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/vltek01t2vsiat67ggsl.png)

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 




```javascript 

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


```javascript 



    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 


```javascript 

   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 


```javascript 

    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 


```javascript 

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

```javascript 

  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 


```javascript 

    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 

```javascript 

    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 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/g2xx39vwgt00xrvj3fpc.png)

```javascript 


   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 


```javascript 

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)









```