Data Structures & Algorithms Table of content:

Single Linked List In Data Structure | All Operations (+Examples)

Picture this: you’re organizing a line of tasks to complete one after another. You can only see the current task and the next one ahead, and each task knows only the one that follows. This concept is the essence of a singly linked list, a fundamental data structure in programming.

In this article, we’ll explore singly linked lists, including what they are, how they work, and why they’re essential for storing and managing data. Whether you’re coding a to-do list, building a navigation system, or designing a queue for processing, singly linked lists are here to make your life easier.

What Is A Singly Linked List In Data Structure?

A singly linked list is a linear data structure where each element, called a node, points to the next node in the sequence. Unlike arrays, linked lists don’t require a contiguous block of memory. Instead, each node contains two parts:

Data: Stores the actual information.
Pointer (or link): Holds the address of the next node in the list.

The first node in the list is called the head, and the last node’s pointer is set to NULL, indicating the end of the list.

Key Features Of Singly Linked Lists

Dynamic Size: They grow or shrink as needed, making them memory-efficient compared to arrays.
Sequential Access: Nodes can only be accessed sequentially, starting from the head.
Efficient Insertion/Deletion: Adding or removing elements doesn’t require shifting data, unlike arrays.

Think of a singly linked list as a treasure hunt. Each clue (node) points to the location of the next clue until you reach the final treasure (end of the list). Now that you know the basics of single-linked lists in data structures, let’s take a look at the internal structure of these lists and how they work.

Structure Of A Singly Linked List

To truly understand how a singly linked list operates, let’s break down its structure and components step-by-step:

Node: The basic building block of a singly linked list is a node, which consists of two main parts:

Data: Holds the actual information (e.g., a number, string, or object).
Next: A pointer or reference to the next node in the sequence. For the last node, this is set to NULL.

Head: The head is a special pointer that points to the first node in the list. Without the head, the list would be inaccessible.
Tail: The tail is the last node in the list, where the Next pointer is NULL, signaling the end of the list.
Traversal: Starting from the head, the list is traversed node by node using the Next pointer. This sequential nature means you can only access elements in order.

Diagram Of Singly Linked List

Here:

The Head points to the first node.
Each node points to the next one.
The final node points to NULL.

Example Of Singly Linked List Program In Data Structure (Basic Node Structure)

Let’s look at an example of how the single linked list creation works in C++ programming language.

Click here to view code

Output:

Data in Node 1: 10
Data in Node 2: 20

Code Explanation:

We create a class called Node containing two data members: data (an integer data type variable to store the value of the node.) and next (a pointer variable of type Node* to store the address of the next node in the list).

Both members are defined using the public access specifier, meaning they can be accessed directly throughout the program.
We then define a class constructor (also public) to initialize the data member with the given value and set next to nullptr.

In the main() function, we create two nodes, node1 and node2. Each node is an instance of the Node class, initialized with a data value and a next pointer set to nullptr by default.
Next, we update the next pointer of node1 to point to node2, creating a link between the two nodes.
We can then traverse the list starting from node1 and access the data values stored in each node.

Next, we’ll explore insertion operations in single linked lists in data structures to see how nodes are added at different positions.

Insertion Operations On Singly Linked Lists

Insertion is one of the most fundamental operations performed on a single linked list. Depending on where the new node is added, there are three types of insertion operations: at the beginning, at the end, or at a specific position. We’ll explore all these with examples.

Insertion At Beginning Of Singly Linked List

Inserting a node at the beginning of a singly linked list involves adding a new node such that it becomes the first node (head) of the list. The next pointer of this new node is updated to point to the previous head node. Here is how this works:

Create a new node and assign the data.
Update the next pointer of the new node to point to the current head node.
Update the head pointer to point to the new node.

Code Example:

Click here to view code

Output:

10 -> 20 -> 30 -> NULL

Code Explanation:

Just like in the previous example, we begin by importing the iostream header file for input/output operations. We then define a Node class with two data members and a constructor.

Helper Functions: We define two functions: insertAtBeginning(, which adds a new node at the start of the list, and printList() to traverse the list and print the content.
Here, the printList() function uses a while loop to check if the pointer is not null, in which case it prints the content.
Dynamic Node Creation: Inside insertAtBeginning(), a new node is dynamically created using the Node constructor and initialized with newData.
Pointer Update: Then, the next pointer of the newly created node is assigned the current head node, effectively linking it to the existing list.
Head Update: After that, the head pointer is updated to point to the new node, making it the first node in the list.
As a result, the new node becomes the head of the list, and the previous nodes are shifted down in sequence.

Insertion At End Of Singly Linked List

Inserting a node at the end of a singly linked list involves adding a new node as the last element. The next pointer of the current last node is updated to point to the new node, and the new node's next pointer is set to nullptr. Here is how this works:

Create a new node and assign the data.
If the list is empty (head is nullptr), set the head pointer to the new node.
Otherwise, traverse the list to find the last node (whose next is nullptr).
Update the next pointer of the last node to point to the new node.
Set the next pointer of the new node to nullptr.

Code Example:

Click here to view code

Output:

10 -> 20 -> 30 -> NULL

Code Explanation:

Similar to the previous example, we have a Node class with two data members, a constructor and a printList() function to traverse and print the list contents.

Function to Add Node: We also define an insertAtEnd() function to insert a new node at the end of the list.
Node Creation: Inside insertAtEnd(), a new node is dynamically created using the Node constructor and initialized with newData.
Empty List Check: Then, we use an if-statement to check if the list is empty (i.e.,the head is nullptr). If it is true (the list is empty), the head pointer is set to the new node.
Traverse to Last Node: If the list is not empty, a temporary pointer (temp) traverses the list until it reaches the last node (where temp->next == nullptr).
Linking New Node: We then update the next pointer of the last node to point to the new node, linking it to the end of the list.
Pointer Update: The next pointer of the new node is set to nullptr, indicating that it is the last node.

Insertion At A Specific Position In Singly Linked List

Inserting a node at a specific position in a singly linked list involves placing the new node at a user-defined position. The list can be traversed until the desired position is reached, and then the new node is inserted between two existing nodes. This operation requires updating the next pointer of the node just before the insertion point. Here is how it works:

Create a new node and assign the data.
If the position is 0, insert the node at the beginning (this is handled in a similar way to the insertion at the beginning operation).
Otherwise, traverse the list to find the node just before the desired position.
Update the next pointer of the node at the previous position to point to the new node.
Set the next pointer of the new node to point to the next node in the list.

Code Example:

Click here to view code

Output:

10 -> 15 -> 20 -> NULL

Code Explanation:

We begin with defining the Node class and then two functions: printList() to traverse and display the list, and insertAtPosition() to add a node at a specific position.

Insertion at Position 0: Inside the insertAtPosition() function, we first check if the specified position is 0. If it is, we treat that as insertion at the beginning of the list.
Insertion at Other Positions: If the specified position is greater than 0, we traverse the list to find the node just before the specified position.

We start from the head and use a while loop to move through the list until we reach the node at the position position - 1.
This is done by incrementing the currentPos and updating temp to point to the next node in each iteration.

Inserting the New Node: Once we find the node just before the desired position, we:

Set newNode->next to temp->next, which points to the node that will come after the new node.
Update temp->next to point to the new node, effectively inserting it into the list at the specified position.

Out of Bounds Check: If we reach the end of the list (i.e., temp is nullptr before reaching the desired position), it indicates that the position is out of bounds. In this case, a message is printed: "Position is out of bounds!".
In the main() function, we create a new node using the constructor of the Node class, which initializes the new node with the data newData. The next pointer of this new node is set to nullptr by default.
Initial List: We start with a linked list containing two nodes: 10 -> 20 -> NULL.
Insert at Position 1: The insertAtPosition() function inserts the new node with value 15 between 10 and 20. It achieves this by traversing the list until it reaches the node just before position 1, and then adjusting the next pointers accordingly.

This example shows how to start with an existing linked list and insert a new node at a specific position. It gives a clearer picture of how insertion works in a more realistic scenario.

Boost your learning curve with one-on-one mentorship from industry professionals.

Deletion Operation On Singly Linked List

In a singly linked list, deletion operations involve removing a node from a specific location—either the beginning, end or a specified position within the list. Deleting a node requires careful handling of pointers to ensure the integrity of the list.

Deletion From Beginning Of Singly Linked List

To delete the first node (head node), we update the head pointer to point to the second node in the list, effectively removing the first node from the list.

Code Example:

Click here to view code

Output:

Initial list: 10 -> 20 -> 30 -> NULL
List after deletion: 20 -> 30 -> NULL

Code Explanation:

Delete from the Beginning:

We check if the list is empty (i.e., head == nullptr). If so, we print an error message and exit the function.
If the list is not empty, we store the current head node in the temp pointer.
We update the head pointer to point to the next node in the list (head = head->next), effectively removing the first node.
Finally, we delete the original head node using delete temp.

This operation is O(1) in terms of time complexity, as it only involves updating the head pointer and deleting the first node.

Deletion From End Of Singly Linked List

Deleting the last node requires traversing the list to find the second-last node, updating its next pointer to nullptr, and then deleting the last node.

Code Example:

Click here to view code

Output:

Initial list: 10 -> 20 -> 30 -> NULL
List after deletion: 10 -> 20 -> NULL

Code Explanation:

We define the Node class and the printList() function just like before. Then, we define the deleteFromEnd() function:

Delete from the End Function: The deleteFromEnd() function first checks if the list is empty or contains only one node.
If the list contains only one node, it deletes the head node and sets the head to nullptr.
If the list contains more than one node:

We traverse the list to find the second-last node (temp->next->next == nullptr).
Once the second-last node is found, we update its next pointer to nullptr, effectively removing the last node.
Finally, we delete the last node.

In the main() function, we create a list with three linked nodes and print it to the console.
Then, we call the deleteFromEnd() function, passing the head as an argument. The function deletes the last node, and we print the new list to the console for comparison.

Deletion From Specific Position Of Singly Linked List

To delete a node from a specific position, we traverse the list to find the node just before the target node, update its next pointer to skip the target node, and then delete the target node.

Code Example:

Click here to view code

Output:

Initial list: 10 -> 20 -> 30 -> 40 -> NULL
List after deletion: 10 -> 20 -> 40 -> NULL

Code Explanation:

We have a Node class to create nodes, and a printList() function to traverse an print the contents of a linked list.

Delete from a Specific Position: We also define a function to delete the node from a specific position.
The deleteAtPosition() function first checks if the list is empty. If the position is 0, it deletes the head node in the same way as the deletion at the beginning.
If the position is greater than 0:

We traverse the list to find the node just before the specified position.
Once the node before the target is found, we update its next pointer to skip the node at the target position.
We then delete the node at the target position.

If the position is invalid (greater than the number of nodes), an out-of-bounds message is printed.
In the main() function, we create a linked list with four nodes and then print the same.
Next, we call the deleteAtPosition() function with arguments head and 2, i.e., to delete the node at position 2.
The function deletes the respective node and shifts the previous one ahead. We display the new list for comparison.

Want to become an expert? Dive into this curated course on DSA and advance your career.

Searching For Elements In Single Linked List

Searching in a singly linked list involves looking for a specific node that contains a given value. The search operation typically starts from the head node and traverses the list node by node until it finds the target value or reaches the end of the list.

How It Works:

Start from the Head: We begin at the head node and check if it contains the desired value.
Traverse the List: If the current node does not contain the desired value, we move to the next node and repeat the process until we either find the value or reach the end of the list (when the next pointer is nullptr).
Return Result: If the value is found, we return the node or a true indication. If the end of the list is reached and the value isn't found, we return false or an appropriate message.

Code Example:

Click here to view code

Output:

List: 10 -> 20 -> 30 -> NULL
20 found in the list!

Code Explanation:

Just like before, we define a class Node for node creation and a printList() function to traverse and print the linked list.

Search Function: We also define a search() function that takes the head of the list and the target value as arguments. It iterates over each node in the list.

If the value of the current node (temp->data) matches the target, the function returns true, indicating the element is found.
If the loop reaches the end of the list (temp == nullptr) without finding the target, it returns false.

In the main() function, we create a linked list with values 10, 20, and 30, and then search for the element 20.
The program will output that the value is found.

This search operation has a time complexity of O(n), where n is the number of nodes in the list.

Calculating Length Of Single Linked List

The length of a singly linked list refers to the number of nodes it contains. To calculate the length, we need to traverse the entire list and count how many nodes exist before we reach the end (when the next pointer is nullptr).

How It Works:

Initialize Counter: We start by initializing a counter to 0.
Traverse the List: We traverse the list starting from the head node. For each node we visit, we increment the counter.
Return the Counter: Once the traversal is complete (i.e., we reach the end of the list), the counter will hold the total number of nodes in the list, which is the length.

Code Example:

Click here to view code

Output:

List: 10 -> 20 -> 30 -> NULL
Length of the list: 3

Code Explanation:

We have the Node class for node creation and printList() to display the linked list.

Calculate Length Function: Then, we define the calculateLength() function, which initializes a length variable to 0 and starts at the head node.

It traverses the list node by node, incrementing the length for each node it encounters.
Once the end of the list is reached (i.e., temp == nullptr), it returns the length of the list.

In the main() function, we create a linked list with three nodes, and then calculate the length using the calculateLength() function.
The result is 3, since there are three nodes in the list.

This operation has a time complexity of O(n), where n is the number of nodes in the list.

Practical Applications Of Singly Linked Lists In Data Structure

Singly Linked Lists (SLLs) are one of the most fundamental data structures in computer science and have numerous practical applications. They are particularly useful in situations where dynamic memory allocation is required, and fast insertion and deletion of elements are needed.

Implementing Stacks and Queues: These data structures can be implemented efficiently using singly linked lists. The dynamic nature of SLLs allows easy push and pop operations (for stacks) or enqueue and dequeue operations (for queues) without worrying about resizing, as you would with arrays.
Memory Management: In memory management, linked lists are used to represent free blocks of memory. When a block of memory is freed, it is added to a free list (a linked list), and when memory is allocated, it is taken from the free list.
Dynamic Data Allocation: In applications where the size of the data cannot be determined in advance or changes frequently, single linked lists (SLLs) provide an efficient way to handle this. They allow for adding or removing data dynamically without the need to allocate or resize a contiguous block of memory.
Polynomials: They are often represented using linked lists, where each node contains a coefficient and an exponent. This allows for efficient addition, subtraction, and multiplication of polynomials, especially when the number of terms varies.
Graph Representation: Singly linked lists are often used to represent adjacency lists in graph data structures. Each vertex in the graph has a linked list of adjacent vertices, making it easy to store and traverse a sparse graph.
Implementing Hash Tables: In hash table implementation using chaining, each bucket can be implemented using a linked list. This helps in handling collisions efficiently when multiple keys hash to the same bucket.
Sparse Matrices: Singly linked lists are useful for storing sparse matrices, where most of the elements are zero. Rather than allocating memory for every element, linked lists allow efficient storage of only non-zero elements.
Undo Mechanism: In software applications like text editors or drawing tools, linked lists can be used to store a history of operations. By using a linked list to represent actions, the system can easily undo or redo previous operations.

Common Problems With Singly Linked Lists

While singly linked lists are a powerful data structure, they come with certain challenges and potential pitfalls. Understanding these common issues helps in building robust solutions and avoiding common mistakes.

Memory Leaks: Failing to properly deallocate memory when nodes are removed can lead to memory leaks.
Solution: Always ensure that you free memory when nodes are deleted or no longer needed. In C++, this can be done using delete for each node that is removed.
Traversal Time Complexity: Accessing elements in a singly linked list requires traversal from the head to the desired position, leading to O(n) time complexity for searches, insertions, and deletions.
Solution: For more efficient access, consider using other data structures like arrays or doubly linked lists, where backward traversal is also possible.
Difficulty with Backtracking: Singly linked lists only allow traversal in one direction. Once you move past a node, you cannot go back to it without restarting from the head.
Solution: If you need frequent backward traversal, a doubly linked list may be more appropriate, as it allows traversal in both directions.
Insertion at Specific Positions: Inserting an element at a specific position in a singly linked list requires traversal to that position, which can be inefficient if the position is near the end of the list.
Solution: If insertion at specific positions is a frequent operation, consider using other data structures like a doubly linked list or an array-based structure for faster access.
Difficulty in Reversing the List: Reversing a singly linked list involves changing the direction of the pointers for each node, which requires an additional traversal and careful handling of pointers to avoid breaking the list.
Solution: Use a well-defined algorithm for reversing the list. For instance, iteratively reverse the list by updating the pointers from the head to the end.
Limited Use of Indexing: Unlike arrays, linked lists don’t support indexing, meaning direct access to a node by position is not possible.
Solution: If you need frequent random access to elements, an array or vector might be more efficient.
Complicated Deletion: Deleting nodes in a singly linked list, especially when dealing with deletion at the middle or end of the list, can be tricky as it requires keeping track of the previous node in order to update the next pointer.
Solution: Properly manage pointers during deletion to ensure the list remains intact. When deleting from the middle or end, handle the previous node’s next pointer carefully.

Stay ahead of the curve—practice with hands-on coding problems designed to level up your abilities.

Conclusion

In this article, we have explored the fundamentals of singly linked lists, including their structure, insertion and deletion operations, and common applications. We’ve also covered some practical aspects, such as best practices for managing linked lists efficiently and tackling challenges.

By understanding the core concepts and operations on single linked lists, you'll be better equipped to use them effectively in real-world applications, whether it's for managing dynamic data or solving complex problems. Remember to follow best practices, handle memory efficiently, and use iterative approaches when working with linked lists to avoid common pitfalls.

Frequently Asked Questions

Q1. What is the difference between a singly linked list and a doubly linked list?

In a singly linked list, each node has a pointer to the next node, and traversal can only be done in one direction (forward). In contrast, a doubly linked list has two pointers in each node—one pointing to the next node and another pointing to the previous node, allowing traversal in both directions.

Q2. Can we have a singly linked list with no nodes?

Yes, a singly linked list can be empty. This occurs when the head pointer is set to nullptr, meaning there are no nodes in the list.

Q3. How do we traverse a singly linked list?

To traverse a singly linked list, start from the head node and continue to the next node until you reach a node whose next pointer is nullptr. At each step, you can process or access the data in the current node.

Node* current = head;
while (current != nullptr) {
// Process current->data
current = current->next;
}

Q4. How can I find the length of a singly linked list?

The length of a singly linked list can be calculated by traversing the list and counting the number of nodes.

int length = 0;
Node* current = head;
while (current != nullptr) {
Length++;
current = current->next;
}

Q5. What happens if I try to delete a node in an empty linked list?

If you try to delete a node when the list is empty (i.e., the head pointer is nullptr), it will have no effect, as there are no nodes to delete. It's essential to first check if the list is empty before performing deletion.

if (head != nullptr) {
// Perform deletion
}

Q6. Can I add elements at the end of a singly linked list efficiently?

Yes, you can add elements at the end, but if you don’t maintain a tail pointer, you’ll need to traverse the entire list to reach the last node. This results in an O(n) time complexity for insertion at the end. Maintaining a tail pointer allows for O(1) insertion at the end.

By now, you must be able to understand the theory as well as implement, modify, and troubleshoot single linked lists like a pro. Here are a few more interesting articles you must explore:

Shivani Goyal

Manager, Content

An economics graduate with a passion for storytelling, I thrive on crafting content that blends creativity with technical insight. At Unstop, I create in-depth, SEO-driven content that simplifies complex tech topics and covers a wide array of subjects, all designed to inform, engage, and inspire our readers. My goal is to empower others to truly #BeUnstoppable through content that resonates. When I’m not writing, you’ll find me immersed in art, food, or lost in a good book—constantly drawing inspiration from the world around me.