Hi π, welcome back to this series on linked lists. In our last article, we learned about the basics of linked lists, including their definition, terminologies, its difference with arrays, and the types of linked lists. I promised we'd dive deeper into the implementation of linked lists, so let's get started.
Course Outline
Introduction
As we've learned in the previous article, Linked Lists are fundamental data structures in the world of programming. They consist of nodes, where each node contains data and a reference (or link) to the next node (in a singly linked list) or both the next and previous nodes (in a doubly linked list) in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, allowing for efficient insertions and deletions.
Understanding the concept of a linked list is crucial for mastering data structures and algorithms. In this article, we'll dive deeper into the implementation of linked lists, starting with the basics of a singly linked list.
Implementing Singly Linked Lists
A Singly Linked List is the simplest type of linked list, where each node points to the next node in the sequence. Just like in the image below.
Now, it's time to start implementing our singly linked list basics operations. Shall we?
Creating new Node
Let's start by creating a new Node class. The Node class will have a constructor that takes in the data for the node and a next pointer which is initially set to null.
// Node class for Singly Linked List
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
This newly created Node class (which represents a node in the linked list) can be visualized as below.
Before we proceed, let's create a new instance of our SinglyLinkedList class that will hold our linked list operations.
// Singly Linked List class
class SinglyLinkedList {
constructor() {
this.head = null;
}
// Operations come here π
}
Insert at the Beginning
class SinglyLinkedList {
constructor() {
this.head = null;
}
// Previous `SinglyLinkedList` class codes here π
// .
// .
// .
// Insert at the beginning
insertAtBeginning(data) {
const newNode = new Node(data); // Create a new node with the given data
newNode.next = this.head; // Set the new node's next pointer to the current head
this.head = newNode; // Update the head to be the new node
}
// Other operations come here π
// .
// .
// .
}
Explanation: Inserting at the beginning is like someone new joining the line at the front. They become the new first person, linking to the previous first.
Insert at the End
class SinglyLinkedList {
constructor() {
this.head = null;
}
// Previous `SinglyLinkedList` class codes here π
// .
// .
// .
// Insert at the end
insertAtEnd(data) {
const newNode = new Node(data); // Create a new node with the given data
// check if the list does not have a head i.e the list is empty
// NOTE: Every non-empty linked list will have a head
if (!this.head) {
this.head = newNode; // If the list is empty, set the new node as the head
return;
}
let current = this.head; // Start at the head of the list
while (current.next) {
current = current.next; // Move to the next node in the list by updating the current node
}
current.next = newNode; // Set the next pointer of the last node to the new node
}
// Other operations come here π
// .
// .
// .
}
Explanation: Inserting at the end is like someone joining the line at the very end. We need to walk to the end to find the last person, then link them to the new person.
Delete a Node
class SinglyLinkedList {
constructor() {
this.head = null;
}
// Previous `SinglyLinkedList` class codes here π
// .
// .
// .
// Delete a node
deleteNode(data) {
if (!this.head) return; // If the list is empty, do nothing
if (this.head.data === data) {
this.head = this.head.next; // If the node to delete is the head, update the head to the next node
return;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
current.next = current.next.next; // If the node to delete is found, update the next pointer to skip it
return;
}
current = current.next;
}
}
// Other operations come here π
// .
// .
// .
}
Explanation: Deleting a node is like someone in the middle of the line deciding to leave. We find that person and connect the one before them to the one after them.
Search for a Node
class SinglyLinkedList {
constructor() {
this.head = null;
}
// Previous `SinglyLinkedList` class codes here π
// .
// .
// .
// Search note
search(data) {
let current = this.head; // Start at the head of the list
while (current) {
if (current.data === data) {
// If the data is found, return true
return true;
}
current = current.next; // Move to the next node
}
return false;
}
// Other operations come here π
// .
// .
// .
}
Explanation: Searching for a node is like trying to find a specific person in the line. We start at the front and ask each person until we find them or reach the end.
Traverse the List
class SinglyLinkedList {
constructor() {
this.head = null;
}
// Previous `SinglyLinkedList` class codes here π
// .
// .
// .
traverse() {
let current = this.head; // Start at the head of the list
while (current) {
console.log(current.data); // Print the data of the current node
current = current.next; // Move to the next node
}
}
}
// End of class
Explanation: Traversing is like walking down the line and greeting each person. We start at the front and keep moving until we reach the end.
Conclusion
In this article, we've learned about the basics operations of linked lists and how to implement them in JavaScript. In the next article, we'll be learning about Doubly Linked Lists.
Remember, mastering linked lists requires practice. Continue solving problems and implementing these data structures in various scenarios.
Stay Updated and Connected
To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:
Stay tuned and happy coding π¨βπ»π
Top comments (0)