A linked list is a linear data structure where elements, called nodes, are stored in a sequence, and each node points to the next one in the list. Unlike arrays, linked lists do not require contiguous memory locations, making them more flexible for dynamic memory allocation. Linked lists are particularly useful when the size of the data structure is not known beforehand and frequent insertions and deletions are needed.
A node in a linked list typically contains:
The head of the list points to the first node. The last node points to NULL (or nullptr in C++), indicating the end of the list.
Insertion:
Deletion:
Traversal: Accessing all nodes in the list, usually for printing or searching.
Search: Finding a node with a specific value.
Update: Modifying the data of a node.
A singly linked list is the most basic type of linked list, where each node contains data and a reference (pointer) to the next node in the list. The last node’s reference points to NULL, signifying the end of the list.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
// Insertion at the beginning
void insertAtBeginning(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}
// Insertion at the 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;
}
// Deletion from the beginning
void deleteFromBeginning() {
if (head == nullptr) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
head = head->next;
delete temp;
}
// Traversing the list
void traverse() {
if (head == nullptr) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Searching for an element
bool search(int value) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == value)
return true;
temp = temp->next;
}
return false;
}
// Destructor to free memory
~LinkedList() {
Node* temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
LinkedList list;
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtBeginning(5);
cout << "List after insertions: ";
list.traverse(); // Output: 5 10 20
list.deleteFromBeginning();
cout << "List after deletion from beginning: ";
list.traverse(); // Output: 10 20
cout << "Is 20 in the list? " << (list.search(20) ? "Yes" : "No") << endl; // Yes
return 0;
}
A doubly linked list is a variation of the singly linked list where each node has two pointers: one pointing to the next node and another pointing to the previous node. This allows traversal in both directions (forward and backward).
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
private:
Node* head;
public:
DoublyLinkedList() : head(nullptr) {}
// Insertion at the beginning
void insertAtBeginning(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
return;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
}
// Insertion at the 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;
newNode->prev = temp;
}
// Deletion from the beginning
void deleteFromBeginning() {
if (head == nullptr) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
}
delete temp;
}
// Traversing the list from beginning
void traverseForward() {
if (head == nullptr) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Traversing the list from end
void traverseBackward() {
if (head == nullptr) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}
// Destructor to free memory
~DoublyLinkedList() {
Node* temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}
}
};
int main() {
DoublyLinkedList list;
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtBeginning(5);
cout << "Forward traversal: ";
list.traverseForward(); // Output: 5 10 20
cout << "Backward traversal: ";
list.traverseBackward(); // Output: 20 10 5
return 0;
}
In a circular linked list, the last node points back to the first node, forming a loop. This structure can be either singly or doubly linked. Circular linked lists are used in applications where you need continuous looping, such as in circular buffers or scheduling systems.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class CircularLinkedList {
private:
Node* head;
public:
CircularLinkedList() : head(nullptr) {}
// Insert at the beginning
void insertAtBeginning(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
newNode->next = head;
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head;
head = newNode;
}
}
// Traversing the list
void traverse() {
if (head == nullptr) {
cout << "List is empty!\n";
return;
}
Node* temp = head;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
cout << endl;
}
// Destructor to free memory
~CircularLinkedList() {
if (head == nullptr) return;
Node* temp = head;
do {
Node* nextNode =
Open this section to load past papers