A LinkedList is a sequential collection of data. Linked List are of two types, Singly Linked List and Doubly Linked List.
In this article, I will discuss how you can use es6 (JavaScript) to implement a Singly Linked List. The example below uses object-oriented features of es6, please refer my previous on Object-Oriented Programming in ES6.
Download the course content below.
Steps to run the code
- Unzip the downloaded package and navigate inside the folder
- Run
npm install
- Run
npm run start
- The above step should open
http://localhost:3000
in your browser automatically, if it does not please open the same in a browser. - A debug point is already inserted in the test file, please play with the test now by opening browser
debug console
.
A Linked List is a linear data structure. It is made up of independent nodes that may contain any type of data like objects, functions, character, number, etc.
1. Singly LinkedList Node
A LinkedList node consists of 2 parts, data – which actually holds the value and next – a reference or pointer to the next node. The node that does not point to any node, should have next = null
2. Singly LinkedList
A singly Linked List is made up of multiple nodes connected with next (next of node1 points to the node2, next of next2 points to next3 and so on). LinkedList has 3 important parts as:
- Head: The first node of the list is known as Head, this is null for an empty list.
- Tail: The last node of the list is known as Tail, this is null for an empty list.
- Size: Number of elements present in a Linked List. This is 0 for an empty list.
Linked List allows the following operations:
3. Insertion/add data
Data can be added/inserted to LinkedList in two ways i.e on top – prepending, or at the bottom – appending.
Below is the code which explains how to achieve prepending and appending.
4. Deletion of a random node containing data
The code below is refactored into 3 methods, deleteHead() – deletes the first node, deleteTail() – deletes the last node and delete(data) – deletes a random node with the given data.
5. Traverse LinkedList or find a node with the data
Below is the code that implements a find(data) method with the LinkedList basic traversal logic.
6. The complete LinkedList code
Now, let us look into how the LinkedList class look like after assembling all bits and pieces.
7. Test Singly Linked List
You can create a LinkedList as below and write a few test cases to verify the functionalities. You can also try out enterprise level testing tools like Jest, Karma, etc.
I would love to hear your thoughts on the approach I took in implementing a Singly Linked List in JavaScript. There are off-course many more ways to implement the same. I did not like the way many popular blogs implemented this, so decided to write an article on the same. Happy Coding…