Traversal of Singly Linked List (Recursive Approach)
Approach:
We can traverse Singly Linked List using recursion by defining a recursive function with takes pointer to a node as an argument and check if the pointer points to null, then return otherwise print the value of the node to which the pointer points to and call the recursive function again with the next node as the argument.
Step-by-step algorithm:
- Firstly, we will define a recursive method to traverse the singly linked list, which take a node as a parameter.
- Secondly, we will take a base case, that is, if the node is null then we will return from the recursive method.
- After it, we will recursively call the recursive method with the next node as the parameter.
- Then, we will start the recursive traversal from the head node.
Below is the implementation of the recursive approach.
#include <iostream>
// Node class
class Node {
public:
int data;
Node* next;
// Constructor for creating a new node with given data
Node(int data)
{
this->data = data;
this->next = nullptr;
}
};
// Function to traverse the linked list
void traverseList(Node* ptr)
{
if (ptr == nullptr) {
std::cout << std::endl;
return;
}
std::cout << ptr->data << " ";
traverseList(ptr->next);
}
int main()
{
// Define the head of the linked list;
Node* head = new Node(10);
// Inserting some elements in the list
head->next = new Node(20);
head->next->next = new Node(30);
head->next->next->next = new Node(40);
traverseList(head);
return 0;
}
class Node {
int data;
Node next;
// Constructor for creating a new node with given data
Node(int data)
{
this.data = data;
this.next = null;
}
}
public class Main {
// Recursive function to traverse the linked list
public static void traverseList(Node ptr)
{
if (ptr == null) {
System.out.println();
return;
}
System.out.print(ptr.data + " ");
traverseList(ptr.next);
}
public static void main(String[] args)
{
// Define the head of the linked list;
Node head = new Node(10);
// Inserting some elements in the list
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
traverseList(head);
}
}
# Node class
class Node:
def __init__(self, data):
# Constructor for creating a new node with given data
self.data = data
self.next = None
# Function to traverse the linked list
def traverse_list(node):
if node is None:
print()
return
print(node.data, end=" ")
traverse_list(node.next)
# Main function
def main():
# Define the head of the linked list
head = Node(10)
# Inserting some elements in the list
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
traverse_list(head)
if __name__ == "__main__":
main()
// Define the Node class
class Node {
// Constructor for creating a new node with given data
constructor(data) {
this.data = data;
this.next = null;
}
}
// Recursive function to traverse the linked list
function traverseList(ptr) {
if (ptr === null) {
console.log();
return;
}
process.stdout.write(ptr.data + " ");
traverseList(ptr.next);
}
// Main function
function main() {
// Define the head of the linked list
let head = new Node(10);
// Inserting some elements in the list
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
traverseList(head);
}
main();
Output
10 20 30 40
Time Complexity: O(N), where N is number of nodes in the linked list.
Space complexity: O(N) because of recursive stack space.
Traversal of Singly Linked List
Traversal of Singly Linked List is one of the fundamental operations, where we traverse or visit each node of the linked list. In this article, we will cover how to traverse all the nodes of a singly linked list along with its implementation.
Examples:
Input: 1->2->3->4->5->null
Output: 1 2 3 4 5
Explanation: Every element of each node from head node to last node is printed which means we have traversed each node successfully.Input: 10->20->30->40->50->null
Output: 10 20 30 40 50
Explanation: Every element of each node from head node to last node is printed which means we have traversed each node successfully.