Linked Lists
Linked lists are linear data structures where elements are stored in nodes, and each node contains data and a pointer/reference to the next node. Unlike arrays, linked list elements are not stored in contiguous memory locations.
Linked lists provide dynamic memory allocation and efficient insertion/deletion operations, making them ideal for applications where the size of data is unknown or frequently changes.
Singly Linked List
A singly linked list is the simplest type where each node points to the next node in the sequence:
Singly Linked List Implementation
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
// Insert at beginning
void insertAtBeginning(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}
// Insert at end
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
// Delete by value
void deleteValue(int value) {
if (head == nullptr) return;
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
while (current->next != nullptr && current->next->data != value) {
current = current->next;
}
if (current->next != nullptr) {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}
}
// Display list
void display() {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
// Search for value
bool search(int value) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == value) {
return true;
}
temp = temp->next;
}
return false;
}
// Destructor
~LinkedList() {
while (head != nullptr) {
Node* temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
LinkedList list;
// Insert elements
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtBeginning(5);
cout << "Linked List: ";
list.display();
// Search
cout << "Search 20: " << (list.search(20) ? "Found" : "Not Found") << endl;
cout << "Search 25: " << (list.search(25) ? "Found" : "Not Found") << endl;
// Delete
list.deleteValue(20);
cout << "After deleting 20: ";
list.display();
return 0;
}Doubly Linked List
A doubly linked list has nodes with pointers to both next and previous nodes, allowing bidirectional traversal:
Doubly Linked List Implementation
#include <iostream>
using namespace std;
struct DoublyNode {
int data;
DoublyNode* next;
DoublyNode* prev;
DoublyNode(int value) : data(value), next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
private:
DoublyNode* head;
DoublyNode* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// Insert at beginning
void insertAtBeginning(int value) {
DoublyNode* newNode = new DoublyNode(value);
if (head == nullptr) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
// Insert at end
void insertAtEnd(int value) {
DoublyNode* newNode = new DoublyNode(value);
if (tail == nullptr) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// Display forward
void displayForward() {
DoublyNode* temp = head;
cout << "Forward: ";
while (temp != nullptr) {
cout << temp->data << " <-> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
// Display backward
void displayBackward() {
DoublyNode* temp = tail;
cout << "Backward: ";
while (temp != nullptr) {
cout << temp->data << " <-> ";
temp = temp->prev;
}
cout << "NULL" << endl;
}
// Delete by value
void deleteValue(int value) {
DoublyNode* temp = head;
while (temp != nullptr && temp->data != value) {
temp = temp->next;
}
if (temp == nullptr) return; // Value not found
if (temp->prev) {
temp->prev->next = temp->next;
} else {
head = temp->next;
}
if (temp->next) {
temp->next->prev = temp->prev;
} else {
tail = temp->prev;
}
delete temp;
}
~DoublyLinkedList() {
while (head != nullptr) {
DoublyNode* temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
DoublyLinkedList list;
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
list.insertAtBeginning(5);
list.displayForward();
list.displayBackward();
list.deleteValue(20);
cout << "After deleting 20:" << endl;
list.displayForward();
return 0;
}Advantages and Disadvantages
Advantages
- Dynamic size - can grow or shrink during runtime
- Efficient insertion/deletion at beginning - O(1)
- Memory efficient - allocates memory as needed
- No memory waste - unlike arrays with fixed size
Disadvantages
- No random access - must traverse from head
- Extra memory for storing pointers
- Not cache friendly - elements scattered in memory
- No backward traversal in singly linked lists