A Linked List is a set of linked elements. It consists of Nodes and links between each node with another node. These nodes contain data and link to the next node. The first node is called the head node. Linked Lists offer dynamic memory allocation and enable efficient insertion and deletion operations, distinguishing them from arrays.
Alright, let's see what are the linked list operations and their time complexities.
- Insertion at Beginning: O(1)
- Insertion at End: O(n)
- Deletion by Value: O(n)
- Search (Finding a Node): O(n)
- Traversal (Display): O(n)
- Deletion at Beginning: O(1)
- Deletion at End (without tail pointer): O(n)
- Deletion at End (with tail pointer): O(n)
- Insertion/Deletion at Specific Position: O(n)
- Reversing the List: O(n)
Now let's see the implementation of LinkedList in C++.
*Reading comment lines is essential to understand the code and try these codes yourself. If you are using a mobile phone to read this, make sure to rotate your screen while reading this code.
#include <iostream>
using namespace std;
// Define a Node structure
struct Node {
int data; // Data value of the Node
Node* next; // Next Reference
Node(int val) : data(val), next(nullptr) {} // Constructor
};
// Define a LinkedList class
class LinkedList {
private:
Node* head; // Pointer to the first node in the list
public:
// Constructor
LinkedList() : head(nullptr) {} // Initially set the head value to null pointer
// Destructor to free memory
~LinkedList() {
Node* current = head; // Start from the head
while (current != nullptr) { // Loop until the end of the list
Node* next = current->next; // Save the reference to the next node
delete current; // Delete the current node
current = next; // Move to the next node
}
}
// Function to insert a node at the beginning
void insertAtBeginning(int val) {
Node* newNode = new Node(val); // Create a new node
newNode->next = head; // Set the next of the new node to the current head
head = newNode; // Update the head to point to the new node
}
// Function to insert a node at the end
void insertAtEnd(int val) {
Node* newNode = new Node(val); // Create a new node
if (head == nullptr) { // If the list is empty
head = newNode; // Make the new node the head
return;
}
Node* current = head; // Start from the head
while (current->next != nullptr) { // Traverse to the end of the list
current = current->next;
}
current->next = newNode; // Insert the new node at the end
}
// Function to delete a node by value
void deleteNode(int val) {
if (head == nullptr) // If the list is empty
return;
if (head->data == val) { // If the node to be deleted is the head
Node* temp = head; // Store the head in a temporary variable
head = head->next; // Move the head to the next node
delete temp; // Delete the old head
return;
}
Node* current = head; // Start from the head
while (current->next != nullptr && current->next->data != val) {
// Traverse until the node before the one to be deletedcurrent = current->next;
}
if (current->next == nullptr) // If the node to be deleted is not found
return;
Node* temp = current->next; // Store the node to be deleted in a temporary variable
current->next = current->next->next; // Remove the node from the list
delete temp; // Delete the node
}
// Function to search for a node
bool search(int val) {
Node* current = head; // Start from the head
while (current != nullptr) { // Traverse the list
if (current->data == val) // If the value is found
return true;
current = current->next; // Move to the next node
}
return false; // If the value is not found
}
// Function to display the linked list
void display() {
Node* current = head; // Start from the head
while (current != nullptr) { // Traverse the list
cout << current->data << " "; // Print the value of the current node
current = current->next; // Move to the next node
}
cout << endl; // Print a new line after printing all the values
}
// Function to reverse the linked list
void reverse() {
Node* prev = nullptr; // Pointer to the previous node
Node* current = head; // Pointer to the current node
Node* next = nullptr; // Pointer to the next node
while (current != nullptr) { // Traverse the list
next = current->next; // Store the next node
current->next = prev; // Reverse the link
prev = current; // Move prev to current
current = next; // Move current to next
}
head = prev; // Make the last node as head
}
};
int main() {
LinkedList myList;
myList.insertAtEnd(1);
myList.insertAtEnd(2);
myList.insertAtEnd(3);
myList.insertAtBeginning(0);
cout << "Linked List: ";
myList.display(); // Output: 0 1 2 3
myList.deleteNode(2);
cout << "After deleting 2: ";
myList.display(); // Output: 0 1 3
bool isFivePresent = myList.search(5);
if (isFivePresent)
cout << "Yes";
else
cout << "No";
cout << endl;
bool isThreePresent = myList.search(3);
if (isThreePresent)
cout << "Yes";
else
cout << "No";
cout << endl;
myList.reverse();
cout << "Reversed Linked List: ";
myList.display(); // Output: 3 1 0
return 0;
}
Singly Linked Lists elegantly traverse from one node to the next, gracefully skipping the notion of a previous connection. Each node stands independently, intricately linked only to its successor. Think, if this singly linked list can access the previous node, then some of the linked list operations can do more efficiently than the previous one. For these reasons, the doubly linked list comes to the front.
Doubly Linked List
You can get an idea of how this works from this picture.
.png)
| Operation | Singly Linked List Time Complexity | Doubly Linked List Time Complexity |
|---|---|---|
| Insertion at Beginning | O(1) | O(1) |
| Insertion at End | O(n) | O(1) |
| Deletion by Value | O(n) | O(n) |
| Search (Finding a Node) | O(n) | O(n) |
| Traversal (Display) | O(n) | O(n) |
| Deletion at Beginning | O(1) | O(1) |
| Deletion at End (without tail pointer) | O(n) | O(1) |
| Deletion at End (with tail pointer) | O(n) | O(1) |
| Insertion/Deletion at Specific Position | O(n) | O(n) |
| Reversing the List | O(n) | O(n) |
However, we should select a suitable linked list (singly or doubly) considering our problem.
Conclusion
In this post, we discussed Linked lists and their types. If you think this is valuable, please share this with your friends. Thank you for reading this and have a nice day!
