# Singly Linked List - Data Structures and Algorithms in Javascript

Nov 20, 2023·

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.

Every node contains two crucial things:

1. Data (integer, string, boolean, etc)

2. Pointer (points to the next node)

A singly linked list has two pointers of its own:

1. head (points to the first node)

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

1. Node (represents the structure of the node)

2. 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
}
}
``````

A singly linked list will have:

1. head pointer (points to the first node)

2. tail pointer (points to the last node)

3. length (number of nodes in the list)

``````class SinglyLinkedList {
constructor() {
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.tail = node
} else {
this.tail.next = node
this.tail = node
}
this.length++
return this
}
``````

### Pop

Pop will remove a node from the end.

``````  pop() {
if (this.length <= 1) {
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.tail = null
} else {
}
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 {
}

this.length++
return this
}
``````

### Get

Get a node's value from a particular index.

``````  get(index) {
if (index < 0 || index >= this.length) return undefined
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
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)
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()
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.