A LinkedList is a sequential collection of data. Linked List are of two types, Singly Linked List and Doubly Linked List.
Download the course content below.
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
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.