Singly Linked List Explanation and Operations
Introduction: A singly linked list is a linear data structure consisting of nodes where each node contains data and a reference (or pointer) to the next node in the list. The first node is called the head, and the last node points to NULL, indicating the end of the list. Linked lists are dynamic in nature and can grow or shrink as needed.Here's an example implementation of a singly linked list in C++ with step-by-step explanations of all the operations:
#include <iostream>
// Define the structure for a node
struct Node {
int data;
Node* next;
};
// Class for the Singly Linked List
class LinkedList {
private:
Node* head;
public:
// Constructor
LinkedList() {
head = nullptr;
}
// Destructor
~LinkedList() {
// Traverse the list and delete all nodes
Node* current = head;
while (current != nullptr) {
Node* temp = current;
current = current->next;
delete temp;
}
}
// Function to check if the list is empty
bool isEmpty() {
return (head == nullptr);
}
// Function to insert a node at the beginning of the list
void insertAtBeginning(int value) {
// Create a new node
Node* newNode = new Node;
newNode->data = value;
newNode->next = head;
// Update the head pointer
head = newNode;
}
// Function to insert a node at the end of the list
void insertAtEnd(int value) {
// Create a new node
Node* newNode = new Node;
newNode->data = value;
newNode->next = nullptr;
// If the list is empty, make the new node as the head
if (isEmpty()) {
head = newNode;
} else {
// Traverse to the end of the list
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
// Link the new node at the end
current->next = newNode;
}
}
// Function to insert a node at a specific position in the list
void insertAtPosition(int value, int position) {
if (position <= 0) {
insertAtBeginning(value);
} else if (position >= length()) {
insertAtEnd(value);
} else {
// Create a new node
Node* newNode = new Node;
newNode->data = value;
// Traverse to the position before the desired position
Node* current = head;
int count = 1;
while (count < position) {
current = current->next;
count++;
}
// Link the new node at the desired position
newNode->next = current->next;
current->next = newNode;
}
}
// Function to delete a node from the list
void deleteNode(int value) {
// If the list is empty, return
if (isEmpty()) {
return;
}
// If the head node contains the value
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
// Traverse the list to find the node with the value
Node* current = head;
Node* previous = nullptr;
while (current != nullptr && current->data != value) {
previous = current;
current = current->next;
}
// If the value was not found in the list
if (current == nullptr) {
return;
}
// Link the previous node to the next node, bypassing the current node
previous->next = current->next;
// Delete the current node
delete current;
}
// Function to search for a value in the list
bool search(int value) {
// Traverse the list to find the value
Node* current = head;
while (current != nullptr) {
if (current->data == value) {
return true;
}
current = current->next;
}
return false;
}
// Function to get the length of the list
int length() {
int count = 0;
Node* current = head;
while (current != nullptr) {
count++;
current = current->next;
}
return count;
}
// Function to display the list
void display() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
// Insert elements at the beginning of the list
list.insertAtBeginning(10);
list.insertAtBeginning(20);
list.insertAtBeginning(30);
list.insertAtBeginning(40);
// Display the list
std::cout << "List: ";
list.display(); // Output: 40 30 20 10
// Insert elements at the end of the list
list.insertAtEnd(50);
list.insertAtEnd(60);
// Display the list
std::cout << "List: ";
list.display(); // Output: 40 30 20 10 50 60
// Insert element at a specific position in the list
list.insertAtPosition(25, 3);
// Display the list
std::cout << "List: ";
list.display(); // Output: 40 30 25 20 10 50 60
// Delete a node from the list
list.deleteNode(20);
// Display the list
std::cout << "List: ";
list.display(); // Output: 40 30 25 10 50 60
// Search for a value in the list
int value = 25;
bool isFound = list.search(value);
if (isFound) {
std::cout << value << " is found in the list." << std::endl; // Output: 25 is found in the list.
} else {
std::cout << value << " is not found in the list." << std::endl;
}
return 0;
}
- Define a `Node` struct:
- The struct defines a node with an integer `data` and a pointer `next` to the next node.
- Define the `LinkedList` class:
- The class has a private member `head` that points to the head (first node) of the list.
- Implement the constructor and destructor:
- The constructor initializes the `head` pointer to `nullptr`.
- The destructor traverses the list and deletes all the nodes to free memory.
- Implement the `isEmpty` function:
- The function checks if the list is empty by checking if the `head` pointer is `nullptr`.
- Implement the `insertAtBeginning` function:
- The function creates a new node, sets its `data` to the given value, and updates the pointers to insert it at the beginning of the list.
- Implement the `insertAtEnd` function:
- The function creates a new node, sets its `data` to the given value, and traverses the list to find the last node. It links the new node at the end.
- Implement the `insertAtPosition` function:
- The function creates a new node, sets its `data` to the given value, and traverses the list to find the position before the desired position. It links the new node at the desired position.
- Implement the `deleteNode` function:
- The function traverses the list to find the node with the given value. It updates the pointers to bypass the node and deletes it.
- Implement the `search` function:
- The function traverses the list to find the given value. It returns `true` if the value is found, otherwise `false`.
- Implement the `length` function:
- The function traverses the list and counts the number of nodes. It returns the count.
- Implement the `display` function:
- The function traverses the list and prints the data of each node.
- In the `main` function:
- We create a `LinkedList` object called `list`.
- We insert elements at the beginning using `insertAtBeginning`.
- We display the list using `display`.
- We insert elements at the end using `insertAtEnd`.
- We display the list again.
- We insert an element at a specific position using `insertAtPosition`.
- We display the list again.
- We delete a node from the list using `deleteNode`.
- We display the list again.
- We search for a value in the list using `search` and display the result.
List: 40 30 20 10
List: 40 30 20 10 50 60
List: 40 30 25 20 10 50 60
List: 40 30 25 10 50 60
25 is found in the list.