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 Arrays which are inbuilt in JavaScript, LinkedLists is not inbuilt. Let's briefly know what is LinkedList and then deeply dive into the implementation.
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
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 the memory allocation is dynamic 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 Arrays 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.
As you can see LinkedListconstructor 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 as null
count : Keep count of number of elements in LinkedList. Initialised as 0
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 list
getAt(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 return false
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 the node to the head
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 the next of last node
Last but not the least we need to increase the count of the list.
If it is not in bounds then we simply throw a Error that the provided index is out 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 the head to our newly created node and then point the next of new node to the old head
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 find previous node, I have implemented a utility method _getNodeAt(index), which return node at the provided index.
In _getNodeAt(index) we start from head and loop until we reach the specified index. Once we reach that index we return the node. If the head is null then we return undefined.
After we find the previous node using _getNodeAt(previousIndex) then we point the next of previous node to our newly created node and next of our newly created node to the existing node at that index.
At last we increase the count and return true to specify that the operation is success.
In summery whole insertAt will be like this
// src/linkedlist/linkedlist.jsinsertAt(element,index){if(this._isIndexWithinBound(index)){constnode=newNode(element);if(index===0){constcurrentNode=this.head;node.next=currentNode;this.head=node;}else{constpreviousNode=this._getNodeAt(index-1);node.next=previousNode.next;previousNode.next=node;}this.count++;returntrue;}thrownewError(`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.
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
getsize(){returnthis.count;}
isEmpty()
If the size of the list is 0 then list is empty.
isEmpty(){returnthis.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 and 3 in LinkedList then toString will return [1,2,3]
To make it simpler, I first made this LinkedListiterable 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 :
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";exportclassLinkedList{constructor(equals=defaultEquals){this.equals=equals;this.head=null;this.count=0;}add(element){constnode=newNode(element);if(this.size===0){this.head=node;}else{letcurrentNode=this.head;while(currentNode.next!==null){currentNode=currentNode.next;}currentNode.next=node;}this.count++;}_isIndexWithinBound(index){returnindex>=0&&index<=this.count;}_getNodeAt(index){if(this._isIndexWithinBound(index)){letcurrentNode=this.head;for(leti=0;i<index&¤tNode!==null;i++){currentNode=currentNode.next;}returncurrentNode;}returnundefined;}getAt(index){constnode=this._getNodeAt(index);returnnode&&node.data;}insertAt(element,index){if(this._isIndexWithinBound(index)){constnode=newNode(element);if(index===0){constcurrentNode=this.head;node.next=currentNode;this.head=node;}else{constpreviousNode=this._getNodeAt(index-1);node.next=previousNode.next;previousNode.next=node;}this.count++;returntrue;}thrownewError(`IndexOutOfBoundError: Provided index ${index} is not
within bounds[${0} - ${this.size}] of LinkedList`);}addFirst(element){returnthis.insertAt(element,0);}addLast(element){returnthis.insertAt(element,this.count);}removeAt(index){if(this._isIndexWithinBound(index)){letcurrentNode=this.head;if(index===0){this.head=currentNode.next;}else{constpreviousNode=this._getNodeAt(index-1);currentNode=previousNode.next;previousNode.next=currentNode.next;}this.count--;returncurrentNode.data;}returnundefined;}indexOf(element){letcurrentNode=this.head;for(leti=0;i<this.count&¤tNode!=null;i++){if(this.equals(element,currentNode.data)){returni;}currentNode=currentNode.next;}return-1;}remove(element){constelementIndex=this.indexOf(element);returnthis.removeAt(elementIndex);}isEmpty(){returnthis.size===0;}getsize(){returnthis.count;}getHead(){returnthis.head;}getTail(){returnthis.getAt(this.size-1);}clear(){this.head=null;this.count=0;}*[Symbol.iterator](){letcurrentNode=this.head;while(currentNode){yieldcurrentNode.data;currentNode=currentNode.next;}}toString(){return`[${[...this].toString()}]`;}}