Table of Content
Linked List
Linked List using CPP
Linked List
Linked List is a list of nodes. Node has two parts, one part containing the data and the other part containing the address of the next node of the list.
struct Node{
int data; //4 bytes
Node* next; //4 bytes
}
The first node is called the head node. The only information we keep for the list is the address of the head node. The address of the head node gives us access to the complete list. The address of the last node is NULL/0.
Types of Linked List
- Singly Linked List: Navigation is forward only.
- Doubly Linked List: Both Forward and Backward navigation is possible.
- Circular Linked List: The last node is linked to the first node.
Implementation of Singly Linked List
Creating a Node
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
int main() {
Node* head = nullptr;
head = new Node();
head->data = 1;
head->next = nullptr;
// Printing the node data
cout << "Node data: " << head->data << endl;
delete head; // Don't forget to free memory
return 0;
}
Here we created a node with data 1 and the next pointer pointing to NULL. We also freed the memory allocated to the node after printing the data.
Also don't forget to free the memory allocated to the node using the delete keyword, or else something bad will happen 😜💀.
Output:
Node data: 1
Creating a Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
int main() {
Node* head = nullptr;
head = new Node();
head->data = 1;
head->next = nullptr;
Node* second = new Node();
second->data = 2;
second->next = nullptr;
head->next = second;
Node* third = new Node();
third->data = 3;
third->next = nullptr;
second->next = third;
// Printing the linked list
cout << "Linked List: ";
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
// Freeing memory
delete head;
delete second;
delete third;
return 0;
}
In the above code we created three different nodes and updated the next pointers each nodes. You can also achieve the same thing by:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
int main() {
Node* head = new Node{1, nullptr}; // Create first node and initialize its data
Node* second = new Node{2, nullptr}; // Create second node and initialize its data
Node* third = new Node{3, nullptr}; // Create third node and initialize its data
// Link nodes
head->next = second;
second->next = third;
// Printing the linked list
cout << "Linked List: ";
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
// Freeing memory
delete head;
delete second;
delete third;
return 0;
}
In the above code we first initialized the data of the nodes while creating them. Then we linked the nodes and printed the linked list. Finally, we freed the memory allocated to the nodes.
Output:
Linked List: 1 2 3
This method creates unnecessary pointers which creates memory that is not useful. Below is a more optimized method to create a Linked List.
#include <iostream>
using namespace std;
struct Node{
int data;
Node* link;
};
int main(){
Node* head = new Node();
head->data = 1;
head->link = nullptr;
Node* current = new Node();
current->data = 2;
current->link = nullptr;
head->link = current;
current = new Node();
current->data = 3;
current->link = nullptr;
head->link->link = current;
return 0;
}
In this code, we are accessing the address of all the nodes of the list using the sequential link arrow function, so we need not create any extra pointers and move the head pointer.
Traversing a singly Linked List
It is a method to go through each node of a Linked List from the beginning until the end node is reached.
Count number of nodes in a Linked List
#include<iostream>
using namespace std;
struct Node{
int data;
Node* link;
};
void countNodes(Node *head){
int count = 0;
if (head == nullptr)
cout << "Linked List is empty!";
Node* ptr = nullptr;
ptr = head;
while(ptr != nullptr){
count++;
ptr = ptr -> link;
}
cout << count;
}
int main(){
countNodes(head); //assuming that a Linked List exist
return 0;
}
In the above code, we created a function countNodes that takes the head of the Linked List as an argument and counts the number of nodes in the list. We created a pointer ptr and assigned it to the head of the list. We traversed the list and incremented the count variable for each node. Finally, we printed the count variable.
Print the data of a list
#include<iostream>
using namespace std;
struct Node{
int data;
Node* link;
}
void printData(Node* head){
if(head == nullptr)
cout << "List is empty!";
Node* ptr = nullptr;
ptr = head;
while(ptr != nullptr){
cout << ptr->data;
ptr = ptr->link;
}
}
int main(){
printData(head);//assuming that a Linked List exist
return 0;
}
In the above code, we created a function printData that takes the head of the Linked List as an argument and prints the data of the list. We created a pointer ptr and assigned it to the head of the list. We traversed the list and printed the data of each node.
Insertion in a Linked List
Insert a node at the end of a list
Let's say that there is a list containing 3 nodes, and there's a node that we want to insert. We will assign a temp pointer to the node which we want to insert at the end. We will traverse the list using a pointer and we will stop at the last node of the list. We will update the link of the last node to the temp pointer.
#include<iostream>
using namespace std;
struct Node{
int data;
Node* link;
};
void insertAtEnd(Node* head, int data){
Node* ptr, *temp;
ptr = head;
temp = new Node();
temp -> data = data;
temp -> link = nullptr;
while(ptr -> link != nullptr){
ptr = ptr -> link;
}
ptr->link = temp;
}
int main(){
insertAtEnd(head, 123);
return 0;
}
Optimal code to create a Linked List using insertAtEnd function
#include<iostream>
using namespace std;
struct Node{
int data;
Node* link;
};
Node* insertAtEnd(Node* ptr, int data){
Node* temp = new Node();
temp->data = data;
temp->link = nullptr;
ptr->link = temp;
return temp;
}
int main(){
Node* head = new Node();
head->data = 1;
head->link = nullptr;
Node* ptr = head;
ptr = insertAtEnd(ptr, 2);
ptr = insertAtEnd(ptr, 3);
ptr = insertAtEnd(ptr, 4);
ptr = head;//move the pointer back to the head node after adding all the elements
while(ptr != nullptr){
cout << ptr->data;
ptr = ptr->link;
}
return 0;
}
In the above code, we created a Linked List using the insertAtEnd function. We created a head node and a pointer pointing to the head node. We inserted 4 nodes at the end of the list using the insertAtEnd function. After adding all the elements, we moved the pointer back to the head node and printed the data of the list.
Insert a node at the beginning of a list
Abstract code:
ptr -> link = head;
head = ptr;
Here the head is the first node of the list and ptr points to the node that we want to insert at the beginning.
Insert a new node at a given position in a list
Assuming that we already have a linked list and we want to insert a new node at the third position. We will create a new node (ptr2 pointing to it) first, and then we will need to traverse the list(ptr pointer). Now we will traverse the list till the node just before the position we want to insert the new node. (in this case till the 2nd node).
ptr2->link = ptr->link
//this joins the new node with the 3rd node
ptr->link = ptr2
//this joins the 2nd node with the inserted node
let's say there is a linked list with 4 nodes and I want to insert a new node at the 3rd position. We will create a new node and we will traverse the list till the 2nd node. We will update the link of the 2nd node to the new node and the link of the new node to the 3rd node.
#include<iostream>
using namespace std;
struct Node{
int data;
Node* link;
};
void insertAtPosition(Node* head, int data, int pos){
Node* ptr = head;
Node* temp = new Node();
temp->data = data;
temp->link = nullptr;
for(int i = 1; i < pos - 1; i++){
ptr = ptr->link;
}
temp->link = ptr->link;
ptr->link = temp;
}
int main(){
insertAtPosition(head, 123, 3);
return 0;
}
Deletion in a Linked List
Delete the first node of a list
To achieve this we need to create a pointer which points to the first node of the list and we'll have to move the head pointer to the 2nd node and we'll free the memory of the temp pointer.
//In this function we are passing the head function and we return the updated head.
Node* delFirst(Node* head){
if(head == nullptr)
cout << "List is empty!";
else{
Node* temp = head;
head = head*link;
delete temp;
}
return head;
}
Delete the last node of a list
Suppose we already have a Linked List and we want to delete the last node of it. We will create a temp pointer pointing to the first node of the list and we'll need to traverse the list. For that we will keep two pointers. One pointer will stop at the last node and the other will stop at the second last node of the list.
temp1->link = nullptr; //remove the link between the second last and the last node
delete temp2; //free the memory of the last node
Can I use only 1 temp ptr?
Yes! we can achieve it by using only 1 pointer. We will move the temp pointer to the second last node of the list and we'll free memory of the last node using the temp pointer.
delete temp->link;
Delete a node at the given position in a list
For this we will create 2 temp pointers pointing to the first node of the list. We'll move the first pointer to the node before the node which we want to delete and the second one to the node which we want to delete. Now we will update the link of the 1st pointer and free the memory of the second pointer.
temp1->link = temp2->link;
delete temp2;
Reverse a Linked List
To reverse a Linked List, we need to keep track of 3 pointers. One pointer will point to the current node, the second pointer will point to the previous node, and the third pointer will point to the next node. We will traverse the list and update the links of the nodes.
Node* reverse(Node* head){
Node* current = head;
Node* prev = nullptr;
Node* next = nullptr;
while(current != nullptr){
next = current->link;
current->link = prev;
prev = current;
current = next;
}
head = prev;
return head;
}
In the above code, we created a function reverse that takes the head of the Linked List as an argument and returns the head of the reversed Linked List. We created three pointers, current, prev, and next. We traversed the list and updated the links of the nodes. Finally, we returned the head of the reversed Linked List.
Detect a loop in a Linked List
To detect a loop in a Linked List, we will use the Floyd's Cycle Detection Algorithm. We will keep two pointers, one slow and one fast. The slow pointer will move one step at a time and the fast pointer will move two steps at a time. If there is a loop in the Linked List, the two pointers will meet at some point.
bool detectLoop(Node* head){
Node* slow = head;
Node* fast = head;
while(slow && fast && fast->link){
slow = slow->link;
fast = fast->link->link;
if(slow == fast)
return true;
}
return false;
}
Find the starting point of the loop in a Linked List
To find the starting point of the loop in a Linked List, we will use the Floyd's Cycle Detection Algorithm. We will keep two pointers, one slow and one fast. The slow pointer will move one step at a time and the fast pointer will move two steps at a time. If there is a loop in the Linked List, the two pointers will meet at some point. After that, we will move the slow pointer to the head of the list and move both pointers one step at a time. The point where the two pointers meet is the starting point of the loop.
Node* findLoopStart(Node* head){
Node* slow = head;
Node* fast = head;
while(slow && fast && fast->link){
slow = slow->link;
fast = fast->link->link;
if(slow == fast){
slow = head;
while(slow != fast){
slow = slow->link;
fast = fast->link;
}
return slow;
}
}
return nullptr;
}
Doubly Linked List
Doubly Linked List is a type of Linked List in which each node has two pointers, one pointing to the next node and the other pointing to the previous node.
struct Node{
int data;
Node* next;
Node* prev;
}
Implementation of Doubly Linked List
Creating a Doubly Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
int main() {
Node* head = new Node();
head->data = 1;
head->next = nullptr;
head->prev = nullptr;
Node* second = new Node();
second->data = 2;
second->next = nullptr;
second->prev = head;
head->next = second;
Node* third = new Node();
third->data = 3;
third->next = nullptr;
third->prev = second;
second->next = third;
// Printing the doubly linked list
cout << "Doubly Linked List: ";
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
// Freeing memory
delete head;
// delete second; // Already deleted!
delete third;
return 0;
}
In the above code, we created a doubly linked list with 3 nodes. We created a head node and two other nodes. We updated the next and prev pointers of each node. Finally, we printed the doubly linked list and freed the memory allocated to the nodes.
Output:
Doubly Linked List: 1 2 3
Insertion in a Doubly Linked List
Insert a node at the end of a list
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
void insertAtEnd(Node* head, int data) {
Node* ptr = head;
Node* temp = new Node();
temp->data = data;
temp->next = nullptr;
while (ptr->next != nullptr) {
ptr = ptr->next;
}
ptr->next = temp;
temp->prev = ptr;
}
int main() {
Node* head = new Node();
head->data = 1;
head->next = nullptr;
head->prev = nullptr;
insertAtEnd(head, 2);
insertAtEnd(head, 3);
// Printing the doubly linked list
cout << "Doubly Linked List: ";
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
// Freeing memory
delete head;
return 0;
}
In the above code, we created a doubly linked list with 3 nodes. We created a head node and inserted 2 nodes at the end of the list using the insertAtEnd function. Finally, we printed the doubly linked list and freed the memory allocated to the nodes.
Output:
Doubly Linked List: 1 2 3
Delete a node at the given position in a Doubly Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node* prev;
};
void deleteNode(Node* head, int pos) {
Node* ptr = head;
int count = 1;
while (count < pos) {
ptr = ptr->next;
count++;
}
ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
delete ptr;
}
int main() {
Node* head = new Node();
head->data = 1;
head->next = nullptr;
head->prev = nullptr;
Node* second = new Node();
second->data = 2;
second->next = nullptr;
second->prev = head;
head->next = second;
Node* third = new Node();
third->data = 3;
third->next = nullptr;
third->prev = second;
second->next = third;
deleteNode(head, 2);
// Printing the doubly linked list
cout << "Doubly Linked List: ";
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
// Freeing memory
delete head;
delete second;
delete third;
return 0;
}
In the above code, we created a doubly linked list with 3 nodes. We created a head node and two other nodes. We deleted the 2nd node of the list using the deleteNode function. Finally, we printed the doubly linked list and freed the memory allocated to the nodes.
Output:
Doubly Linked List: 1 3
Circular Linked List
Circular Linked List is a type of Linked List in which the last node of the list is linked to the first node of the list.
struct Node{
int data;
Node* next;
}
Implementation of Circular Linked List
Creating a Circular Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
int main() {
Node* head = new Node();
head->data = 1;
head->next = head;
Node* second = new Node();
second->data = 2;
second->next = head;
head->next = second;
Node* third = new Node();
third->data = 3;
third->next = head;
second->next = third;
// Printing the circular linked list
cout << "Circular Linked List: ";
Node* temp = head;
while (temp->next != head) {
cout << temp->data << " ";
temp = temp->next;
}
cout << temp->data << endl;
// Freeing memory
delete head;
delete second;
delete third;
return 0;
}
In the above code, we created a circular linked list with 3 nodes. We created a head node and two other nodes. We updated the next pointers of each node. Finally, we printed the circular linked list and freed the memory allocated to the nodes.
Output:
Circular Linked List: 1 2 3
Insertion in a Circular Linked List
Insert a node at the beginning of a list
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void insertAtBeginning(Node* head, int data) {
Node* ptr = head;
Node* temp = new Node();
temp->data = data;
temp->next = head;
while (ptr->next != head) {
ptr = ptr->next;
}
ptr->next = temp;
head = temp;
}
int main() {
Node* head = new Node();
head->data = 1;
head->next = head;
insertAtBeginning(head, 0);
// Printing the circular linked list
cout << "Circular Linked List: ";
Node* temp = head;
while (temp->next != head) {
cout << temp->data << " ";
temp = temp->next;
}
cout << temp->data << endl;
// Freeing memory
delete head;
return 0;
}
In the above code, we created a circular linked list with 2 nodes. We created a head node and inserted a node at the beginning of the list using the insertAtBeginning function. Finally, we printed the circular linked list and freed the memory allocated to the nodes.
Output:
Circular Linked List: 0 1
Insert a node at the end of a list
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void insertAtEnd(Node* head, int data) {
Node* ptr = head;
Node* temp = new Node();
temp->data = data;
temp->next = head;
while (ptr->next != head) {
ptr = ptr->next;
}
ptr->next = temp;
}
int main() {
Node* head = new Node();
head->data = 1;
head->next = head;
insertAtEnd(head, 2);
insertAtEnd(head, 3);
// Printing the circular linked list
cout << "Circular Linked List: ";
Node* temp = head;
while (temp->next != head) {
cout << temp->data << " ";
temp = temp->next;
}
cout << temp->data << endl;
// Freeing memory
delete head;
return 0;
}
In the above code, we created a circular linked list with 3 nodes. We created a head node and inserted 2 nodes at the end of the list using the insertAtEnd function. Finally, we printed the circular linked list and freed the memory allocated to the nodes.
Output:
Circular Linked List: 1 2 3
Insert a new node at a given position in a Circular Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void insertAtPosition(Node* head, int data, int pos) {
Node* ptr = head;
Node* temp = new Node();
temp->data = data;
temp->next = nullptr;
int count = 1;
while (count < pos - 1) {
ptr = ptr->next;
count++;
}
temp->next = ptr->next;
ptr->next = temp;
}
int main() {
Node* head = new Node();
head->data = 1;
head->next = head;
insertAtPosition(head, 2, 2);
// Printing the circular linked list
cout << "Circular Linked List: ";
Node* temp = head;
while (temp->next != head) {
cout << temp->data << " ";
temp = temp->next;
}
cout << temp->data << endl;
// Freeing memory
delete head;
return 0;
}
In the above code, we created a circular linked list with 2 nodes. We created a head node and inserted a node at the 2nd position of the list using the insertAtPosition function. Finally, we printed the circular linked list and freed the memory allocated to the nodes.
Output:
Circular Linked List: 1 2
Delete a node at the given position in a Circular Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
void deleteNode(Node* head, int pos) {
Node* ptr = head;
Node* prev = nullptr;
int count = 1;
while (count < pos) {
prev = ptr;
ptr = ptr->next;
count++;
}
prev->next = ptr->next;
delete ptr;
}
int main() {
Node* head = new Node();
head->data = 1;
head->next = head;
Node* second = new Node();
second->data = 2;
second->next = head;
head->next = second;
Node* third = new Node();
third->data = 3;
third->next = head;
second->next = third;
deleteNode(head, 2);
// Printing the circular linked list
cout << "Circular Linked List: ";
Node* temp = head;
while (temp->next != head) {
cout << temp->data << " ";
temp = temp->next;
}
cout << temp->data << endl;
// Freeing memory
delete head;
delete second;
delete third;
return 0;
}
In the above code, we created a circular linked list with 3 nodes. We created a head node and two other nodes. We deleted the 2nd node of the list using the deleteNode function. Finally, we printed the circular linked list and freed the memory allocated to the nodes.
Output:
Circular Linked List: 1 3
Conclusion
In this article, we learned about Linked List, its types, and how to implement Singly, Doubly, and Circular Linked List using C++. We also learned about the operations like Traversing, Insertion, Deletion, Reversing, and Detecting a loop in a Linked List. I hope you found this article helpful.
Authors: