Musings on Data Structures: Part 3 — Linked Lists — Javascript
Data Structures: Linked Lists — from a Javascript perspective.
The Data Structure of a Linked List is a sequential collection of elements¹. Although it is a linear collection of data like an array; unlike an array, the elements are not stored contiguously in memory. The location in memory of an array is declared at compile time (in most languages-along with it’s size), but for Linked Lists memory is assigned as and when data is added to it, at runtime². Each element, referred to from here on out as a node, holds 2 pieces of important information, its data (or value) and an address that points to the next node in the list.
Using Linked Lists have advantages and disadvantages over using Arrays depending upon the action that you’re performing on the data. Because Linked Lists are not contiguous (next to or together) in memory, adding (inserting) and removing (deleting) nodes have a Big O time complexity of O(1). With arrays when you add or remove elements, worst case scenario is that you may need to shift the index of all elements after the added/removed element, but with Linked List, no matter how large the data set gets, you only have to change the next pointer of element preceding it, if that element exists. The largest disadvantage of Linked Lists is that because its nodes don’t have indexes that hold the specific place in memory where their value is kept, Linked Lists are terrible for direct access. Nodes can not be accessed randomly: In order to get to a node, you must first traverse all the nodes before it that point to it sequentially, leaving us with a Big O(n). You’re better off choosing a different data structure for searches.
This post will focus on building a Singly Linked List, but Doubly Linked Lists, which have not only a next value for the next node, but a previous value for the node before it, are great for when you need to traverse the list in reverse as well as forward. There’s also Circular Linked Lists where the last nodes’ pointer actually points to the first node again. A great example of a Circular Linked Lists is a multiplayer game where after the last player has finished their turn, the game reverts back to the first player for their next move.
Let’s build a Singly Linked List and define its most important functions of insertion, searching and deletion. Please note that I received a lot of my information for the Linked List that we build below from Web Dev Simplified’s Youtube video here.
The data object that we add to a Linked List can be an integer, a string, or any other object we need to store.
The first thing we need to do is create a Class for our Linked List. This is necessary for anytime we need to instantiate a new Linked List object. We will incorporate a constructor method (a special method of a class for creating and initializing an object of that class)³. Our constructor method, will have one reference, the reference to the Head, which is always the beginning of the Linked List. The head has the address to our first node in our list⁴. We make sure to set the head to null, because when we instantiate a List, we don’t start with a head immediately.
class LinkedList {
constructor() {
this.head = null
}
}We want to now set up a class for instantiating our nodes. The constructor for our Node class will have 2 parameters: value and next. The value is the value of the data at that reference to memory and next will be the reference to the node that comes after this node. This next pointer will point to the next node in the list, or null if it is the Tail node in the list (the last node).
class Node {
constructor(value, next) {
this.value = value,
this.next = next
}
}ADD NODE TO BEGINNING OF LIST
Now that we have classes for constructing new objects of Lists and Nodes, lets build the functions for working with our lists, starting with adding nodes to the BEGINNING our Lists. Our prepend function will have take in a parameter of the value of the data. In this function, we’ll first construct a new Node, with the value of the data and we need to give it whatever the next node is in our List, which because we are adding to the beginning, will be whatever this.head (our current head) is because it’s currently the first node in our List. We’ll need to now make sure to re-set our head to the node we are inserting.
prepend(value) {
const newNode = new Node(value, this.head)
this.head = newNode
}SEARCHING
Let’s say we have now instantiated a Linked List, and have added a bunch of nodes to our List. Our List looks something like this:
Even though it might not be the best Data Structure for doing so, we want to create two different ways to search in our list, 1st by value, and 2nd by index.
Search By Value:
searchByValue(value) {
let currentNode = this.head
while (currentNode) {
if (currentNode.value === value) {
return currentNode
}
currentNode = currentNode.next
}
return null // (if node with same value never found)
}Search By Index
searchByIndex(index) {
if (index < 0) return null
let currentNode = this.head
for (let i = 0; i < index; i++) {
currentNode = CurrentNode.next
}
return currentNode
}INSERTING
We can insert nodes into our List at a specific index with our insertAtIndex function below and passing the function 2 attributes of the index we want to insert at and the value of the data we want inserted. If there is a node at previous position to this inserted node, we need to update that nodes .next value and our node that we will insert will have a next pointer pointing to the node that was initially in the index our new node took over.
insertAtIndex(index, value) {
if (index === 0) return this.prepend(value)
const previousNode = this.searchByIndex(index - 1)
if (previousNode === null) return null
previousNode.next = new Node(value, previousNode.next)
}DELETION
Below are different functions for deleting nodes at different places in our Singly Linked List. I have only outlined 3 delete functions, 1 for deleting at the head, 1 for deleting by index, and 1 for deleting by value.
Delete At Head
deleteHead() {
this.head = this.head.next
}Delete By Value
deleteByValue(value) {
let previousNode = this.head
let currentNode = previousNode.next
while (currentNode) {
if (currentNode.value === value) {
previousNode.next = currentNode.next
}
currentNode = currentNode.next
}
return null // (if node with same value never found)
}Delete At Index
deleteAtIndex(index) {
if (index === 0) return this.deleteHead()
const previousNode = this.searchByIndex(index - 1)
if (previousNode === null) return null
previousNode.next = previousNode.next.next
}INSERTING & REMOVING AT TAIL
We do have the ability to add or delete at the tail, the last node, of our Linked List, but you would first need to make sure that your initial LinkedList constructor initializes a length attribute and then for every function above, you would have to change the value of this.length accordingly with each operation (ex: for a function that adds a node in, you’d have to add a line of code to the function like ‘this.length++’). The tail would become something that lived at a variable like, ‘let position = this.length — 1’.
example of initiating with length:class LinkedList {
constructor() {
this.head = null
this.length = 0
}
}
THE ENTIRE SNIPPET OF CODE
class LinkedList {
constructor() {
this.head = null
} prepend(value) {
const newNode = new Node(value, this.head)
this.head = newNode
} searchByValue(value) {
let currentNode = this.head
while (currentNode) {
if (currentNode.value === value) {
return currentNode
}
currentNode = currentNode.next
}
return null // (if node with same value never found)
} searchByIndex(index) {
if (index < 0) return null
let currentNode = this.head
for (let i = 0; i < index; i++) {
currentNode = CurrentNode.next
}
return currentNode
} insertAtIndex(index, value) {
if (index === 0) return this.prepend(value)
const previousNode = this.searchByIndex(index - 1)
if (previousNode === null) return null
previousNode.next = new Node(value, previousNode.next)
} deleteHead() {
this.head = this.head.next
} deleteByValue(value) {
let previousNode = this.head
let currentNode = previousNode.next
while (currentNode) {
if (currentNode.value === value) {
previousNode.next = currentNode.next
}
currentNode = currentNode.next
}
return null // (if node with same value never found)
} deleteAtIndex(index) {
if (index === 0) return this.deleteHead()
const previousNode = this.searchByIndex(index - 1)
if (previousNode === null) return null
previousNode.next = previousNode.next.next
}
}class Node {
constructor(value, next) {
this.value = value,
this.next = next
}
}
Interesting point that I learned while researching this blog: Linked Lists are used to create trees and graphs⁵.
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
- Linked Lists — Data Structures in JavaScript | beiatrix | ‘https://youtu.be/ChWWEncl76Y’
- Difference between Array and Linked List | Study Tonight | ‘https://www.studytonight.com/data-structures/linked-list-vs-array’
- constructor | MDN Web Docs | ‘https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes/constructor’
- Computer Science | Stack Exchange | ‘https://cs.stackexchange.com/questions/76704/what-precisely-concisely-is-the-head-of-a-singly-linked-list-i-ask-bc-of-ambi’
- Introduction to Linked Lists | Study Tonight | ‘https://www.studytonight.com/data-structures/introduction-to-linked-list’
