Linked List Traversal

Problem Statement: Given a Linked List, iterate through it, and print all the elements in it.

Examples

Example 1:

Input Format: 0 -> 1 -> 2

Result 0 1 2 

Explanation: The data of each node has been printed in the output.

Example 2:

Input Format: 2 -> 5 -> 8 -> 7

Result 2 5 8 7 

Explanation: The data of each node has been printed in the output.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

Traversing through the nodes will allow us to print all the elements in a linked list. In order to traverse through a linked list, we need to start at the head of the linked list and move to the next node and repeat this process till we reach the end, which is denoted by NULL in the linked list. 

Algorithm:

  • For traversing the entire linked list, we will have to start with the head of the list and keep moving till we reach the end, i.e., NULL. Initially, keep a pointer temp pointing to the head.
  • Keep iterating the linked list and at every node, print the data, and move to the next node by temp = temp->next.

Code:

C++ Code

class Node {
public:
    int data;
    Node* next;
    // Constructor with both data and next node
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }
    // Constructor with only data (assumes next is nullptr)
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};
int main() {
    // Initializing an array
    vector<int> arr = {2, 5, 8, 7};
    // Creating a linked list manually
    Node* head = new Node(arr[0]);
    head->next = new Node(arr[1]);
    head->next->next = new Node(arr[2]);
    head->next->next->next = new Node(arr[3]);
    // Traversing the linked list and printing data
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    return 0;
}

Output: 2 5 8 7

Time Complexity: O(N), since we are iterating over the entire array, where N is the number of elements in the array.

Space Complexity: O(1), as we have not used any extra space.

Java Code

class Node {
        int data;
        Node next;
        // Constructor with both data and next node
        Node(int data1, Node next1) {
            data = data1;
            next = next1;
        }
        // Constructor with only data (assumes next is null)
        Node(int data1) {
            data = data1;
            next = null;
        }
}
public class LinkedList{
    public static void main(String[] args) {
        // Initializing an array
        int[] arr = {2, 5, 8, 7};
        // Creating a linked list manually
        Node head = new Node(arr[0]);
        head.next = new Node(arr[1]);
        head.next.next = new Node(arr[2]);
        head.next.next.next = new Node(arr[3]);
        // Traversing the linked list and printing data
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
}

Output: 2 5 8 7

Time Complexity: O(N), since we are iterating over the entire array, where N is the number of elements in the array.

Space Complexity: O(1), as we have not used any extra space.

Python Code

class Node:
    def __init__(self, data1, next1=None):
        self.data = data1
        self.next = next1
# Initializing an array
arr = [2, 5, 8, 7]
# Creating a linked list manually
head = Node(arr[0])
head.next = Node(arr[1])
head.next.next = Node(arr[2])
head.next.next.next = Node(arr[3])
# Traversing the linked list and printing data
temp = head
while temp is not None:
    print(temp.data, end=" ")
    temp = temp.next

Output: 2 5 8 7

Time Complexity: O(N), since we are iterating over the entire array, where N is the number of elements in the array.

Space Complexity: O(1), as we have not used any extra space.

JavaScript Code

class Node {
    constructor(data1, next1 = null) {
        this.data = data1;
        this.next = next1;
    }
}
// Initializing an array
let arr = [2, 5, 8, 7];
// Creating a linked list manually
let head = new Node(arr[0]);
head.next = new Node(arr[1]);
head.next.next = new Node(arr[2]);
head.next.next.next = new Node(arr[3]);
// Traversing the linked list and printing data
let temp = head;
while (temp !== null) {
    console.log(temp.data + " ");
    temp = temp.next;
}

Output: 2 5 8 7

Time Complexity: O(N), since we are iterating over the entire array, where N is the number of elements in the array.

Space Complexity: O(1), as we have not used any extra space.

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Neerav Sethi for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article