Linked list implementation using JavaScript

What is a Linked List?

Linked list is a linear data structure in which data is stored in non-contiguous memory location. Data in a linked list is wrapped in an object which is commonly called as a node. Each node points (or links) to the next node in the sequence of a list. Unlike arrays, linked lists can easily grow or shrink with addition or removal of data.

More detailed information about linked lists can be found here.

What will I get from this article?

In this article, you will learn about implementing Singly Linked List using JavaScript. Note that, this code is written for learning purpose, so, if you are planning to use this code or a piece of this code in your application, please make sure to have thorough testing in place.

Implementation

We will be executing our code using NodeJS, make sure it is installed in your system. We will have three files in our project directory.

  1. list-node.js – class representing a node in linked list.
  2. linked-list.js – class representing a linked list.
  3. index.js – driver program to test our implementation.

Below is the code for each file.

Execute driver program by running command “node index.js” in your terminal. You will see below as output.

Explanation

Let’s begin with list-node.js which exposes a class which will represent a single node in a linked list. Node object contains two properties:

  1. data – as the name suggests, stores some data in it.
  2. next – reference to next node in the sequence.

Moving on to linked-list.js. This file contains the implementation of a Singly Linked List. LinkedList class contains

  1. Properties
    1. head – a reference to first node of the linked list or undefined.
    2. tail – a reference to last node of the linked list or undefined.
  2. Methods
    1. isEmpty – checks whether the list is empty. Returns a Boolean value.
    2. insertAtStart – inserts a node at the beginning of the list.
    3. insertAt – inserts a node at a specific position.
    4. insertAtEnd – inserts a node at the end of the linked list.
    5. insertAtEndWithoutUsingTail – inserts a node at the end of the list without using the tail property.
    6. insert – inserts a node at the end of the linked list.
    7. deleteFromStart – deletes a node from beginning of the linked list.
    8. delete – deletes a node containing specific data.
    9. deleteFromEnd – deletes a node from the end of the linked list.
    10. search – Searches for a data in the list. Returns a Boolean value.
    11. print – prints the list in a readable format.

index.js file contains driver code to test our linked list implementation.

 

With this, I hope you have got an idea about how linked lists are implemented. You can download the source code from Github if you want to run it on your machine.

Comments

Popular posts from this blog

What is object destructuring and spread operator in JavaScript?

What are filter, map and reduce functions in JavaScript?

Is competitive programming required to become a good software engineer?