Solomon Yunana

Posted on

# Implementing array methods on a linked list

## 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.

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;

this.data = data;
this.next = next;
}
}

``````

Now we will define an interface for our `linked list`

``````
type CallBack<T> = (item: T, index: number)=> void;

length: number;
push: (...data: T[]) => number;
printList: ()=> void;
unshift: (...data: T[]) => number;
}

public length = 0;

private isEmpty(): boolean{
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 `LinkedNode`s 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(){
}
``````

## pop() Method

We want to be able to remove the last item from an array and return it so we have the following code ...

``````

if(this.isEmpty()){
return;
}

while (currentNode.next){
previousNode = currentNode;
currentNode = currentNode.next
}

if(!previousNode.next){
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 the`linked-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{

data.forEach((nodeData)=> {
if(!newNodes){
newNodes = newNode;
currentNode = newNode;
}else{
currentNode.next = newNode;
currentNode = newNode;
}
})

// connect the new nodes to linkedlist
if(this.isEmpty()){
}else{
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..

• if the list is empty our new `linked list` becomes our list
• otherwise we grab the last item in our existing `linked list` and set the `next` property 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;

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{
data.forEach((nodeData)=> {
if(!newNodes){
newNodes = newNode;
currentNode = newNode;
}else{
currentNode.next = newNode;
currentNode = newNode;
}
})

if(this.isEmpty()){
}else{

let current = newNodes;
while(current.next){
current = current.next;
}

}

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...

• if the list is empty our new `linked list` becomes our list.
• otherwise we grab the last item in our second `linked list` and set the `next` property 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`

``````

}else{

let counter = 0;

while (currentList.next){
currentList = currentList.next;
callback(previousNode,counter)
recomposePrevItem = previousNode;
}else{
recomposePrevItem.next = previousNode;
recomposePrevItem = previousNode;
}

counter++;

}

callback(currentList,counter++);
recomposePrevItem.next = currentList;
}
}

``````

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 `next` property to null
• pass it to the `callback` function
• 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.

``````  let testLinkedList = new LinkedList<number>();

// prints our link list showing how they are linked and the last item removed

// print our link list and show the items inserted at the begining of the linked list

// print our link list and show the first item removed from the beginning of the linked list

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