Singly Linked List in Data Structure
Last Updated on: 2nd Jan 2026 20:28:59 PM
A Singly Linked List is a fundamental linear data structure used to store data dynamically. Unlike arrays, it does not require continuous memory allocation and allows efficient insertion and deletion of elements.
This tutorial explains the structure, creation, operations, advantages, limitations, applications, and includes complete C++ coding examples with time complexity analysis.
What is a Singly Linked List?
A Singly Linked List is a collection of nodes where each node contains two parts:
-
Data – stores the actual value.
-
Next – stores the address of 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.
Definition
A Singly Linked List is a linear data structure in which each element points to the next element in the sequence.
Real-Life Example
Consider a train where each coach is connected only to the next coach. You can move forward from one coach to another, but you cannot move backward directly. This is similar to a singly linked list.
Structure of Singly Linked List
Each node is created using a structure that stores data and a pointer to the next node. The pointer creates a link between nodes.In C++, we use a struct or class to create a node.
Each node in a Singly Linked List has the following structure:
-
Data: Holds the value of the node.
-
Next: Holds the address of the next node.
-
The Head stores the address of the first node.
-
The Next of the last node stores NULL.
Creation of Singly Linked List
A Singly Linked List is created dynamically using memory allocation.
Steps to Create a Singly Linked List:
-
Create a node.
-
Store data in the node.
-
Store NULL or the address of the next node.
-
Assign the first node’s address to Head.
-
Repeat the process to add more nodes.
Real-Life Example
Creating a Singly Linked List is like forming a queue of people, where each person knows who is standing next but not who is behind them.
C++ Implementation of Singly Linked List
Node Definitation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Operations on Singly Linked List
1. Insertion in Singly Linked List
Insertion is the process of adding a new node to the linked list. In a singly linked list, insertion can be performed at different positions depending on requirements
Types of Insertion:
-
Insertion at the beginning
-
Insertion at the end
-
Insertion at a specific position
A. Insertion at the Beginning
The new node is added before the existing first node. The new node’s next pointer points to the current head, and then the head is updated.
Logic
-
Create a new node
-
New node’s next points to Head
-
Head points to new node
Real-Life Example
Adding a new book at the front of a stack without disturbing the rest.
Coding Example
void insertAtBeginning(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = head;
head = newNode;
}
Time Complexity : O(1)
Because the operation takes constant time regardless of list size.
B. Insertion at the End
The new node is added after the last node. The last node’s next pointer is updated to point to the new node.
Logic
-
Traverse to last node
-
Last node’s next points to new node
Real-Life Example
Adding a new passenger at the end of a queue.
Coding Example
void insertAtEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
Time Complexity: O(n)
Because every node must be visited once in the worst case.
2. Deletion in Singly Linked List
Deletion removes a node from the linked list and frees its memory. Care must be taken to adjust pointers properly.
Types of Deletion
-
Deletion from the Beginning
-
Deletion from the End
-
Deletion of a Specific Node
A. Deletion from the Beginning
The head node is removed, and the head pointer is updated to the next node.
Logic
-
Store head node
-
Move head to next node
-
Delete old head
Real-Life Example
Removing the first task from a to-do list after completion.
Coding Example
void deleteFromBeginning() {
if (head == NULL)
return;
Node* temp = head;
head = head->next;
delete temp;
}
Time Complexity: O(1)
Because no traversal is required.
B. Deletion from the End
The list is traversed to find the second-last node. The last node is removed, and the second-last node’s next pointer is set to NULL.
Logic
-
Traverse to second-last node
-
Set its next to NULL
-
Delete last node
Real-Life Example
Removing the last person from a line.
Coding Example
void deleteFromEnd() {
if (head == NULL)
return;
if (head->next == NULL) {
delete head;
head = NULL;
return;
}
Node* temp = head;
Node* prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
delete temp;
}
Time Complexity: O(n)
Traversal is required to reach the second-last node.
3. Traversal of Singly Linked List
Traversal is the process of visiting each node of the linked list one by one to access or display its data.
Real-Life Example
Reading each page of a book from the first page to the last page.
Coding Example
void traverse() {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL";
}
Time Complexity: O(n)
Because all nodes are accessed sequentially.
4. Searching in Singly Linked List
Searching is the process of finding whether a particular element exists in the linked list.
Concept Explanation
The list is traversed from the head node, and each node’s data is compared with the search value.
Real-Life Example
Searching for a contact name in a phone list sequentially.
Coding Example
void search(int key) {
Node* temp = head;
int position = 1;
while (temp != NULL) {
if (temp->data == key) {
cout << "Element found at position " << position;
return;
}
temp = temp->next;
position++;
}
cout << "Element not found";
}
Time Complexity
-
Best Case: O(1) (element found at first node)
-
Worst Case: O(n) (element at last node or not present)
-
Average Case: O(n)
Complete Menu-Driven Program in C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head = NULL;
/* Insert at Beginning */
void insertAtBeginning(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = head;
head = newNode;
}
/* Insert at End */
void insertAtEnd(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
/* Delete from Beginning */
void deleteFromBeginning() {
if (head == NULL) {
cout << "List is empty\n";
return;
}
Node* temp = head;
head = head->next;
delete temp;
cout << "Node deleted from beginning\n";
}
/* Delete from End */
void deleteFromEnd() {
if (head == NULL) {
cout << "List is empty\n";
return;
}
if (head->next == NULL) {
delete head;
head = NULL;
cout << "Last node deleted\n";
return;
}
Node* temp = head;
Node* prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
delete temp;
cout << "Node deleted from end\n";
}
/* Traversal */
void traverse() {
if (head == NULL) {
cout << "List is empty\n";
return;
}
Node* temp = head;
cout << "Linked List: ";
while (temp != NULL) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL\n";
}
/* Searching */
void search(int key) {
Node* temp = head;
int position = 1;
while (temp != NULL) {
if (temp->data == key) {
cout << "Element " << key << " found at position " << position << endl;
return;
}
temp = temp->next;
position++;
}
cout << "Element " << key << " not found in the list\n";
}
/* Main Function */
int main() {
int choice, value;
while (true) {
cout << "\n--- Singly Linked List Menu ---\n";
cout << "1. Insert at Beginning\n";
cout << "2. Insert at End\n";
cout << "3. Delete from Beginning\n";
cout << "4. Delete from End\n";
cout << "5. Traverse\n";
cout << "6. Search\n";
cout << "7. Exit\n";
cout << "Enter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter value: ";
cin >> value;
insertAtBeginning(value);
break;
case 2:
cout << "Enter value: ";
cin >> value;
insertAtEnd(value);
break;
case 3:
deleteFromBeginning();
break;
case 4:
deleteFromEnd();
break;
case 5:
traverse();
break;
case 6:
cout << "Enter value to search: ";
cin >> value;
search(value);
break;
case 7:
cout << "Exiting program\n";
return 0;
default:
cout << "Invalid choice\n";
}
}
}
Sample Output
--- Singly Linked List Menu ---
1. Insert at Beginning
2. Insert at End
3. Delete from Beginning
4. Delete from End
5. Traverse
6. Search
7. Exit
Enter your choice: 1
Enter value: 10
--- Singly Linked List Menu ---
Enter your choice: 2
Enter value: 20
--- Singly Linked List Menu ---
Enter your choice: 2
Enter value: 30
--- Singly Linked List Menu ---
Enter your choice: 5
Linked List: 10 -> 20 -> 30 -> NULL
--- Singly Linked List Menu ---
Enter your choice: 6
Enter value to search: 20
Element 20 found at position 2
--- Singly Linked List Menu ---
Enter your choice: 4
Node deleted from end
--- Singly Linked List Menu ---
Enter your choice: 5
Linked List: 10 -> 20 -> NULL
--- Singly Linked List Menu ---
Enter your choice: 3
Node deleted from beginning
--- Singly Linked List Menu ---
Enter your choice: 5
Linked List: 20 -> NULL
--- Singly Linked List Menu ---
Enter your choice: 7
Exiting program
Time Complexity Analysis
| Operation | Time Complexity | Reason |
|---|---|---|
| Insert at Beginning | O(1) | No traversal required |
| Insert at End | O(n) | Traverses entire list |
| Delete from Beginning | O(1) | Direct head update |
| Delete from End | O(n) | Traversal needed |
| Traversal | O(n) | Visits each node once |
| Searching | O(n) | Sequential search |
Conclusion
Singly Linked List is a powerful dynamic data structure that efficiently handles insertion and deletion operations. By understanding its structure and operations such as insertion, deletion, traversal, and searching, students can easily move toward advanced data structures like stacks, queues, and graphs.
Keep practicing — you're doing amazing!
Happy Coding! 