# 2. Connecting the dots — Big O and Linked List Data Structure

In my previous article, I mentioned about Array Data Structure. Like Arrays, Linked List are also another way to structure, manage and organize data. In order to understand linked list(LL) let’s compare it to Arrays. Arrays have indexes and occupy contiguous in memory while LL can be anywhere in memory however the elements are stored sequentially.

When we create a LL, we are creating an object like this.

Linked list have head, tail and a null pointer. Heads points to the beginning of the list and the tail points to a null pointer at the end of the list. A pointer points to the memory slot of the next item in the list. Each node has a value and points to the next value using the pointer. Like Arrays, LL also reads from left to right. Here are some of the operations you can perform on a LL.

a) Insert at the beginning or at the end using *push()**.*

b) Delete elements using *pop()**.*

c) Inserting and Deleting in the middle using ** shift()** and

*unshift()**.*

d) Look for an index, set value to an index, insert a value at an index and also remove an item using an index.

e) We can also reverse a LL.

Before we start to perform the above operations, let us see how to create a LL in code and what are the steps involved.

# Steps for creating a Linked List

## 1. Creating a Node

In LL, a node is an object which contains value and a pointer together.

The code for creating a LL will look like this

// Creating a Node

class Node {

constructor(value){

this.value = value

this.next = null

}

}const newNode = new Node(6)

## 2. Creating a LinkedList with a single object

class LinkedList {

constructor(value) {

//creates a new Node and calls the Node class from above

const newNode =newNode(value)

//head pointing to the newNode

this.head = newNode

//tail pointing to head (i.e., to the newNode)

this.tail = this.head

this.length = 1

}

}// creating a LinkedList with a head and tail point to the with a value of 6let exampleLinkedList = new LinkedList(6)

Note: **new** key word calls the** constructors either the LinkedList or from the Node Class. **The output of the above will look like this in the browser console

# Adding items to the Linked List

## 1) Adding to the end using — push( ):

When we add a node to the end of a LL, we will need to do the following steps

1. Last item on the list point to the new node

2. Tail now then points to the new node that we inserting at the end

3. New node now becomes the tail which has a null pointer at the end.

When we push an item at the end of the node in a LL the number of steps taken to add them is same. So we can say that the the time taken for this operation is ** constant** time and it takes

**Big O(1)**to add an element at the end. When we add a node to the head, similar operation takes place. Also, here we need to consider one edge case

*when head and tail are pointing to null.***class LinkedList {**

constructor(value) {

//creates a new node and calls the Node class from above

**const newNode = new Node(value)**

//head pointing to the newNode

** this.head = newNode**

//tail pointing to head (i.e., to the newNode)

** this.tail = this.head **

this.length = 1

}

push(value) {

const newNode = new Node(value)

// checking for the edge case where head and tail are pointing to null

**if (!this.head) {**

this.head = newNode

this.tail = newNode

} else {

this.tail.next = newNode

this.tail = newNode

}

this.length++

// returning an entire LL. push() is part of class LinkedList

**return this**

}

}

## 2) At the beginning using — unshift( ):

Adding at the beginning using ** unshift()** will all take

**BigO(1)**as adding at the end.

**unshift(value) {**

const newNode = new Node(value)

// when no items in LL

**if(!this.head) {**

this.head = newNode

this.tail = newNode

// when 2 or more items are present in LL

**} else {**

newNode.next = this.head

this.head = newNode

}

// increase the length by 1

** this.length++**

return this

}

# Removing an item to the Linked List

## 1) At the end using — pop( ):

There is an issue with removing the node at the end of a LL. When you remove a LL from the end we need to iterate over all the items to move the tail. Since we need to iterate over the entire list, removing a node from the end of the LL is **Big O(n)**. There are three scenarios to consider when you remove an item from the end of a LL

1. When the number of items are zero

2. One item on the list

3. Two or more item on the list

You create variables ** temp** and

**to iterate over the list.**

*prev*pop() {

// when 0 items in LL

if(!this.head)// When 2 or more items in LL

return undefined

let temp = this.head

let prev = this.head

while(temp.next) {

prev = temp

temp = temp.next

}

this.tail = prev

this.tail.next = null

this.length--

// Edge case

// When there is one item in the list

if(this.length === 0) {

this.head = null

this.tail = null

}

return temp

}

## 2) Removing at beginning using shift ( ):

Removing will also be like adding at the beginning. This also takes **constant time**.

**shift() {**

if(!this.head)

return undefined

// two or more items in the LL

**let temp = this.head**

this.head = this.head.next

// decrement the LL

**this.length--**

** **

if(this.length === 0) {

this.tail = null

}

// make sure temp is pointing to null

**temp.next = null**

return temp

}

# By Index

## Looking for an item — get(index)

get(index) {// Out of range. When the index in unavailable ie. < 0 or greater // than the lengthif(index < 0 || index >= this.length)

return undefined// to get the head of the LLL

let temp = this.head

for(let i = 0; i<index; i++){

temp = temp.next

}

return temp

}

In Linked List, looking for something **by value is Big O(n)** whereas in Arrays its Big O(1).

**Setting an Index — set(index, value)**

set(index, value) {// calling the get() from above

let nodeToBeUpdated = this.get(index)

if(nodeToBeUpdated) {

nodeToBeUpdated.value = value

return true

}

return false

}

## Inserting by Index

insert(index, value) {

if(index < 0 || index > this.length)

return false

if(index === this.length)

return this.push(value)

if(index === 0)

return this.unshift(value)

const newNode = new Node(value)

const temp = this.get(index - 1)

newNode.next = temp.next

temp.next = newNode this.length++

return true

}

## Removing by Index

remove(index) {

if(index < 0 || index >= this.length)

return undefined

if(index === 0)

return this.shift()

if(index === this.length - 1)

return this.pop() const before = this.get(index - 1)

const temp = before.next

before.next = temp.next

temp.next = null this.length--

return temp

}

# Reversing a Linked List

This is a common interview question. Here we need to create three variables *temp**,*** next**,

**to keep track of the items on the list**

*prev***.**

`reverse() {`

let temp = this.head

this.head = this.tail

this.tail = temp

let next = temp.next

let prev = null

for(let i = 0; i < this.length; i++) {

next = temp.next

temp.next = prev

prev = temp

temp = next

}

return this

}

Final code will look like this in

To summarize, linked list will have ** time complexities of Big O(n) or Big O(1)** depending on where insertion and deletion of items takes place.

If you like this article, please follow me and give a clap!

# Resources:

MDN , Grokking Algorithms, Big O cheatsheet , *algorithm** , **wikipedia**.*