Introduction
Having a good understanding of data structure is the key that enables one thinks fast when it comes to solving problems, while lots of tech interviews use it as a roadblock to getting a job I will emphasize it should be a daily practice and routine because it results can not be undermined.To learn more on datastructure i recomend you get the book below,
- A common sense to Data structures and algorithm - Jay Wengrow
Moltivation
Curiosity got me thinking, since an array has lots of built-in methods in Javascript and a linked list is an abstract data type in javascript that can be implemented. I decided to implement a linked list that has all the methods of javascript methods. The linked list shines where an array is terrible from the Big O!! guy and seriously none is better than the other but the type of problem at hand determines the champion. I know this will be an unending post if i post all methods of an array in a linked list that's why this post will be divided into different parts to be posted seperately.
Hold on!!! What is a linked list ?
A linked list is a linear collection of data in a non-contiguous manner. This means a linked list is the opposite of an array which is contiguous in design. When it comes to data placement in the computer memory, contiguous means array items must be placed next to each other in memory and the reverse is the case for a linked list.
Linked Node
Since linked list is define by a node where one item points us to the next item in the list we will define a class of node using typescript
class LinkedNode<T> {
data: T;
next?: LinkedNode<T>;
constructor(data: T, next?: LinkedNode<T>){
this.data = data;
this.next = next;
}
}
Linked List
Now we will define an interface for our linked list
type CallBack<T> = (item: T, index: number)=> void;
interface LinkedListProp<T> {
length: number;
push: (...data: T[]) => number;
pop: ()=> LinkedNode<T>;
printList: ()=> void;
shift: ()=> LinkedNode<T>;
unshift: (...data: T[]) => number;
forEach: (callBack: CallBack<LinkedNode<T>>)=>void;
}
class LinkedList<T> implements LinkedListProp<T> {
private linkedList: LinkedNode<T>;
public length = 0;
private isEmpty(): boolean{
if(!this.linkedList){
return true;
}
return false;
}
}
Note the Generic CallBack type alias is for defining the forEach method of an array that we are about to implement.Also notice the isEmpty methode which returns a boolean true | false to tell us if our list is empty or not.
printList Method
we want to be able to print all the list on the terminal but our terminal will print few LinkedNodes and tells us the rests are LinkedNodes so we will stringify our output and format it nicely so that we can see our linked list functions correctly.
public printList(){
console.log(JSON.stringify(this.linkedList,null,4))
}
pop() Method
We want to be able to remove the last item from an array and return it so we have the following code ...
pop():LinkedNode<T>{
if(this.isEmpty()){
return;
}
let removedNode:LinkedNode<T>
let previousNode: LinkedNode<T>;
let currentNode = this.linkedList;
while (currentNode.next){
previousNode = currentNode;
currentNode = currentNode.next
}
if(!previousNode.next){
removedNode = this.linkedList;
this.linkedList = null;
this.length = 0;
}else{
this.length -= 1;
removedNode = currentNode;
previousNode.next = null;
}
return removedNode;
}
push() method
we want to be able to add an item to end of thelinked-list, but note since we want to implement it the same as javascript arrays we want a user to be able to add multiple items to the end of the array by passing desired number of items to the push method, to achieve this we will use rest parameters for our push method.
push(...data: T[]): number{
let newNodes: LinkedNode<T>;
let currentNode: LinkedNode<T>
data.forEach((nodeData)=> {
let newNode = new LinkedNode(nodeData);
if(!newNodes){
newNodes = newNode;
currentNode = newNode;
}else{
currentNode.next = newNode;
currentNode = newNode;
}
})
// connect the new nodes to linkedlist
if(this.isEmpty()){
this.linkedList = newNodes;
}else{
let current = this.linkedList;
while(current.next){
current = current.next;
}
current.next = newNodes;
}
this.length = data.length + this.length;
return this.length;
};
Let me explain shortly. The thought process here is if we have two linked-list were the first is our existing linked-list and the second is linked-list containing our new items, we can connect them by having reference to the last item in the first list. So what we do is..
- link up all items to be added to the linked list
- if the list is empty our new
linked listbecomes our list - otherwise we grab the last item in our existing
linked listand set thenextproperty to point to our new list.
Shift() Method
Opposite to pop() we want to be able to remove an item from the begining of the list, so we have the following code.
shift(){
if(this.isEmpty()) return;
let currentList: LinkedNode<T>;
let removedNode : LinkedNode<T>;
currentList = this.linkedList.next;
this.linkedList.next = null;
removedNode = this.linkedList;
this.linkedList = currentList;
return removedNode;
}
This method is simple, all we have to do is
- store the reference to the rest of our list except the first.
- set our current list to the list which exempts the first one
- set the next of the removed node to
null - finally we - return the removed node
Unshift() method
Opposite to push() method we will want to be able to add these numerous item to the begining of the array and again rest parameters to the rescue
unshift(...data: T[]): number{
let newNodes: LinkedNode<T>;
let currentNode: LinkedNode<T>
data.forEach((nodeData)=> {
let newNode = new LinkedNode(nodeData);
if(!newNodes){
newNodes = newNode;
currentNode = newNode;
}else{
currentNode.next = newNode;
currentNode = newNode;
}
})
if(this.isEmpty()){
this.linkedList = newNodes;
}else{
let current = newNodes;
while(current.next){
current = current.next;
}
current.next = this.linkedList;
this.linkedList = newNodes;
}
this.length = data.length + this.length;
return this.length;
};
Let me explain shortly again. The thought process here is if we have two linked-list were the first is our existing linked-list and the second is linked-list containing our new items, we can connect them by having reference to the last item in the second list. So what we do is...
- link up all items to be added to the linked list.
- if the list is empty our new
linked listbecomes our list. - otherwise we grab the last item in our second
linked listand set thenextproperty to point to our existing list.
forEach() method
lastly we want to implement the foreach method. this method should allow us iterate through each item in the array using a callBack function that allow us access the item and index. Note i didnt pass the linked list which is suppose to be the last parameter of the callback if we are to implement it same as array
forEach(callback:CallBack<LinkedNode<T>>){
if(!this.linkedList) return ;
let linkedList = this.linkedList;
if(!linkedList.next){
callback(this.linkedList,0);
}else{
let currentList = this.linkedList;
let previousNode: LinkedNode<T>;
let recomposeLinkedList: LinkedNode<T>;
let recomposePrevItem: LinkedNode<T>
let counter = 0;
while (currentList.next){
currentList = currentList.next;
this.linkedList.next = null;
previousNode = this.linkedList;
callback(previousNode,counter)
if(!recomposeLinkedList){
recomposeLinkedList = previousNode;
recomposePrevItem = previousNode;
}else{
recomposePrevItem.next = previousNode;
recomposePrevItem = previousNode;
}
this.linkedList = currentList;
counter++;
}
callback(currentList,counter++);
recomposePrevItem.next = currentList;
this.linkedList = recomposeLinkedList;
}
}
Let me explain something that can make understanding this easier. We want to access each item in the list, but anytime we are accessing the current item it has bunch of other referenced object. The thought process here is...
- Detatch item to be accessed from the list.
- pass it to the callback function afterwards attatch it back.
- we do this for each item in the array.
For accessing single item in the linked list without reference to bunch of others it is linked, I used a thought process that ..
- stores the reference to only the previous item.
- then set the
nextproperty to null - pass it to the
callbackfunction - add the previous node to a variable that recompose the list of accessed items.
But the issue now is our last item will not be read which is the result of the last callback function at the end of the method because our currentList will contain only our last item.
My Linked-List
let testLinkedList = new LinkedList<number>();
testLinkedList.push(100,200,300,400,500,600);
// prints our link list showing how they are linked
testLinkedList.printList()
testLinkedList.pop();
// prints our link list showing how they are linked and the last item removed
testLinkedList.printList();
testLinkedList.unshift(800,900,700);
// print our link list and show the items inserted at the begining of the linked list
testLinkedList.printList();
testLinkedList.unshift();
// print our link list and show the first item removed from the beginning of the linked list
testLinkedList.printList();
testLinkedList.forEach((item,index)=>{
console.log(item);
})
Conclusion
There are couple of more efficient ways of doing this. This is my thoughts and i will really appreciate if there are any suggestion.
I know this is a long read. Watch out for part 2
Top comments (0)