Linked lists are a fundamental data structure in computer science, used to store a collection of elements. They consist of nodes, where each node contains a value and a reference (or link) to the next node in the sequence.
Dynamically resized
No copying overhead
Basics of Linked Lists
Node Structure:
Each node typically contains two parts:
Data: The value stored in the node. Next: A reference to the next node in the list.
Types of Linked Lists:
Singly Linked List:
Each node points to the next node in the sequence.
Structure
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
Traversal
void traverse() {
Node* current = head;
while (current) {
cout << current->data;
current = current->next;
}
}
Reverse Traversal
// Using stack
void traverseReverse(Node* head) {
std::stack<int> nodeStack;
// Traverse the linked list and push data onto the stack
Node* current = head;
while (current != nullptr) {
nodeStack.push(current->data);
current = current->next;
}
// Pop data from the stack to print in reverse order
while (!nodeStack.empty()) {
std::cout << nodeStack.top() << " ";
nodeStack.pop();
}
std::cout << std::endl;
}
void traverseReverseRecursive(Node* head) {
if (head == nullptr) return;
traverseReverseRecursive(head->next);
std::cout << head->data << " ";
}
Insert
void insert_at_beginning(int data) {
Node* new_node = new Node(data);
new_node->next = head;
head = new_node;
}
void insert_at_middle(int data, int position) {
if (position == 0) {
insert_at_beginning(data);
return;
}
Node* new_node = new Node(data);
Node* current = head;
for (int i = 0; i < position - 1 && current != nullptr; ++i) {
current = current->next;
}
if (current == nullptr) {
cout << "Position out of bounds" << endl;
delete new_node;
return;
}
new_node->next = current->next;
current->next = new_node;
}
void insert_at_end(int data) {
Node* new_node = new Node(data);
if (!head) {
head = new_node;
return;
}
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = new_node;
}
Delete
void delete_at_beginning() {
if (!head) return;
Node* temp = head;
head = head->next;
delete temp;
}
void LinkedList::delete_at_middle(int position) {
if (!head) return;
if (position == 0) {
delete_at_beginning();
return;
}
Node* current = head;
for (int i = 0; i < position - 1 && current->next != nullptr; ++i) {
current = current->next;
}
if (current->next == nullptr) {
std::cerr << "Position out of bounds" << std::endl;
return;
}
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}
void delete_at_end() {
if (!head) return;
if (!head->next) {
delete head;
head = nullptr;
return;
}
Node* current = head;
while (current->next && current->next->next) {
current = current->next;
}
delete current->next;
current->next = nullptr;
}
Doubly Linked List: Each node has two references, one to the next node and one to the previous node.
Structure
struct Node {
int data;
Node* next;
Node* prev;
Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};
Construct DLL
Node* constructDLL(vector<int>& arr) {
// code here
Node* head=new Node(arr[0]);
Node* temp=head;
for(int i=1;i<arr.size();i++){
Node * nn=new Node(arr[i]);
nn->prev=temp;
temp->next=nn;
temp=nn;
}
return head;
}
Insert
void DoublyLinkedList::insert_at_beginning(int data) {
Node* new_node = new Node(data);
if (head) {
new_node->next = head;
head->prev = new_node;
}
head = new_node;
}
void DoublyLinkedList::insert_at_middle(int data, int position) {
if (position == 0) {
insert_at_beginning(data);
return;
}
Node* new_node = new Node(data);
Node* current = head;
for (int i = 0; i < position - 1 && current != nullptr; ++i) {
current = current->next;
}
if (current == nullptr) {
cout << "Position out of bounds";
delete new_node;
return;
}
new_node->next = current->next;
if (current->next != nullptr) {
current->next->prev = new_node;
}
current->next = new_node;
new_node->prev = current;
}
void insert_at_end(int data) {
Node* new_node = new Node(data);
if (!head) {
head = new_node;
return;
}
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = new_node;
new_node->prev = current;
}
Delete
void delete_at_beginning() {
if (!head) {
std::cerr << "List is empty" << std::endl;
return;
}
Node* temp = head;
head = head->next;
if (head) {
head->prev = nullptr;
}
delete temp;
}
void DoublyLinkedList::delete_at_middle(int position) {
if (!head) {
std::cerr << "List is empty" << std::endl;
return;
}
if (position == 0) {
delete_at_beginning();
return;
}
Node* current = head;
for (int i = 0; i < position && current != nullptr; ++i) {
current = current->next;
}
if (current == nullptr) {
std::cerr << "Position out of bounds" << std::endl;
return;
}
if (current->prev) {
current->prev->next = current->next;
}
if (current->next) {
current->next->prev = current->prev;
}
delete current;
}
void DoublyLinkedList::delete_at_end() {
if (!head) {
std::cerr << "List is empty" << std::endl;
return;
}
Node* current = head;
while (current->next) {
current = current->next;
}
if (current->prev) {
current->prev->next = nullptr;
} else {
head = nullptr; // List had only one node
}
delete current;
}
Circular Linked List: The last node points back to the first node, forming a circle.
Important Algorithms
Tortoise Hare
bool detect_cycle() {
if (!head || !head->next) {
return false;
}
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next
if (fast == slow) {
return true;
}
}
return false;
}
Middle of an element
Node* find_middle() {
if (!head) {
return nullptr;
}
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
Reverse a linkedlist (3 - pointer approach)
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while(curr != NULL){
ListNode* forward = curr->next;
curr->next = prev;
prev = curr;
curr = forward;
}
return prev;
}
Merge Sorted Lists
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// Create a dummy node to act as the start of the merged list
ListNode dummy(0);
ListNode* tail = &dummy;
// Traverse both lists
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// If one of the lists is not empty, append the remaining nodes
if (l1 != NULL) {
tail->next = l1;
} else {
tail->next = l2;
}
return dummy.next;
}
Applications:
Dynamic Memory Management
Implementing Queues and Stacks
Graph Representations
Routing Tables in Networking
Stay Connected! If you enjoyed this post, don’t forget to follow me on social media for more updates and insights:
Twitter: madhavganesan
Instagram: madhavganesan
LinkedIn: madhavganesan