This content originally appeared on DEV Community and was authored by Veronika Fatikhova
Linked List is a linear data structure, very similar to an array. However, in an array, data is stored as consecutive chunks of values where each element has a particular index. In a linked list, all elements are stored in different memory locations and linked together by pointers (which is the next node’s memory address).
Each element (called a node), contains two parts: data of any type and a pointer to the next element. The last node points to null (in human language, nothing). The reference to the very first element is commonly called head, and the reference to the last element is called tail. We don’t always need to know the tail but must remember the first element of the list.
In this article, we’ll take a look at the basics: implementation of a singly linked list in JavaScript and some operations on it.
Implementation of a linked list in JS
In programming languages, a linked list can be represented either as a separate data structure or just as a reference to the list's head that is more commonly used in interview questions. Having the head, a cursor to the very first node, we can refer to the whole list because, again, all its nodes in the computer memory are linked together.
In JavaScript, we can implement a singly-linked list with a class or with a function. In both cases, we have to define two parts: data and a pointer to the next node.
That’s how we can define it with a class of linked lists:
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
That’s how we can define it with function:
const ListNode = (val, next) => {
this.val = (val===undefined ? 0 : val);
this.next = (next===undefined ? null : next);
}
Note that with the last implementation, if we don’t pass the arguments the node will be created with 0 value and null pointer by default.
Let’s create the first node instance with a value of 1 and set up the head cursor.
let node1 = new ListNode(1);
let head = node1;
We created a list containing one single node. Setting the head cursor, we can further return the whole list head=[1]:
return head;
Operations on a linked list
Now, let’s implement some basic operations on a singly linked list, such as: inserting a node, deleting the node, and traversing the list.
Inserting a node
- The simplest operation on the list could be appending a node (adding to the end of a list). To do so we just have to allocate memory for a node and link it with the previous node:
node1.next = new ListNode(2);
We added the second node to our list: head=[1,2].
- At the same time, to prepend a node (push at the beginning of the list), we firstly create a node and then change pointers so that the new node first links to the rest of the list, and then the head points to our new node (we know that the initial list is not empty):
const pushFront = (head) => {
let newNode = new ListNode(0);
newNode.next = head;
head = newNode;
return head;
};
We returned our new list head=[0,1,2].
Prepending a node can be made in constant O(1) time while to append to the last node we have to traverse the list till the last node is found. This can be made in linear O(n) time when n is the length of the list.
Deleting a node
To delete a node we can use a simple approach of mutating the nodes where we just change the values of a node we’re going to delete to its next node’s values (you can find a similar Leetcode problem here):
const deleteNode = (node) => {
node.val = node.next.val;
node.next = node.next.next;
}
Here we don’t return anything as we just changed the values in place.
Traversing the list
In a singly linked list, we can move only in one direction, forward. To traverse through the list, we should define an additional pointer to keep track of the current node we’re working on. We have to start from the head and keep following the next pointers until we reach the null pointer.
For each iteration, we check if the current node exists (not equal to null). When we reach the null, we reach the end of the list:
let curNode = head;
while (curNode) {
curNode = curNode.next;
}
Similarly, getting the last element can be implement as follows (we know that the list is not empty):
const getLast = (head) => {
let curNode = head;
while (curNode) {
curNode = curNode.next;
}
return curNode;
};
Now we can traverse the list with one additional pointer. In the next articles, I’ll show you how we can search an element in the list faster and more efficiently, using the two-pointers approach.
I hope this article helped you to understand the basics of a singly linked list.
This content originally appeared on DEV Community and was authored by Veronika Fatikhova
Veronika Fatikhova | Sciencx (2022-04-13T23:01:12+00:00) The Linked List in JavaScript: implementation, operations (basics). Retrieved from https://www.scien.cx/2022/04/13/the-linked-list-in-javascript-implementation-operations-basics/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.