Singly Linked List

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.

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

Implementation

• First we'll create a node class which we will instantiate when we want to create a node.

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

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

 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

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

  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

 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

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

printListData() {
    //set current to first node
    let current = this.head;
    //iterate over list
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

Clear List

  clearList() {
    this.head = null;
    this.size = 0;
  }

Example test code;

//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 ❤️ .