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)
Start Your JavaScript Journey
If you're new to JavaScript or want a refresher, visit my blog on BuyMeACoffee to get started with the basics.
π Introduction to JavaScript: Your First Steps in Coding
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
Part | Title | Link |
---|---|---|
1 | Day 1: Introduction to Data Structures and Algorithms (DSA)π | Read |
2 | Day 2: Understanding Big O Notation π | Read |
3 | Day 3: Introduction to Arrays π | Read |
4 | Day 4: Understanding Linked Lists π | Read |
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:
- Instagram: devdivewithdipak
- Website: Dipak Ahirav
- Email: dipaksahirav@gmail.com
- YouTube: devDive with Dipak
- LinkedIn: Dipak Ahirav
Top comments (0)