Implementation of Linked List in JavaScript and solution to Leetcode interview Question
Tags: algorithms, datascience, javascript, codenewbie
Published: 2021-08-10 13:41:01

## Introduction

In *computer science*, a data structure is a data organization, management and storage format that enables efficient access and modification. Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing.

There are various types of data structures which includes *array*, *linked list*, *record*, *union*, *binary tree* and *graph*.
In this article, we will look at *linked list*, it's implementation, various methods we can perform on the linked list and some interview questions.


### What is linked list?
A linked list also  called list is a linear collection of elements called *nodes. The nodes can be any data type(primitive or non-primitive). Each node has  a value, and points to the next node in the linked list. i.e* a node is aware of next node.

![singlyLinkedList](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mfwevocj8fclnlg0ltcy.PNG)

*Linked list* is the second most-used data structure after *array* and it is similar to *array*. The entry point of a linked list is called head while the last node points to null. If a linked list is empty, the head put to null.



### Types of Linked list
There are `three` basic types of linked list namely:

* **Singly-linked list** : This is the simplest type, each node has a data and a pointer to the next *node*. It allow traversal of data in one direction.


* **Doubly-linked list**: This is a complex type in which each *node* has a data and two pointers which point to the previous *node* and next node. traversal of data is bi-directional.


* **Circular-linked list**: This is a similar to *singly linked list* with the last *node* points to the first *node* and vice versa. While traversing a *circular liked list*, we can start at any node and traverse the list in any direction forward and backward until we reach the same *node* we started. Thus, a *circular linked list* has no beginning and no end. 


### Why use Linked list?
Just like *array*, *linkedlist* is a linear *data structure* which performs all operations like adding, deleting and inserting data. Below are the benefits of Linked List:

* **Insertion and Deletion**: Adding an element at the beginning of *array* rearranged the items and shift their indexes which might be tedious while  working on a large database. In *linked list*, we just update the address present in the next pointer of a *node*

* **Size** : Since *nodes* in the linked list are aware of the next *node* such that data can exist at scattered addresses this allows for dynamic size which can change at run time unlike *array* which stores it's data in a non-scattered blocks of memory which can't be changed at run time.

* **Memory Allocation**: For *array*, memory allocation is done at compile time i.e at the time when *array* is declared. While for linked list, memory is allocated when data is added to it thus done at run time.

* **Memory wastage** : Since memory allocation is done at runtime for linked list, there's no memory waste. In array, if a size of 100 is declared and only 80 is utilized to store data. The remaining 20 spaces are wasted.

* **Implementation**: Linear data structures like stack and queues are often easily implemented using a linked list.


### Limitations of Linked List

* **Memory Utilization**:  Memory is needed to store data and also point to the next node in the list. *Linkedlist* require more memory compared to array.

* **Search operation**: In linked list, direct access to element like index in array is not possible. It involves traversing through the whole list and which could leads to time wastage 

* **Memory wastage**: In *double linked list* that reverse traversing is possible *i.e* a node is aware of element before and ahead of it. This requires extra memory and wastage if not utilized.



### **Time Complexity & Big O Notation for Linked list and array**!

![bigO](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u8ipmz2jbikxqo59y82y.png)
 



### **Implementation of Linked List**

* Let's create a *class* `LinkedList` list, initialized the `head`, and `tail` to `null` and length to zero in the constructor function.


![Linked-list-class](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8fmnwt8wswnrbk01ay5l.png)



* We will also use class to create nodes in the list. This can be access by using the `new` keyword.

![node](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1ut2291g9fn9on5tnynk.png)


### **putting all together**


![Implementing=LinkedList](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1l5s6fogm4rq8awy50hb.png)

### **Some Linkedlist method**

* **Prepend()** : This method add node to the list at the beginning.

![prepend](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/it4ajjm7r5w7wcbm1qr8.png)

 
* **printData()** : This method prints all the nodes present in the list. It shows the node, pointer and the next node.

![printData](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/snldfy3qjce4afhtjpgz.png)

* **append()**: This method add new node as the last node on the linked list.

![append](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/989z9s8m5gwtgyx1a20r.png)

* **getLength()**: This return the length of the list.

![getLength](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n5uhaui6q2gwaie0ymw4.png)

* **find()** : This method finds the *node* passed as argument. or it return `null` if its not found.


![find](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xqh5i4i6746sverbmzmx.png)

* **delete()**: This removes the node referenced from the argument.
![delete](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pwvnx6linmyq3w01sd0r.png)

> **code snippets available on** 
* [code pen](https://codepen.io/pen/?template=gOWZKdv) 
* [github](https://github.com/isiakaabd/LinkedListArticle.git)


##LeetCode  interview
 
> Question 1

![Example1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lhylv29bdc93kk0r3rw1.png)


![leetcode-Image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7ljazwc0yahz5x1628ps.PNG)


## Solution to Question 1

![deleteNode](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z2slhe771eoojtvr7f90.png)
**Explanation**
Deleting a node in *linkedlist* involves moving pointer to the next node ahead of the target. 
```
 node.val = node.next.val ;
```
> Basically saying, where we have `5` as the `val`,  replace it with next `val` which is `1`. this remove 5 from the node.

```
node.next = node.next.next;
```
> here, our node is an array, [4,5,1,9]. our `node.next.next` will be [1,9]. This delete the node and its value.

## Summary

In this article, we discussed `linkedlist`, different types of `linkedlist`, the benefits and limitations over `array`, several methods that can be used and solution to leetcode problem. 

 
**Thanks for reading**
Do you wish to get notified when I published a new article? click [here](https://mailchi.mp/4f641d33a5ee/subscribe-ti-my)

[ISIAKA ABDULAHI](https://abdulahi.netlify.app)