A linked list is a fundamental data structure consisting of nodes where each node contains a piece of data and a reference to the next node. C++ allows manual memory management through pointers, making it a great language to understand how linked lists work under the hood. In this post, we'll explore how to implement a singly linked list from scratch in C++.
By the end of this tutorial, you'll learn:
- How to define a node and a linked list class in C++
- How to insert elements at the beginning and the end
- How to traverse, display, and delete nodes from the list
1. Understanding the Linked List Structure
A singly linked list consists of nodes where each node has two members:
- data: Stores the value of the node.
- next: A pointer to the next node in the sequence, or
nullptrif it's the last node.
Example of a Node Struct:
struct Node {
int data;
Node* next; // Pointer to the next node
Node(int value) : data(value), next(nullptr) {} // Constructor to initialize data
};
Here, the Node struct:
- Uses an integer
datato store the value. - Has a
nextpointer that either points to another node or isnullptr, indicating the end of the list.
2. Creating a Linked List Class
We will now define a LinkedList class to manage the nodes. This class will have a pointer to the head of the list, which keeps track of the first node.
Example:
class LinkedList {
private:
Node* head; // Pointer to the head (first node) of the list
public:
LinkedList() : head(nullptr) {} // Constructor initializes an empty list
bool isEmpty() const {
return head == nullptr; // Check if the list is empty
}
};
Here, the LinkedList class:
- Initializes the list with an empty head (
nullptr). - Has a method
isEmpty()to check if the list is empty.
3. Inserting Nodes into the Linked List
There are two common ways to insert nodes into a singly linked list:
- At the beginning: The new node becomes the head.
- At the end: The new node is added after the last node.
a) Inserting at the Beginning
To insert at the beginning, we create a new node and update its next pointer to point to the current head, then update the head to point to this new node.
void insertAtBeginning(int value) {
Node* newNode = new Node(value);
newNode->next = head; // New node points to the current head
head = newNode; // Update the head to the new node
}
b) Inserting at the End
To insert a node at the end, we traverse the list to find the last node (where next is nullptr) and then link the new node to the last node.
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (isEmpty()) { // If the list is empty, set the new node as the head
head = newNode;
return;
}
Node* current = head;
while (current->next != nullptr) { // Traverse the list to find the last node
current = current->next;
}
current->next = newNode; // Link the last node to the new node
}
4. Displaying the Linked List
To display the elements of the linked list, we need to traverse from the head to the last node, printing each node's data.
Example:
void display() const {
if (isEmpty()) {
std::cout << "List is empty\n";
return;
}
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "nullptr\n"; // Indicate the end of the list
}
In this method:
- We start from the head and traverse the list using the
nextpointers, printing the data of each node. - Once
currentbecomesnullptr, the traversal is complete, and we printnullptrto indicate the end.
5. Deleting a Node
We will discuss two common deletion operations:
- Deleting the first node (head).
- Deleting a node by value.
a) Deleting the First Node (Head)
To delete the first node, we update the head to point to the second node and free the memory allocated to the original head.
void deleteFirstNode() {
if (isEmpty()) {
std::cout << "List is empty\n";
return;
}
Node* temp = head;
head = head->next; // Move the head to the second node
delete temp; // Free the old head
}
b) Deleting a Node by Value
To delete a node by value, we search for the node with the specified value and adjust the previous node's next pointer to skip over the node being deleted.
void deleteNode(int value) {
if (isEmpty()) {
std::cout << "List is empty\n";
return;
}
// If the node to be deleted is the head
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
Node* previous = nullptr;
while (current != nullptr && current->data != value) {
previous = current;
current = current->next;
}
if (current == nullptr) {
std::cout << "Value not found in the list\n";
return;
}
previous->next = current->next; // Unlink the node
delete current;
}
6. Complete Example
Here’s the full implementation of a basic linked list in C++, including insertion, display, and deletion of nodes.
#include <iostream>
struct Node {
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
bool isEmpty() const {
return head == nullptr;
}
void insertAtBeginning(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (isEmpty()) {
head = newNode;
return;
}
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
void display() const {
if (isEmpty()) {
std::cout << "List is empty\n";
return;
}
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "nullptr\n";
}
void deleteFirstNode() {
if (isEmpty()) {
std::cout << "List is empty\n";
return;
}
Node* temp = head;
head = head->next;
delete temp;
}
void deleteNode(int value) {
if (isEmpty()) {
std::cout << "List is empty\n";
return;
}
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
Node* previous = nullptr;
while (current != nullptr && current->data != value) {
previous = current;
current = current->next;
}
if (current == nullptr) {
std::cout << "Value not found in the list\n";
return;
}
previous->next = current->next;
delete current;
}
};
int main() {
LinkedList list;
list.insertAtEnd(10);
list.insertAtEnd(20);
list.insertAtEnd(30);
std::cout << "Initial List:\n";
list.display();
list.deleteFirstNode();
std::cout << "After deleting first node:\n";
list.display();
list.deleteNode(20);
std::cout << "After deleting node with value 20:\n";
list.display();
return 0;
}
Conclusion
In this tutorial, you've learned how to manually implement a basic singly linked list in C++, including how to insert, display, and delete nodes. While C++ offers high-level containers like std::list, understanding the internal workings of a linked list helps you build a strong foundation in data structures and memory management.