Implementing array methods on a linked list
Tags: javascript, typescript, algorithms
Published: 2022-03-28 19:29:17

## **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 list](https://en.wikipedia.org/wiki/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
```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`
```typescript

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

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

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

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

## **My Linked-List**
```typescript
  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