What is a Singly Linked List?
In the previous post, Data Structure - Linked List, we explored the general concepts of linked list and their structure.
Here, we dive into the singly linked list and its three operations:
- Insertion - add an element at the beginning and end
- deletion - remove an element at its index or value
- Search - find an element given its value
Node Class
It represents a single node in the linked list with two properties: value to store the data and next to reference the next node in the list
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
Linked List Class
isEmpty: Check if the linked list is empty or norgetSize: Get the current size of the linked listprint: Display the linked list
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
getSize() {
return this.size;
}
print() {
if (this.isEmpty()) {
return "the list is empty";
}
let curr = this.head;
let ListValues = "";
while (curr) {
ListValues += `${curr.value} `;
curr = curr.next;
}
return ListValues;
}
}
Adding an Element at the Front (prepend)
prepend(value) {
// Create a new node with the provided value
const node = new Node(value);
// Check if the linked list is empty
if (this.isEmpty()) {
// If empty, set the new node as the head node
this.head = node;
} else {
// If not empty, set the next pointer of the new node to the current head
node.next = this.head;
// Update the head of the linked list to the new node
this.head = node;
}
// Increase the size by 1
this.size += 1;
}
Adding an Element at the Back (append)
append(value) {
// Create a new node with the provided value
const node = new Node(value);
// Check if the linked list is empty
if (this.isEmpty()) {
// If empty, set the new node as the head node
this.head = node;
} else {
// If not empty, traverse the list to find the last node
let prev = this.head;
// Traverse the nodes until the last node
while (prev.next) {
prev = prev.next;
}
// Set the next pointer of the last node to the new node
prev.next = node;
}
// Increase the size by 1
this.size += 1;
}
Remove a Node Based On Index
removeFrom(index) {
// Check if the index is out of bounds
if (index < 0 || index >= this.size) {
return null;
}
let removedNode;
// If index is 0, remove the first node
if (index === 0) {
// Store the first node as removedNode
removedNode = this.head;
// Update the head node to the next node
this.head = this.head.next;
} else {
// If index is not 0, traverse the list to find the node beofre the index
let prev = this.head;
for (let i = 0; i < index - 1; i += 1) {
prev = prev.next;
}
// Store the node as removedNode
removedNode = prev.next;
// Update the prev node's next pointer to removedNode's next node
prev.next = removedNode.next;
}
// Increase the size by 1
this.size -= 1;
return removedNode.value;
}
Search Based On the Value
search(value) {
// Check if the linked list is empty
if (this.isEmpty()){
// If empty, return -1
return -1
}
// Set index to 0 and curr to the head node
let index = 0
let curr = this.head
// Traverse through these nodes
while(curr){
// If the curr value is equal to the value, return the index
if (curr.value === value) {
return index
}
// Update curr node to the next node
curr = curr.next
// Increase index by 1
index++
}
// Return -1 if value is not found after traversed the list
return -1
}
Reverse the Order of the List
reverse() {
// Initialize prev node as null
let prev = null;
// Set current node as the head of the list
let curr = this.head;
// Traverse these nodes until current node becomes null
while (curr) {
// Store the next node in a temporary variable
let { next } = curr; // let next = curr.next;
// Reverse the next pointer of the current node to point to the prev node
curr.next = prev;
// Update prev node to current node and current node to next node
prev = curr;
curr = next;
}
// Set the head to the last node
this.head = prev;
}
Full Code
Here is the full code for this post.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
getSize() {
return this.size;
}
prepend(value) {
const node = new Node(value);
if (this.isEmpty()) {
this.head = node;
} else {
node.next = this.head;
this.head = node;
}
this.size += 1;
}
append(value) {
const node = new Node(value);
if (this.isEmpty()) {
this.head = node;
} else {
let prev = this.head;
while (prev.next) {
prev = prev.next;
}
prev.next = node;
}
this.size += 1;
}
removeFrom(index) {
if (index < 0 || index >= this.size) {
return null;
}
let removedNode;
if (index === 0) {
removedNode = this.head;
this.head = this.head.next;
} else {
let prev = this.head;
for (let i = 0; i < index - 1; i += 1) {
prev = prev.next;
}
removedNode = prev.next;
prev.next = removedNode.next;
}
this.size -= 1;
return removedNode.value;
}
reverse() {
let prev = null;
let curr = this.head;
while (curr) {
let { next } = curr; // let next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
this.head = prev;
}
search(value) {
if (this.isEmpty()) {
return -1;
}
let index = 0;
let curr = this.head;
while (curr) {
if (curr.value === value) {
return index;
}
curr = curr.next;
index++;
}
return -1;
}
print() {
if (this.isEmpty()) {
return "the list is empty";
}
let curr = this.head;
let ListValues = "";
while (curr) {
ListValues += `${curr.value} `;
curr = curr.next;
}
return ListValues;
}
}
Resources
I appreicate the way Codevolution, a Youtuber, explains the process of coding a JavaScript implementation for a Linked List, with clear visuals. The playlist covers more linked list methods than this post mentioned, so I highly recommend exploring the JavaScript Data Structures playlist to deepen your knowledge on data structures.
JavaScript Data Structure 14 - Linked List Class
JavaScript Data Structure 15 - Linked List Preend
JavaScript Data Structure 17 - Linked List Append
JavaScript Data Structure 19 - Linked List Remove
JavaScript Data Structure 21 - Linked List Search
JavaScript Data Structure 22 - Linked List Reverse
Thank you!
Thank you for your time and for reading this!