In this series which I called JS-DS (JavaScript Data Structure)
, I will implement various Data Structures in Javascript. The first Data Structure that I am implementing is LinkedList.
One of the widely used data structure is Array
in JavaScript. In contrast to Array
s which are inbuilt in JavaScript, LinkedList
s is not inbuilt. Let's briefly know what is LinkedList and then deeply dive into the implementation.
LinkedList
@vaidehijoshi in her awesome medium blog post says:
LinkedList is linear data structure, which means that there is a sequence and an order to how it is constructed and traversed.
One of the famous analogy which is given for LinkedList is chain
link. You can think of LinkedList as chain link. Each link in the chain is connected to another link to form the whole chain.
Basic building block
As you can see in the picture above, the basic building block of a chain
is link
, in similar fashion the basic building block of a LinkedList is node
.
Node
A node has two parts
- Data
- Pointer or reference to next node
One of the important thing about node is, it only cares about the data
it holds and the pointer
to next node
. Apart from this it does not know anything about other nodes in LinkedList
.
Head
First node of the LinkedList is referred as head
. When there is no element in LinkedList, the head
is null
. Head
is the starting point of LinkedList
.
Tail
The last node of the LinkedList is referred as tail
. The tail
of the LinkedList points to null
as it is the last element in the list.
In Summery there is three main parts of LinkedList
- Head
- Node
- Tail
Difference between LinkedList and Array
In her blog @vaidehijoshi says:
The biggest differentiator between arrays and linked lists is the way that they use memory in our machine.
Array requires allocation of
contiguous memory
while in LinkedList thememory allocation
isdynamic
which means the elements of LinkedList can be anywhere in memory.When we add or remove element at start of the
Array
, it needs to shift all the elements (reindex all the items)When we add or remove items from between the elements, array need to be reindexed again.
When we add more items in the array and it does not have enough memory for items, it will recreate a new array with enough memory (point to note here that it need to find enough contiguous memory again) and copy all the items from the previous array to new array then add our new items.
Adding and deleting items in Array
s is costly operation due to the reindexing, whereas LinkedList
do not suffer the same issue.
Implementation of LinkedList
So now when basics are clear. Let's start implementing the LinkedList
.
Node
As discussed above, Node
has 2 properties:
- data : Contains value of element added
- next : Pointer to next element
To create a Node
we need some element
or data
that we need to add to LinkedList
. In ES 6
we have class
so let's use it to implement Node
.
// src/linkedlist/model.js
class Node {
constructor(element) {
this.data = element;
this.next = null;
}
}
Equality of node
Equality of nodes is one thing that we need later in our LinkedList
implementation.
Anatomy of equals
method:
- Take two nodes as params
- Perform some operation to decide whether nodes are equal or not
- Return a
boolean
For a default
I am going to write a defaultEquals
method which simply compares two nodes with ===
operator.
// src/linkedlist/utils.js
const defaultEquals = (nodeA, nodeB) => {
return nodeA === nodeB;
};
LinkedList
Now it's time to write our LinkedList
class.
// src/linkedlist/linkedlist.js
class LinkedList {
constructor(equals = defaultEquals) {
this.equals = equals;
this.head = null;
this.count = 0;
}
}
As you can see LinkedList
constructor
will take an equals
methods which is equal to defaultEquals
. If user of the LinkedList
want to override the equals
, he/she can provide his/her own implementation of the equals
method.
We initialise 3 internal properties of LinkedList
:
-
equals : Which is initialised as passed
defaultEquals
methods -
head: Pointer to the start of
LinkedList
. Initialised asnull
-
count : Keep count of
number of elements
inLinkedList
. Initialised as0
Methods of LinkedList
add(element): Takes an element and add it to the list
insertAt(element, index): Adds the element at the specified index
addFirst(element): Takes an element and add it to
start
of the listgetAt(index): Return the element at the specified index
indexOf(element): Returns index of the passed the element. If the element do not exist in list it returns
-1
removeAt(index): Removes the element at the specified index and return the removed element
remove(element): Removes the element if it exist in list and returned the removed element
size: A getter method which return size of the list
isEmpty(): Return
true
if list is empty otherwise returnfalse
clear(): Clears the list
toString(): Return the string representation of the list
add(element)
Steps:
- Create the
new Node
for the passed element. - Check if the list is
empty
i.e.size === 0
. If yes then it is easy we just assign thenode
to thehead
- If list is not empty we need to go through the whole list to reach to the end of the list. As we know that the last element always points to
null
so that will be our breaking condition. - After we find last node, we simply assign the newly created
node
to thenext
of last node
- Last but not the least we need to increase the
count
of the list.
// src/linkedlist/linkedlist.js
add(element) {
const node = new Node(element);
if (this.size === 0) {
this.head = node;
} else {
let currentNode = this.head;
while (currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
this.count++;
}
insertAt(element, index)
Steps:
- First thing we check that the passed
index
is within thebounds
i.e. between0
andsize
. For this I have written anutility
method_isIndexWithinBound
_isIndexWithinBound(index) {
return index >= 0 && index <= this.count;
}
If it is not in bounds then we simply throw a
Error
that the provided index isout of bound
If the index is within the bounds of list then
Create the
new Node
for the passed element.If we want to add the element to start of the list i.e.
index === 0
then we simply need to point thehead
to our newly creatednode
and then point thenext
of newnode
to the oldhead
const currentNode = this.head;
node.next = currentNode;
this.head = node;
If the index is not
0
then we need to find the previous node of the provide index. We need to find it because we need to break the link between previous node and the node at the provided index. To findprevious node
, I have implemented a utility method_getNodeAt(index)
, which returnnode
at the provided index.In
_getNodeAt(index)
we start fromhead
and loop until we reach the specified index. Once we reach that index we return thenode
. If thehead
isnull
then we return undefined.
_getNodeAt(index) {
if (this._isIndexWithinBound(index)) {
let currentNode = this.head;
for (let i = 0; i < index && currentNode !== null; i++)
{
currentNode = currentNode.next;
}
return currentNode;
}
return undefined;
}
- After we find the previous node using
_getNodeAt(previousIndex)
then we point thenext
of previous node to ournewly created node
andnext
of our newly created node to theexisting node
at that index.
const previousNode = this._getNodeAt(index - 1);
node.next = previousNode.next;
previousNode.next = node;
- At last we increase the
count
and returntrue
to specify that the operation is success.
In summery whole insertAt
will be like this
// src/linkedlist/linkedlist.js
insertAt(element, index) {
if (this._isIndexWithinBound(index)) {
const node = new Node(element);
if (index === 0) {
const currentNode = this.head;
node.next = currentNode;
this.head = node;
} else {
const previousNode = this._getNodeAt(index - 1);
node.next = previousNode.next;
previousNode.next = node;
}
this.count++;
return true;
}
throw new Error(
`IndexOutOfBoundError: Provided index ${index} is not
within bounds[${0} - ${this.size}] of LinkedList`
);
}
addFirst(element):
After implementing insertAt(element, index)
it is very easy to implement addFirst
. We just need to pass element
and index = 0
for adding at the start.
addFirst(element) {
return this.insertAt(element, 0);
}
getAt(index)
To implement getAt(index)
we simply use _getNodeAt(index)
to get the node at that index and if the node exist then we return data
of the node.
getAt(index) {
const node = this._getNodeAt(index);
return node && node.data;
}
indexOf(element)
Steps
To find index of provided element we start from
head
.For every node and use our
equals
method to check thatprovided node
is equal to ourcurrent node
or not.If it is equal to our current node then we return the index.
If
head
isnull
or we have visited all the nodes and we do not find any of the elements to be equal toprovided node
then we return-1
.
indexOf(element) {
let currentNode = this.head;
for (let i = 0; i < this.count && currentNode != null;
i++) {
if (this.equals(element, currentNode.data)) {
return i;
}
currentNode = currentNode.next;
}
return -1;
}
removeAt(index)
Steps
- First we check that the passed index is within bounds of list.
- Then we check if the
index === 0
means we want to delete first node of list. Then we assign second node (this.head.next
) to head.
- If
index !== 0
then we need to find previous node to provided index. We can find that by using_getNodeAt(index - 1)
. - Then we point
next
ofprevious node
tonext node
ofcurrent node
(we can find current node bypreviousNode.next
). - Lastly we decrease the
count
and returndata
ofdeleted
node.
removeAt(index) {
if (this._isIndexWithinBound(index)) {
let currentNode = this.head;
if (index === 0) {
this.head = currentNode.next;
} else {
const previousNode = this._getNodeAt(index - 1);
currentNode = previousNode.next;
previousNode.next = currentNode.next;
}
this.count--;
return currentNode.data;
}
return undefined;
}
remove(element)
Now that we know that how to find index of a given element and we also know how to remove a element at a given index.
Combining these two methods, we can implement remove(element)
as follows:
remove(element) {
const elementIndex = this.indexOf(element);
return this.removeAt(elementIndex);
}
get size()
I have implemented size
as getter to make it similar to length
property in Array
. Implementation is very easy, we just return count
of the list
get size() {
return this.count;
}
isEmpty()
If the size
of the list is 0
then list is empty.
isEmpty() {
return this.size === 0;
}
clear()
To clear a list we simply set head
to null
and reset the count to 0
.
clear() {
this.head = null;
this.count = 0;
}
toString()
I wanted the string implementation of LinkedList
to be similar to Java
implementation of toString
of LinkedList
which is something like this:
If we have added
1
,2
and3
in LinkedList thentoString
will return[1,2,3]
To make it simpler, I first made this LinkedList
iterable
by implementing [Symbol.iterator]
generator. If you do not know how to make any object in JavaScript iterable. I highly recommend this Convert any object to Iterable blog. Implementation is as follows :
*[Symbol.iterator]() {
let currentNode = this.head;
while (currentNode) {
yield currentNode.data;
currentNode = currentNode.next;
}
}
Once our LinkedList
is iterable
we simply take advantage of ...
(spread operator) and convert our linkedlist to array
and call toString
on it.
toString() {
return `[${[...this].toString()}]`;
}
Whole implementation
import { Node } from "./model";
import { defaultEquals } from "./utils";
export class LinkedList {
constructor(equals = defaultEquals) {
this.equals = equals;
this.head = null;
this.count = 0;
}
add(element) {
const node = new Node(element);
if (this.size === 0) {
this.head = node;
} else {
let currentNode = this.head;
while (currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
this.count++;
}
_isIndexWithinBound(index) {
return index >= 0 && index <= this.count;
}
_getNodeAt(index) {
if (this._isIndexWithinBound(index)) {
let currentNode = this.head;
for (let i = 0; i < index && currentNode !== null; i++)
{
currentNode = currentNode.next;
}
return currentNode;
}
return undefined;
}
getAt(index) {
const node = this._getNodeAt(index);
return node && node.data;
}
insertAt(element, index) {
if (this._isIndexWithinBound(index)) {
const node = new Node(element);
if (index === 0) {
const currentNode = this.head;
node.next = currentNode;
this.head = node;
} else {
const previousNode = this._getNodeAt(index - 1);
node.next = previousNode.next;
previousNode.next = node;
}
this.count++;
return true;
}
throw new Error(
`IndexOutOfBoundError: Provided index ${index} is not
within bounds[${0} - ${
this.size
}] of LinkedList`
);
}
addFirst(element) {
return this.insertAt(element, 0);
}
addLast(element) {
return this.insertAt(element, this.count);
}
removeAt(index) {
if (this._isIndexWithinBound(index)) {
let currentNode = this.head;
if (index === 0) {
this.head = currentNode.next;
} else {
const previousNode = this._getNodeAt(index - 1);
currentNode = previousNode.next;
previousNode.next = currentNode.next;
}
this.count--;
return currentNode.data;
}
return undefined;
}
indexOf(element) {
let currentNode = this.head;
for (let i = 0; i < this.count && currentNode != null;
i++) {
if (this.equals(element, currentNode.data)) {
return i;
}
currentNode = currentNode.next;
}
return -1;
}
remove(element) {
const elementIndex = this.indexOf(element);
return this.removeAt(elementIndex);
}
isEmpty() {
return this.size === 0;
}
get size() {
return this.count;
}
getHead() {
return this.head;
}
getTail() {
return this.getAt(this.size - 1);
}
clear() {
this.head = null;
this.count = 0;
}
*[Symbol.iterator]() {
let currentNode = this.head;
while (currentNode) {
yield currentNode.data;
currentNode = currentNode.next;
}
}
toString() {
return `[${[...this].toString()}]`;
}
}
Thank you for reading.
You can play around the code on Codesandbox
Access the repository on Github
thejsdeveloper / JS-DS-LinkedList
Created with CodeSandbox
JS-DS: LinkedList- JavaScript Implementation
This repository contains implementation of LinkedList in JavaScript.
To know in detail please refer to my blog in JS-DS series.
Setup
- Clone the repository
git clone https://github.com/thejsdeveloper/JS-DS-LinkedList.git
- Enter into
JS-DS-LinkedList
directory
cd JS-DS-LinkedList
- To Run
yarn start
- To run Test Cases
yarn test
Instructions
- You can find implementation in /src/linkedlist directory
- I have added some test cases in /src/tes directory
- I have also added some use cases in /src/index
After running
yarn start
look into the console of your browser for result
Read my other articles
Special kind of array in Typescript - Tuple
Vikas yadav for XenoX ・ Sep 26 ・ 4 min read
JavaScript Jungle: Curious case of sparse array in JS
Vikas yadav for XenoX ・ Sep 19 ・ 3 min read
Follow me on twitter
References
- @vaidehijoshi 's [blog] on LinkedList part-1 (https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d)
- @vaidehijoshi 's [blog] on LinkedList part-2 (https://medium.com/basecs/whats-a-linked-list-anyway-part-2-131d96f71996)
- @vaidehijoshi 's video Lecture series on LinkedList
- Learning Javascript DataStructure book
Top comments (0)