Traversal of Singly Linked List (Iterative Approach)
The iterative approach to traversing a singly linked list involves using a loop to visit each node of the list sequentially. We start from the head node and use a temporary pointer variable to keep track of the current node being visited. The temporary pointer is initially set to the head of the list and is updated to the next node in each iteration of the loop until it reaches the end of the list (i.e. when the next pointer becomes NULL).
Let’s understand this process that how it works :
1. Initialize a temporary pointer variable, let's call it "current," and set it to the head of the linked list.
2. Enter a loop that continues until "current" becomes NULL.
3. Inside the loop, process the data of the current node (e.g., print the data, and perform a specific operation).
4. Update the "current" pointer to point to the next node by assigning it the value of the next pointer of the current node.
5. Repeat steps 3-4 until "current" becomes NULL, indicating the end of the list has been reached.
By following these steps, we can traverse the entire linked list and access each node's data in a sequential manner.
Step-by-Step Algorithm
Let’s see a step-by-step algorithm for the iterative traversal of a singly linked list:
1. Initialize a pointer variable "current" to the head of the linked list.
2. While "current" is not NULL, do the following:
a. Process the data of the current node (e.g., print the data, perform a specific operation).
b. Update "current" to point to the next node by assigning it the value of the next pointer of the current node.
3. If "current" becomes NULL, exit the loop as the end of the list has been reached.
This algorithm provides a clear and concise set of steps to perform the iterative traversal of a singly linked list. It ensures that each node is visited exactly once and that the traversal continues until the end of the list is reached.
Examples
- C
- C++
- Java
- Python
- JavaScript
- C#
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void traverseList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
printf("Linked List: ");
traverseList(head);
return 0;
}
You can also try this code with Online C Compiler
C++
#include <iostream>
struct ListNode {
int data;
ListNode* next;
};
void traverseList(ListNode* head) {
ListNode* current = head;
while (current != NULL) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
int main() {
ListNode* head = new ListNode{1, NULL};
ListNode* second = new ListNode{2, NULL};
ListNode* third = new ListNode{3, NULL};
head->next = second;
second->next = third;
std::cout << "Linked List: ";
traverseList(head);
delete head;
delete second;
delete third;
return 0;
}
You can also try this code with Online C++ Compiler
Java
class ListNode {
int data;
ListNode next;
public ListNode(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedListTraversal {
public static void traverseList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
ListNode head = new ListNode(1);
ListNode second = new ListNode(2);
ListNode third = new ListNode(3);
head.next = second;
second.next = third;
System.out.print("Linked List: ");
traverseList(head);
}
}
You can also try this code with Online Java Compiler
Python
class ListNode:
def __init__(self, data=0, next=None):
self.data = data
self.next = next
def traverse_list(head):
current = head
while current:
print(current.data, end=" ")
current = current.next
print()
# Create the linked list
head = ListNode(1)
second = ListNode(2)
third = ListNode(3)
head.next = second
second.next = third
print("Linked List:", end=" ")
traverse_list(head)
You can also try this code with Online Python Compiler
JavaScript
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
function traverseList(head) {
let current = head;
while (current) {
console.log(current.data);
current = current.next;
}
}
// Create the linked list
const head = new ListNode(1);
const second = new ListNode(2);
const third = new ListNode(3);
head.next = second;
second.next = third;
console.log("Linked List:");
traverseList(head);
You can also try this code with Online Javascript Compiler
C#
public class ListNode
{
public int data;
public ListNode next;
public ListNode(int data)
{
this.data = data;
next = null;
}
}
public class LinkedList
{
public void TraverseList(ListNode head)
{
ListNode current = head;
while (current != null)
{
Console.Write(current.data + " ");
current = current.next;
}
Console.WriteLine();
}
static void Main(string[] args)
{
ListNode head = new ListNode(1);
ListNode second = new ListNode(2);
ListNode third = new ListNode(3);
head.next = second;
second.next = third;
Console.Write("Linked List: ");
LinkedList linkedList = new LinkedList();
linkedList.TraverseList(head);
}
}
Output
Linked List: 1 2 3
Time Complexity
The time complexity of the iterative traversal algorithm is O(n), where n is the number of nodes in the linked list. This is because we visit each node exactly once during the traversal. The time taken is directly proportional to the size of the linked list, as we need to process each node to access its data and move to the next node.
In the worst case, where we need to traverse the entire linked list, the time complexity remains O(n). This is because we have to visit all n nodes to complete the traversal.
Space Complexity
The space complexity of the iterative traversal algorithm is O(1), which means it uses constant extra space. This is because we only use a single temporary pointer variable to keep track of the current node during the traversal. The space required does not depend on the size of the linked list, as we are not storing any additional data structures that grow with the input size.
The iterative traversal algorithm is space-efficient since it does not require any extra space that scales with the size of the linked list.
In summary, the iterative traversal of a singly linked list has a time complexity of O(n) and a space complexity of O(1). It provides an efficient way to visit each node of the list without requiring any additional data structures.
Traversal of Singly Linked List (Recursive Approach)
In addition to the iterative approach, we can also traverse a singly linked list using recursion. The recursive approach follows the natural recursive structure of a linked list, where each node points to the next node, and the last node points to NULL.
The recursive traversal algorithm works as follows:
1. Base Case: If the current node is NULL, return as there are no more nodes to process.
2. Recursive Case:
a. Process the data of the current node (e.g., print the data, perform a specific operation).
b. Recursively call the traversal function on the next node by passing `current->next` as the argument.
The recursive approach breaks down the problem into smaller subproblems. Each recursive call processes the current node and then makes a recursive call to process the remaining nodes in the list. This process continues until the base case is reached, which is when the current node becomes NULL.
Let’s understand the breakdown of the recursive traversal process:
1. Start with the head node of the linked list.
2. Check if the current node is NULL. If it is, return as there are no more nodes to process.
3. If the current node is not NULL:
a. Process the data of the current node.
b. Recursively call the traversal function on the next node by passing `current->next` as the argument.
4. The recursive calls will continue until the base case is reached (i.e., the current node becomes NULL).
By following these steps, the recursive traversal will visit each node of the linked list and process their data.
Note: The recursive approach provides a concise and elegant solution to traversing a linked list. It takes advantage of the recursive nature of the linked list structure, where each node points to the next node, and the last node points to NULL.
Step-by-Step Algorithm
Let’s look at a step-by-step algorithm for the recursive traversal of a singly linked list:
1. Define a recursive function, let's call it `traverseList`, that takes the head of the linked list as a parameter.
2. In the `traverseList` function:
a. Check the base case: If the current node is NULL, return as there are no more nodes to process.
b. If the current node is not NULL:
- Process the data of the current node (e.g., print the data, perform a specific operation).
- Recursively call the `traverseList` function on the next node by passing `current->next` as the argument.
3. Call the `traverseList` function with the head of the linked list to start the recursive traversal.
Let’s look at a proper representation of the recursive algorithm:
traverseList(head):
if head is NULL:
return
else:
process data of head
traverseList(head->next)
This step-by-step algorithm outlines the recursive approach to traversing a singly linked list. The recursive function `traverseList` takes the head of the linked list as a parameter. It first checks the base case, which is when the current node becomes NULL, indicating the end of the list. If the base case is not met, the function processes the data of the current node and then makes a recursive call to `traverseList` with the next node as the argument.
The recursive calls will keep happening until the base case is reached, at which point the recursion will start unwinding, and the traversal will be complete.
Examples
- C
- C++
- Java
- Python
- JavaScript
- C#
C
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void traverseList(struct Node* head) {
if (head == NULL) {
return;
}
printf("%d ", head->data);
traverseList(head->next);
}
int main() {
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
printf("Linked List: ");
traverseList(head);
printf("\n");
return 0;
}
You can also try this code with Online C Compiler
C++
#include <iostream>
struct ListNode {
int data;
ListNode* next;
};
void traverseList(ListNode* head) {
if (head == NULL) {
return;
}
std::cout << head->data << " ";
traverseList(head->next);
}
int main() {
ListNode* head = new ListNode{1, NULL};
ListNode* second = new ListNode{2, NULL};
ListNode* third = new ListNode{3, NULL};
head->next = second;
second->next = third;
std::cout << "Linked List: ";
traverseList(head);
std::cout << std::endl;
delete head;
delete second;
delete third;
return 0;
}
You can also try this code with Online C++ Compiler
Java
class ListNode {
int data;
ListNode next;
public ListNode(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedListTraversal {
public static void traverseList(ListNode head) {
if (head == null) {
return;
}
System.out.print(head.data + " ");
traverseList(head.next);
}
public static void main(String[] args) {
ListNode head = new ListNode(1);
ListNode second = new ListNode(2);
ListNode third = new ListNode(3);
head.next = second;
second.next = third;
System.out.print("Linked List: ");
traverseList(head);
System.out.println();
}
}
You can also try this code with Online Java Compiler
Python
class ListNode:
def __init__(self, data=0, next=None):
self.data = data
self.next = next
def traverse_list(head):
if head is None:
return
print(head.data, end=" ")
traverse_list(head.next)
# Create the linked list
head = ListNode(1)
second = ListNode(2)
third = ListNode(3)
head.next = second
second.next = third
print("Linked List:", end=" ")
traverse_list(head)
print()
You can also try this code with Online Python Compiler
JavaScript
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
function traverseList(head) {
if (head === null) {
return;
}
console.log(head.data);
traverseList(head.next);
}
// Create the linked list
const head = new ListNode(1);
const second = new ListNode(2);
const third = new ListNode(3);
head.next = second;
second.next = third;
console.log("Linked List:");
traverseList(head);
You can also try this code with Online Javascript Compiler
C#
public class ListNode
{
public int data;
public ListNode next;
public ListNode(int data)
{
this.data = data;
next = null;
}
}
public class LinkedList
{
public void TraverseList(ListNode head)
{
if (head == null)
{
return;
}
Console.Write(head.data + " ");
TraverseList(head.next);
}
static void Main(string[] args)
{
ListNode head = new ListNode(1);
ListNode second = new ListNode(2);
ListNode third = new ListNode(3);
head.next = second;
second.next = third;
Console.Write("Linked List: ");
LinkedList linkedList = new LinkedList();
linkedList.TraverseList(head);
Console.WriteLine();
}
}
Output
Linked List: 1 2 3
Time Complexity
The time complexity of the recursive traversal algorithm is O(n), where n is the number of nodes in the linked list. This is because the recursive function visits each node exactly once. The time taken is directly proportional to the size of the linked list, as the function needs to process each node to access its data and make a recursive call to the next node.
In the worst case, where the recursive function needs to traverse the entire linked list, the time complexity remains O(n). This is because the function will make n recursive calls, one for each node in the list.
Space Complexity
The space complexity of the recursive traversal algorithm is O(n) in the worst case, where n is the number of nodes in the linked list. This is because the recursive calls will be stored on the call stack, and the maximum depth of the recursion will be equal to the number of nodes in the list.
Each recursive call requires a certain amount of space on the call stack to store the function parameters, local variables, and the return address. In the worst case, when the linked list is traversed to the end, the recursion depth will reach n, and the call stack will contain n recursive calls.
It's important to note that the space complexity of O(n) is due to the recursive calls on the call stack and not because of any additional data structures used within the algorithm.
In summary, the recursive traversal of a singly linked list has a time complexity of O(n) and a space complexity of O(n) in the worst case. While the recursive approach provides a concise and elegant solution, it may not be the most space-efficient compared to the iterative approach, especially for large linked lists or in systems with limited stack space.
Frequently Asked Questions
Can we modify the data of nodes while traversing the linked list?
Yes, we can modify the data of nodes while traversing the linked list by accessing and updating the data member of each node.
Is it possible to traverse a linked list in reverse order?
Yes, it is possible to traverse a linked list in reverse order. One approach is to use recursion, where the recursive function first traverses to the end of the list and then processes the nodes in reverse order while backtracking.
How do we handle an empty linked list during traversal?
When traversing an empty linked list, the head pointer will be NULL. In the iterative approach, the loop condition will fail immediately, and in the recursive approach, the base case will be triggered, resulting in no nodes being processed.
Conclusion
In this article, we explained the concept of traversing a singly linked list using both iterative and recursive approaches. We provided step-by-step algorithms, and code examples in multiple programming languages, and analyzed the time and space complexity of each approach. Learning the concept that how to traverse a linked list is very important for performing various operations and solving problems related to linked lists that will be very helpful in your data structures related problems and concepts.
You can also check out our other blogs on Code360.
85+ registered