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

Array Vs Linked List in Memory
LL Object with elements

Steps for creating a Linked List

1. Creating a Node

creating a node
// 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 = 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
}
}
// creating a LinkedList with a head and tail point to the with a value of 6let exampleLinkedList = new LinkedList(6)
Output of LL with a created object

Adding items to the Linked List

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

adding at the end of a LL
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 using unshift( )
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( ):

Removing an item from the end
Keeping track of Linked List while iterating over
when tail = prev iteration stops
pop() {
// when 0 items in LL
if(!this.head)
return undefined
// When 2 or more items in LL
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 an item from the beginning
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 length        if(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
}

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

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
}
Code snippet

Resources:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store