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
Top comments (0)