Singly Linked List
Tags: javascript, webdev, tutorial
Published: 2020-04-06 16:50:21

This is the most common used linked list. It is a single chain of nodes. 

##The Node
In singly linked list, each node contains two parts; data and a link to next node.
![Node](https://dev-to-uploads.s3.amazonaws.com/i/sbzf3hz07azamnxapyp1.png)


##Linked List
Singly Linked List contains a header pointer which contains address of the first node (the head node). Forward sequential movement, only, is possible here. 
Note that the last node has it's link part set to null

![Linked List](https://people.engr.ncsu.edu/efg/210/s99/Notes/LLdefs.gif)
##Implementation
* First we'll create a node class which we will instantiate when we want to create a node.
```javascript
class Node {
  constructor(data, next = null) {
    this.data = data;
//link to next node
    this.next = next;
  }
}
```
The link to next node is set to null for a single node.
* We then create a Linked List class
```javascript
class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
//methods added here...
}
```
For an empty list, head is null and the size is 0.
* We then need to add methods in our linked list class to perform various operations such as **add**, **remove** and **find**. 


**Add node to start of list**

```javascript
 insertFirst(data) {
    this.head = new Node(data, this.head);
    this.size++;
  }
```
If the list was empty, the new node is set as the head and the link is set to null. 
If the list was not empty, the new node is set as the new head and it's link set to the previous head. 
The size of list is increased by one.

**Add node to end of list**
```javascript
insertLast(data) {
    let node = new Node(data);
    let current;
    //if list is empty, make new node the head
    if (this.size === 0) {
      this.head = node;
    } else {
      //select head as current node
      current = this.head;
      //go to end of list
      while (current.next) {
        current = current.next;
      }
      //add new node as next value of the last node
      current.next = node;
    }
    this.size++;
  }
```
The while loop terminates if **current.next** is null and the new node is added as it's value. The size of list is increased by one.

**Remove first node of list**
```javascript
  removeFirst() {
    if (this.size !== 0) {
      this.head = this.head.next;
      this.size--;
      if (this.size === 0) {
        this.head = null;
      }
    }
  }

```
If the list is not empty, the head is removed and replaced by the next node.
The size is decreased

**Remove Last node of list**
```javascript
 removeLast() {
    let current, previous;
    //if list is not empty
    if (this.size !== 0) {
      //if list contains one node
      if (this.size === 1) {
        this.head = null;
      } else { 
         current = this.head;
        //go to end of list
        while (current.next) {
          previous = current;
          current = current.next;
        }   
        //remove last node
        previous.next = null;       
      }
      this.size--;
    }
  }
```
Current and previous variables hold the current node and previous node respectively.

**Find index of node in list**
```javascript
findIndexOf(data) {
    let idx = 0;
    //set current to first node
    let current = this.head;
    //iterate over list
    while (current) {
      if (current.data === data) {
        console.log(idx)
        //return index of item
        return idx;
      }
      //increase index by one 
      idx++;
      //move to next node and recheck
      current = current.next;
    }
    console.log(-1);
    //not found
    return -1;
  }
```
Starting from the head, we check if data in current node equals the data in question and return it's index. After each check the index counter increases by one. If the data is not in the list -1 is returned. 

**Print Linked List Data**
```javascript
printListData() {
    //set current to first node
    let current = this.head;
    //iterate over list
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

```

**Clear List**
```javascript
  clearList() {
    this.head = null;
    this.size = 0;
  }
```

Example test code; 
```javascript
//create empty list
const list = new LinkedList();

list.insertLast(400);
list.insertLast(500);
list.insertFirst(600);
list.findIndexOf(500)

console.log(list);
list.printListData();
```

Thank you for reading :heart: .