Hello, fellow learners! 🌟 Welcome to my journey into the fascinating world of Data Structures and Algorithms (DSA) using the powerful language of C++. In my quest to demystify this exciting field, today, I'm going to explore one of the foundational concepts - the "Linked List."
Understanding the Linked List:
Imagine a linked list as a chain of elements, each holding a reference to the next element. Unlike arrays, which have a fixed size, linked lists are dynamic and can grow or shrink as needed. This flexibility makes them a valuable asset in DSA and various applications.
How Does a Linked List Work?
In a linked list, each element is called a "node." Each node consists of two parts: the data it holds and a reference (or a pointer) to the next node in the sequence. The last node typically points to a special value, often "null," indicating the end of the list.
Implementation Techniques:
Linked lists can be implemented in several ways, but there are two primary techniques I should be familiar with:
1. Singly Linked List:
In a singly linked list, each node points to the next node, forming a unidirectional chain.
This type of linked list is relatively straightforward and often used for its simplicity.
2. Doubly Linked List:
In a doubly linked list, each node has two pointers, one pointing to the next node and the other to the previous node.
This allows for easier traversal in both directions but requires slightly more memory to store the extra pointer.
3.Circular Linked List:
A Circular Linked List is a data structure where the last node points back to the first node, forming a continuous loop.
Each node in this structure has two components: data and a reference to the next node.
The traversal of a Circular Linked List can start from any node, and you can keep moving from one node to the next until you return to the starting node.
Circular Linked Lists are useful in various applications, including scheduling tasks in a round-robin manner and managing processes that cycle continuously.
Why Are Linked Lists Important in DSA?
Linked lists are essential because they provide dynamic data storage, making them ideal for situations where the size of the data structure can change during program execution. Here are a few reasons why understanding linked lists is crucial in DSA:
Dynamic Memory Allocation: Linked lists allow you to allocate memory for new elements as you go, ensuring efficient memory usage.
Insertions and Deletions: They excel at insertions and deletions, as you can easily reassign pointers to rearrange the list.
Versatility: Linked lists serve as the building blocks for more complex data structures like stacks, queues, and hash tables.
As I embark on this journey, keep in mind that understanding the basic concepts like linked lists is a significant milestone. These concepts are the foundation for tackling more intricate data structures and algorithms down the road.
We'll also include the code for basic operations like inserting, deleting, and displaying elements in the linked lists.
Singly Linked List:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
class SinglyLinkedList {
private:
Node* head;
public:
SinglyLinkedList() {
head = nullptr;
}
void insert(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
void remove(int value) {
if (head == nullptr) {
return;
}
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
} else {
Node* current = head;
while (current->next != nullptr) {
if (current->next->data == value) {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
return;
}
current = current->next;
}
}
}
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
};
int main() {
SinglyLinkedList sll;
sll.insert(10);
sll.insert(20);
sll.insert(30);
sll.display(); // Output: 10 -> 20 -> 30 -> nullptr
sll.remove(20);
sll.display(); // Output: 10 -> 30 -> nullptr
return 0;
}
Doubly Linked List:
#include <iostream>
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int value) {
data = value;
prev = nullptr;
next = nullptr;
}
};
class DoublyLinkedList {
private:
Node* head;
public:
DoublyLinkedList() {
head = nullptr;
}
void insert(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
void remove(int value) {
if (head == nullptr) {
return;
}
if (head->data == value) {
Node* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
}
delete temp;
} else {
Node* current = head;
while (current->next != nullptr) {
if (current->next->data == value) {
Node* temp = current->next;
current->next = current->next->next;
if (current->next != nullptr) {
current->next->prev = current;
}
delete temp;
return;
}
current = current->next;
}
}
}
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " <-> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insert(10);
dll.insert(20);
dll.insert(30);
dll.display(); // Output: 10 <-> 20 <-> 30 <-> nullptr
dll.remove(20);
dll.display(); // Output: 10 <-> 30 <-> nullptr
return 0;
}
Circular Linked List:
cppCopy codeclass Node {
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class CircularLinkedList {
private:
Node* head;
public:
CircularLinkedList() : head(nullptr) {}
void insert(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
newNode->next = head; // Point back to itself to create a circular link
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
}
}
void display() {
if (!head) return;
Node* current = head;
do {
std::cout << current->data << " -> ";
current = current->next;
} while (current != head);
std::cout << " (Back to Head)" << std::endl;
}
// Other operations like delete, search, etc. can be added here.
};
You can use these implementations as a starting point and add more functionality as needed for your specific use cases.
These are basic implementations of singly and doubly linked lists in C++. You can further enhance and customize these implementations to suit your specific needs. Happy coding!