This is our first article in the series of Data Structures and Algorithms. In this article, we will discuss the ins and outs of a Singly Linked List.

What is a Singly Linked List?

A Singly Linked List is a linear data structure that allows us to store data in a linear way. It is a collection of nodes where each node points to the next node.

A Singly Linked List from VisuAlgo.net

Every node contains two crucial things:

Data (integer, string, boolean, etc)
Pointer (points to the next node)

A singly linked list has two pointers of its own:

head (points to the first node)
tail (points to the last node)

The pointer of the last node always points to null since there is no node after it.

Implementation in Javascript

Now that we know what is a singly linked list and what it looks like, let's code it using JavaScript. We will be using object-oriented programming to implement it and we will use the ES6 Class syntax.

We will need two classes:

Node (represents the structure of the node)
SinglyLinkedList (represents the structure and also includes the major operations)

Node Class

As we discussed above, a node contains two things:

Data (number, string, boolean, etc)
Pointer (points to the next node)

The pointer initially points to null.

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

Singly Linked List Class

A singly linked list will have:

head pointer (points to the first node)
tail pointer (points to the last node)
length (number of nodes in the list)

class SinglyLinkedList {
  constructor() {
    this.head = null
    this.tail = null
    this.length = 0
  }
}

Basic Operations

A singly linked list can perform the following operations:

push (insert at the end)
pop (remove from the end)
shift (remove from the start)
unshift (insert at the start)
get (get a node at a particular index)
set (change the value of a node at a particular index)
insert (insert at a particular index)
remove (remove from a particular index)

Now we will implement all these operations into the SinglyLinkedList class.

Push

Push will insert a new node at the end.

  push(value) {
    const node = new Node(value)

    if (!this.length) {
      this.head = node
      this.tail = node
    } else {
      this.tail.next = node
      this.tail = node
    }
    this.length++
    return this
  }

Pop

Pop will remove a node from the end.

  pop() {
    let currentNode = this.head
    if (this.length <= 1) {
      this.head = null
      this.tail = null
    } else {
      while (!currentNode?.next?.next) {
        currentNode = currentNode.next
      }
      currentNode.next = null
      this.tail = currentNode
    }
    this.length--
    return this
  }

Shift

Shift will remove a node from the start.

  shift() {
    if (this.length <= 1) {
      this.head = null
      this.tail = null
    } else {
      this.head = this.head.next
    }
    this.length--
    return this
  }

Unshift

Unshift will insert a new node at the start

  unshift(value) {
    const node = new Node(value)
    if (!this.length) {
      this.tail = node
    } else {
      node.next = this.head
    }
    this.head = node

    this.length++
    return this
  }

Get

Get a node's value from a particular index.

  get(index) {
    if (index < 0 || index >= this.length) return undefined
    let currentNode = this.head
    for (let i = 1; i <= index; i++) {
      currentNode = currentNode.next
    }
    return currentNode.value
  }

Set

Change the node's value at a particular index.

  set(index, value) {
    if (index < 0 || index >= this.length) return
    let currentNode = this.head
    for (let i = 1; i <= index; i++) {
      currentNode = currentNode.next
    }
    currentNode.value = value
    return this
  }

Insert

Insert a new node at a particular index.

  insert(index, value) {
    if (index < 0 || index > this.length) return this
    const node = new Node(value)
    if (index === 0) return this.unshift(value)
    if (index === this.length) return this.push(value)
    let currentNode = this.head
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next
    }
    const nextNode = currentNode.next
    currentNode.next = node
    node.next = nextNode
    this.length++
    return this
  }

Remove

Remove a node at a particular index.

  remove(index) {
    if (index < 0 || index >= this.length) return
    if (index === 0) return this.shift()
    if (index === this.length - 1) return this.pop()
    let currentNode = this.head
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next
    }
    currentNode.next = currentNode.next.next
    this.length--
    return this
  }

Time Complexity

Now that we have implemented all the basic operations that a singly linked list can perform, let's talk about the time complexity of each of them:

push: O(1)
pop: O(n)
shift: O(1)
unshift: O(1)
get: O(n)
set: O(n)
insert: O(n)
remove: O(n)

Pros and Cons of a Singly Linked List

Pros

A singly linked list is useful when you want to frequently insert or remove elements because it takes constant time.

Cons

A singly linked list is not efficient when it comes to accessing the elements because there are no indices assigned to the elements. So you have to visit each node starting from the first node until you find the target node.

Shahmir Faisal