ISIAKA ABDULAHI AKINKUNMI

Posted on Aug 10, 2021 • Updated on Aug 11, 2021

Implementation of Linked List in JavaScript and solution to Leetcode interview Question

#algorithms #datascience #javascript #codenewbie

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.

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!

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.

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

putting all together

Some Linkedlist method

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

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

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

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

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

delete(): This removes the node referenced from the argument.

code snippets available on

code pen

github

LeetCode interview

Question 1

Solution to Question 1

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

ISIAKA ABDULAHI