Day 4: Understanding Linked Lists 🔗

Welcome to Day 4 of our Data Structures and Algorithms (DSA) series! Today, we’ll explore linked lists, an essential data structure that provides dynamic memory allocation and ease of insertion and deletion. By the end of this post, you’ll have a solid understanding of linked lists, their properties, and common operations performed on them. Let’s dive in! 🚀

please subscribe to my YouTube channel to support my channel and get more web development tutorials.

What is a Linked List? 🤔

A linked list is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element (called a node) contains a value and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements.

Key Characteristics of Linked Lists

• Dynamic Size: Linked lists can grow and shrink in size dynamically, making them flexible.
• Ease of Insertion/Deletion: Elements can be easily inserted or removed without reorganizing the entire structure.
• Non-Contiguous Storage: Elements are stored in non-contiguous memory locations, linked together using pointers.

Types of Linked Lists 📚

1. Singly Linked List

In a singly linked list, each node points to the next node, and the last node points to null.

2. Doubly Linked List

In a doubly linked list, each node contains two references: one to the next node and one to the previous node.

3. Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circular structure.

How to Implement a Singly Linked List in JavaScript 📜

Node Structure

First, we define a Node class to represent each element in the list.

class Node { constructor(data) { this.data = data; this.next = null; }
}

Linked List Structure

Next, we define a LinkedList class to manage the nodes.

class LinkedList { constructor() { this.head = null; } // Insert at the beginning insertAtBeginning(data) { let newNode = new Node(data); newNode.next = this.head; this.head = newNode; } // Insert at the end insertAtEnd(data) { let newNode = new Node(data); if (this.head === null) { this.head = newNode; return; } let temp = this.head; while (temp.next !== null) { temp = temp.next; } temp.next = newNode; } // Delete a node deleteNode(key) { let temp = this.head; let prev = null; // If the head node itself holds the key to be deleted if (temp !== null && temp.data === key) { this.head = temp.next; // Changed head return; } // Search for the key to be deleted while (temp !== null && temp.data !== key) { prev = temp; temp = temp.next; } // If key was not present in the list if (temp === null) return; // Unlink the node from the linked list prev.next = temp.next; } // Display the linked list printList() { let temp = this.head; while (temp !== null) { console.log(temp.data); temp = temp.next; } }
}

Common Operations on Linked Lists 🛠️

1. Inserting Elements

You can insert elements at the beginning, at the end, or at a specific position.

Example: Inserting at the Beginning

let list = new LinkedList();
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.printList(); // Output: 20 10

Example: Inserting at the End

let list = new LinkedList();
list.insertAtEnd(10);
list.insertAtEnd(20);
list.printList(); // Output: 10 20

2. Deleting Elements

You can delete elements by value or by position.

Example: Deleting a Node by Value

let list = new LinkedList();
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.deleteNode(20);
list.printList(); // Output: 10 30

3. Traversing a Linked List

Traversing a linked list means accessing each node in the list.

Example: Traversing the List

let list = new LinkedList();
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.printList(); // Output: 10 20 30

Time Complexity of Linked List Operations ⏱️

Understanding the time complexity of linked list operations helps in writing efficient code.

• Accessing Elements: O(n)
• Inserting/Deleting at the Beginning: O(1)
• Inserting/Deleting at the End: O(n)
• Inserting/Deleting at an Arbitrary Position: O(n)
• Searching for an Element: O(n)

Conclusion 🎯

Today, we explored linked lists, an essential data structure that offers dynamic memory allocation and ease of insertion and deletion. We learned how to implement a singly linked list in JavaScript and performed common operations. Understanding linked lists is crucial as they are the foundation for more complex data structures.

Series Index

Stay tuned for Day 5, where we will dive into Stacks, their properties, and operations. Feel free to share your thoughts or questions in the comments below. Happy coding! 💻

Follow and Subscribe: