What is Linked List?
A linked list is a dynamic data structure used to store a collection of elements. Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each element, called a node, contains the data and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements.
Types of Linked Lists:
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
Singly Linked List:
A singly linked list is a linear data structure in which the elements are not stored in contiguous memory locations and each element called nodes is connected only to its next element using a pointer.
Each node contains two parts:
1. Data: The value stored in the node.
2. Next: A pointer/reference to the next node in the sequence.
#include <iostream>
using namespace std;
class Node
{
int data; // Data part of the node
Node* next; // Pointer to the next node
// Make LinkedList a friend class to access private members
friend class LinkedList;
};
class LinkedList
{
Node* head; // Pointer to the first node in the list
public:
// Constructor to initialize the head pointer
LinkedList() {
head = nullptr;
}
// Insert a new node at the beginning of the list
bool insertAtStart(int val) {
Node* newNode = new Node;
newNode->data = val;
newNode->next = head;
head = newNode;
return true;
}
// Delete the first node of the list
bool deleteFromStart() {
if (head == nullptr) {
return false;
} else {
Node* Start = head;
head = head->next;
delete Start;
return true;
}
}
// Insert a new node at the end of the list
bool insertAtEnd(int val) {
Node* newNode = new Node;
newNode->data = val;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
return true;
} else {
Node* Curr = head;
while (Curr->next != nullptr) {
Curr = Curr->next;
}
Curr->next = newNode;
return true;
}
}
// Delete the last node of the list
bool deleteFromEnd() {
if (head == nullptr) {
return false;
} else {
Node* Curr = head, * Prev = nullptr;
while (Curr->next != nullptr) {
Prev = Curr;
Curr = Curr->next;
}
if (Prev == nullptr) {
head = nullptr;
} else {
Prev->next = nullptr;
}
delete Curr;
Curr = nullptr;
return true;
}
}
// Insert a new node after a specific value
bool insertAfterSpecificValue(int Sval, int Nval) {
Node* newNode = new Node;
newNode->data = Nval;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
return true;
}
Node* Curr = head;
while (Curr != nullptr) {
if (Curr->data == Sval) {
newNode->next = Curr->next;
Curr->next = newNode;
return true;
}
Curr = Curr->next;
}
return false;
}
// Reverse the linked list
bool ReverseList() {
if (head == nullptr) {
return false;
} else if (head->next == nullptr) {
return true;
} else {
Node* Curr = head, * Next = nullptr, * Prev = nullptr;
while (Curr != nullptr) {
Next = Curr->next;
Curr->next = Prev;
Prev = Curr;
Curr = Next;
}
head = Prev;
return true;
}
}
// Sort the linked list
bool SortList() {
if (head == nullptr) {
return false;
} else if (head->next == nullptr) {
return true;
} else {
Node* Curr = head;
while (Curr->next != nullptr) {
Node* Next = Curr->next;
while (Next != nullptr) {
if (Next->data < Curr->data) {
swap(Next->data, Curr->data);
}
Next = Next->next;
}
Curr = Curr->next;
}
return true;
}
}
// Merge another linked list into this one
void MergeLists(LinkedList* L2) {
if (head == nullptr || L2->head == nullptr)
return;
Node* Curr1 = head;
while (Curr1->next != nullptr)
Curr1 = Curr1->next;
Curr1->next = L2->head;
L2->head = nullptr;
}
// Remove duplicate values from the list
bool RemoveDuplicates() {
if (head == nullptr)
return false;
Node* Curr1 = head;
while (Curr1 != nullptr) {
Node* Prev = Curr1;
Node* Curr2 = Curr1->next;
while (Curr2 != nullptr) {
if (Curr2->data == Curr1->data) {
Prev->next = Curr2->next;
delete Curr2;
Curr2 = Prev->next;
} else {
Prev = Curr2;
Curr2 = Curr2->next;
}
}
Curr1 = Curr1->next;
}
return true;
}
// Display the elements of the list
void Display() {
if (head == nullptr) {
cout << "List is Empty!" << endl;
} else {
Node* Curr = head;
while (Curr != nullptr) {
cout << Curr->data << " ";
Curr = Curr->next;
}
cout << endl;
}
}
// Destructor to clean up the list
~LinkedList() {
while (head != nullptr) {
Node* Curr = head;
head = head->next;
delete Curr;
}
}
};
int main() {
LinkedList List1;
List1.insertAtEnd(1);
List1.insertAtEnd(2);
List1.insertAtEnd(3);
List1.insertAtEnd(4);
List1.insertAtEnd(3);
List1.insertAtEnd(4);
List1.insertAtEnd(3);
List1.Display();
return 0;
}
Doubly Linked List:
Doubly Linked List is a variation of linked list in which navigation is possible in both ways, either forward and backward easily as compared to singly linked list.
Each node contains three parts:
1. Data: The value stored in the node.
2. Next: A pointer/reference to the next node in the sequence.
3. Previous: A pointer/reference to the previous node in the sequence.
#include <iostream>
using namespace std;
// Forward declaration of DoublyLinkedList class
class DoublyLinkedList;
class DNode {
int Data; // Data part of the node
DNode* Next; // Pointer to the next node
DNode* Prev; // Pointer to the previous node
// Make DoublyLinkedList a friend class to access private members
friend class DoublyLinkedList;
};
class DoublyLinkedList {
DNode* Head; // Pointer to the first node in the list
public:
// Constructor to initialize the head pointer
DoublyLinkedList() {
Head = nullptr;
}
// Insert a new node at the beginning of the list
bool insertAtStart(int Value) {
DNode* newNode = new DNode;
newNode->Data = Value;
newNode->Next = Head;
newNode->Prev = nullptr;
if (Head != nullptr) {
Head->Prev = newNode;
}
Head = newNode;
return true;
}
// Insert a new node at the end of the list
bool insertAtEnd(int Value) {
DNode* newNode = new DNode;
newNode->Data = Value;
newNode->Next = nullptr;
if (Head == nullptr) {
newNode->Prev = nullptr;
Head = newNode;
return true;
} else {
DNode* Curr = Head;
while (Curr->Next != nullptr) {
Curr = Curr->Next;
}
Curr->Next = newNode;
newNode->Prev = Curr;
return true;
}
}
// Insert a new node in a sorted order
bool sortedInsert(int Value) {
DNode* newNode = new DNode;
newNode->Data = Value;
if (Head == nullptr || Value <= Head->Data) {
newNode->Next = Head;
newNode->Prev = nullptr;
if (Head != nullptr) {
Head->Prev = newNode;
}
Head = newNode;
return true;
} else {
DNode* Curr = Head;
while (Curr->Next != nullptr && Curr->Next->Data <= Value) {
Curr = Curr->Next;
}
newNode->Next = Curr->Next;
newNode->Prev = Curr;
if (Curr->Next != nullptr) {
Curr->Next->Prev = newNode;
}
Curr->Next = newNode;
return true;
}
}
// Delete the first node of the list
bool deleteFromStart() {
if (Head == nullptr) {
cout << "List is Empty!" << endl;
return false;
} else {
DNode* Temp = Head;
Head = Head->Next;
if (Head != nullptr) {
Head->Prev = nullptr;
}
delete Temp;
return true;
}
}
// Delete the last node of the list
bool deleteFromEnd() {
if (Head == nullptr) {
cout << "List is Empty!" << endl;
return false;
} else {
if (Head->Next == nullptr) {
delete Head;
Head = nullptr;
} else {
DNode* Curr = Head;
while (Curr->Next != nullptr) {
Curr = Curr->Next;
}
Curr->Prev->Next = nullptr;
delete Curr;
}
return true;
}
}
// Search for a node with a specific value
DNode* Search(int Value) {
DNode* Curr = Head;
while (Curr != nullptr) {
if (Curr->Data == Value) {
return Curr;
}
Curr = Curr->Next;
}
return nullptr;
}
// Delete a node with a specific value
bool deleteSpecificValue(int Value) {
DNode* Temp = Search(Value);
if (Temp == nullptr) {
cout << "The Value " << Value << " not found in the List!" << endl;
return false;
}
if (Temp->Prev != nullptr) {
Temp->Prev->Next = Temp->Next;
} else {
Head = Temp->Next;
}
if (Temp->Next != nullptr) {
Temp->Next->Prev = Temp->Prev;
}
delete Temp;
return true;
}
// Display the elements of the list
void Display() {
if (Head == nullptr) {
cout << "List is Empty!" << endl;
} else {
cout << "List: ";
DNode* Curr = Head;
while (Curr != nullptr) {
cout << Curr->Data << " ";
Curr = Curr->Next;
}
cout << endl;
}
}
// Get the number of nodes in the list
int Size() {
if (Head == nullptr) {
return 0;
} else {
int size = 0;
DNode* Curr = Head;
while (Curr != nullptr) {
size++;
Curr = Curr->Next;
}
return size;
}
}
// Destructor to clean up the list
~DoublyLinkedList() {
while (Head != nullptr) {
DNode* Curr = Head;
Head = Head->Next;
delete Curr;
}
}
};
int main() {
DoublyLinkedList List1;
List1.insertAtEnd(2);
List1.insertAtEnd(3);
List1.insertAtEnd(3);
List1.insertAtEnd(5);
List1.insertAtEnd(6);
List1.insertAtEnd(7);
List1.insertAtEnd(8);
List1.Display();
return 0;
}
Circular Singly Linked List:
The Circular Linked List is a list where all nodes are connected to form a circle. In a circular singly linked list, the first node and the last node are connected to each other which forms a circle. There is no NULL at the end.
#include <iostream>
using namespace std;
class Node {
private:
int data; // Data part of the node
Node* next; // Pointer to the next node
friend class CircularSinglyLinkedList; // Make CircularSinglyLinkedList a friend class to access private members
};
class CircularSinglyLinkedList {
private:
Node* head; // Pointer to the last node in the list
public:
// Constructor to initialize the head pointer
CircularSinglyLinkedList() {
head = nullptr;
}
// Check if the list is empty
bool isEmpty() {
return head == nullptr;
}
// Insert a new node at the beginning of the list
void insertAtStart(int val) {
Node* newNode = new Node;
newNode->data = val;
if (isEmpty()) {
newNode->next = newNode;
head = newNode;
} else {
newNode->next = head->next;
head->next = newNode;
}
}
// Insert a new node at the end of the list
void insertAtEnd(int val) {
Node* newNode = new Node;
newNode->data = val;
if (isEmpty()) {
newNode->next = newNode;
head = newNode;
} else {
newNode->next = head->next;
head->next = newNode;
head = newNode;
}
}
// Print the elements of the list from head to end
void Display() {
if (isEmpty()) {
cout << "List is Empty!" << endl;
} else {
Node* curr = head->next;
do {
cout << curr->data << " ";
curr = curr->next;
} while (curr != head->next);
cout << endl;
}
}
// Delete a node from the beginning of the list
void deleteFromStart() {
if (!isEmpty()) {
Node* temp = head->next;
if (temp == head) {
delete temp;
head = nullptr;
} else {
head->next = temp->next;
delete temp;
}
}
}
// Destructor to clean up the list
~CircularSinglyLinkedList() {
while (!isEmpty()) {
deleteFromStart();
}
}
};
int main() {
CircularSinglyLinkedList list;
list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.Display(); // Output: 1 2 3
list.insertAtStart(0);
list.Display(); // Output: 0 1 2 3
list.deleteFromStart();
list.Display(); // Output: 1 2 3
return 0;
}
Circular Doubly Linked List:
Circular Doubly Linked List has properties of both doubly linked list and circular singly linked list or circular linked list in which two consecutive elements are linked by the previous and next pointer and the last node points to the first node by the next pointer and also the first node points to the last node by the previous pointer.
#include <iostream>
using namespace std;
class CDNode {
private:
int data; // Data part of the node
CDNode* next; // Pointer to the next node
CDNode* prev; // Pointer to the previous node
friend class CircularDoublyLinkedList; // Make CircularDoublyLinkedList a friend class to access private members
};
class CircularDoublyLinkedList {
private:
CDNode* head; // Pointer to the first node in the list
public:
// Constructor to initialize the head pointer
CircularDoublyLinkedList() {
head = nullptr;
}
// Insert a new node at the beginning of the list
bool insertAtHead(int value) {
CDNode* newNode = new CDNode;
newNode->data = value;
newNode->next = head;
newNode->prev = nullptr;
if (head == nullptr) {
head = newNode;
newNode->next = newNode;
newNode->prev = newNode;
} else {
CDNode* lastNode = head->prev;
newNode->next = head;
newNode->prev = lastNode;
head->prev = newNode;
lastNode->next = newNode;
head = newNode;
}
return true;
}
// Insert a new node at the end of the list
bool insertAtEnd(int value) {
CDNode* newNode = new CDNode;
newNode->data = value;
newNode->next = nullptr;
newNode->prev = nullptr;
if (head == nullptr) {
head = newNode;
head->next = head;
head->prev = head;
} else {
CDNode* lastNode = head->prev;
newNode->next = head;
newNode->prev = lastNode;
head->prev = newNode;
lastNode->next = newNode;
}
return true;
}
// Print the elements of the list from head to end
void Print() {
if (head == nullptr) {
cout << "List is Empty!" << endl;
} else {
CDNode* curr = head;
do {
cout << curr->data << " ";
curr = curr->next;
} while (curr != head);
cout << endl;
}
}
// Search for a node with a specific value
bool Search(int value) {
if (head == nullptr) {
return false;
}
CDNode* curr = head;
do {
if (curr->data == value) {
return true;
}
curr = curr->next;
} while (curr != head);
return false;
}
// Erase a node with a specific value
bool Erase(int value) {
if (head != nullptr) {
CDNode* curr = head;
do {
if (curr->data == value) {
if (curr == head) {
head = head->next;
}
CDNode* prevNode = curr->prev;
CDNode* nextNode = curr->next;
prevNode->next = nextNode;
nextNode->prev = prevNode;
delete curr;
return true;
}
curr = curr->next;
} while (curr != head);
}
return false;
}
// Print the elements of the list from end to head
void printBack() {
if (head == nullptr) {
cout << "List is Empty!" << endl;
} else {
CDNode* curr = head->prev;
do {
cout << curr->data << " ";
curr = curr->prev;
} while (curr != head->prev);
cout << endl;
}
}
// Insert a new node after a specific key
bool insertAfter(int key, int value) {
if (head != nullptr) {
CDNode* curr = head;
do {
if (curr->data == key) {
CDNode* newNode = new CDNode;
newNode->data = value;
newNode->next = curr->next;
newNode->prev = curr;
curr->next->prev = newNode;
curr->next = newNode;
return true;
}
curr = curr->next;
} while (curr != head);
}
return false;
}
// Get the number of nodes in the list
int Size() {
if (head == nullptr) {
return 0;
}
int count = 0;
CDNode* current = head;
do {
count++;
current = current->next;
} while (current != head);
return count;
}
// Destructor to clean up the list
~CircularDoublyLinkedList() {
if (head == nullptr) {
return;
}
CDNode* current = head;
CDNode* nextNode;
do {
nextNode = current->next;
delete current;
current = nextNode;
} while (current != head);
head = nullptr;
}
};
