Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach 1: Iterative Method
2.1.
Steps of Algorithm
2.2.
Implementation
2.2.1.
Code in Java
2.2.2.
Code in C++
2.2.3.
Complexity Analysis
3.
Approach 2: Recursive Method
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Code in Java
3.2.2.
Code in C++
3.2.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
Can you search a linked list easily?
4.2.
Which search should be used for the linked list?
4.3.
Linked lists require a lot of time to search. What can we do to reduce this time? 
5.
Conclusion
Last Updated: Mar 27, 2024

Function to get Nth node in a Linked List

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

In Linked Lists, objects are connected with a chain of links. These have different links attached to them. Linked lists are widely used data structures, second only to arrays. 

An element is a piece of data stored in each node of a linked list.

A linked list has the next node address at the end of each node that leads to the next node.

In Linked Lists, the first node is the head node connecting the first and other nodes.

Linked lists are collections of memory nodes stored in random order. There are two fields at every node: data at the address and a pointer to the next node in the memory. There is a null pointer at the end of the list.

We are now coming to the main purpose of this blog, which is how to find a specific node's data in a linked list.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm.

Problem Statement

Assume we have a LinkedList with some data elements and that we have to extract the nth position node data from the LinkedList. It is necessary to write a function that searches for the data of the given index value to get this value.

Sample Example

As shown below, we have a Linked List with these elements: Grey => Pink => Black => Blue => Orange.

You have to determine what data value is present in the given index value 3?

We have Blue at the index value 3 in this question.

In this LinkedList, the index value starts at 0, but it can be changed in some questions, so read the question thoroughly.

Also read - Merge sort in linked list

Approach 1: Iterative Method

In computer programming, iteration refers to repeating blocks of code. While there is a larger amount of code, the complexity of time is generally less than for recursion. 

You can find the time complexity of an iteration by counting the repeated cycles within the loop. 

In the following example, there are elements 20 => 76 => 54 => 76 => 20 in our linked list. We are going to look at how to find the nth node data from this LinkedList.

Steps of Algorithm

Step 1: Initialize the current node as currentPointer = head.

Step 2: Initialize the length of the node as length = 0.

Step 3: Enter the while loop and check the condition (LinkedList != NULL) 

  • Now check if the length of the LinkedList is equal to the value of the nth node, i.e., length = value, then return currentPonter.data.
  • Else increase the length by 1 i.e length++ and move the currentPointer to the next node(CurrentPointer = CurrentPointer.next)

Step 4: End the while loop and return -1 means we did not find any node in the LinkedList.

Implementation

Code in Java

A Java program for creating a function to find the Nth Node in a Linked List.

// Node for LinkedList
class Node
{
    int data;
    Node next;
    Node(int d){ 
        data = d;  
        next = null; }
}
// class for LinkedList
class LinkedList
{
    Node head; // head node of LinkedList
    //Function to add data at the end of the LinkedList
    public void add(int val)
    {
        // adding the data to new_node
        Node new_node = new Node(val);
        // initializing the next node as head node  
        new_node.next = head;
        // Now head node is equal to the new_node  
        head = new_node;
    }
    public static void main(String[] args)
    {
        LinkedList element = new LinkedList();
        element.add(20);
        element.add(76);
        element.add(54);
        element.add(74);
        element.add(64);
        // Printing the Nth node data of LinkedList by calling the getNthNode()
        System.out.println("Nth Node data of the LinkedList: " + element.getNthNode(2));
    } 
    private int getNthNode(int value){
        Node CurrentPointer = head;
        int length = 0;
        while (CurrentPointer != null){
            if(length == value)
                return CurrentPointer.data;
            length++;
            CurrentPointer = CurrentPointer.next;
        }
        return -1;
    }
}

 

Code in C++

A C++ program for creating a function to find the Nth Node in a Linked List.

#include <bits/stdc++.h> 
using namespace std; 
// Node for Linked List
class Node  
{  
    public:
    int data; 
    Node* next;  
};  
// class for creating a LinkedList
void add(Node** head_ref, int val)  
{  
    // allocating new_node
    Node* new_node =new Node(); 
    new_node->data = val;  
    new_node->next = (*head_ref);  
    (*head_ref) = new_node;  
}  
int getNthNode(Node *head, int value){
Node *currentPointer = head;
int length = 0;
while (currentPointer != NULL) {
        if (length == value)
            return (currentPointer->data);
        length++;
        currentPointer = currentPointer->next;
}
    return -1;
}
int main(){
    //adding elements in the linkedList
    struct Node* head = NULL;
    add(&head, 20);
    add(&head, 76);
    add(&head, 54);
    add(&head, 74);
    add(&head, 64);
    //printing the Nth Node data
    printf("Nth Node data of LinkedList i: %d\n", getNthNode(head, 2));  
    return 0;
}

 

Output:

Nth Node data of the LinkedList: 54

 

Complexity Analysis

Time Complexity: O(n) as it linearly searches for the values. 

Space complexity: O(1) as it does not require any space to store the values.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2: Recursive Method

Using recursion involves repeatedly calling the same function, and thus, the code length is small. In terms of the previous calls, the nth recursive call can be calculated to determine the time complexity of recursion.

Consider we have Linked List as given below having elements: 20 => 76 => 54 => 76 => 20. Let's see how to find the nth node data from this LinkedList.

Algorithm

Step: 1 Create a method called getNthNode(), which has parameters of starting node and the Nth node value as getNthNode(node, value)

Step: 2 Initialize the length of the LinkedList as length=0;

Step: 3 If the head node is null, then return -1.

Step: 3 If length == value, return the data of the current node.

Step: 4. else return getNthNode(node->next,value-1)

Implementation

Code in Java

A Java program for creating a function to find the Nth Node in a Linked List.

// Node for LinkedList
class Node
{
    int data;
    Node next;
    Node(int d){ 
        data = d;  
        next = null; }
}
// class for LinkedList
class LinkedList
{
    static Node head; // head of LinkedList
    //Function to add data at the end of the LinkedList
    public void add(int new_data)
    {
        // adding the data to new_node
        Node new_node = new Node(new_data);
        // initializing the next node as head node  
        new_node.next = head;
        // Now head node is equal to the new_node  
        head = new_node;
    }
    public static void main(String[] args)
    {
        LinkedList element = new LinkedList();
        // adding elements in the LinkedList
        element.add(20);
        element.add(76);
        element.add(54);
        element.add(54);
        element.add(54);
        // Printing the Nth Node data of LinkedList by calling the getNthNode()
        System.out.printf("Nth Node data of LinkedList is :"+ getNthNode(head, 2));
    } 
    static int getNthNode(Node head, int value)
    {
        int length = 0;
        // if head node is null then return -1
        if (head == null) 
            return -1;
        // check if length of the LinkedList is equal to the index value
        if (length == value)
            return head.data;
        // move to the next node and decrease the index value by 1
        return getNthNode(head.next, value - 1);
    }
}

 

Code in C++

A C++ program for creating a function to find the Nth Node in a Linked List.

#include <bits/stdc++.h> 
using namespace std; 
// Node for Linked List
class Node  
{  
    public:
    int data;  
    Node* next;  
};  
// class for creating a LinkedList
void add(Node** head_ref, int val)  
{  
    // allocating new_node
    Node* new_node =new Node(); 
    new_node->data = val;  
    new_node->next = (*head_ref);  
    (*head_ref) = new_node;  
}    
int getNthNode(struct Node* head, int value)
{
    // if head node is null then return -1
    if (head == NULL)
        return -1;
    // if index value is 0 then return data of the head node
    if (value == 0)
        return head->data;
    // move the currentPointer to the next node and decrease the index value by 1
    return getNthNode(head->next, value - 1);
}
int main(){
    struct Node* head = NULL;
    //adding elements in the linkedList
    add(&head, 20);
    add(&head, 76);
    add(&head, 54);
    add(&head, 74);
    add(&head, 64);
    //printing the Nth Node data of the LinkedList.
    printf("Nth Node data of LinkedList i: %d\n", getNthNode(head, 2));  
    return 0;
}

 

Output:

Nth Node data of the LinkedList: 54

 

Complexity Analysis

Time Complexity: The linear search for the values takes O(n) time. 

Space Complexity: As there is no space required to store the values, it has a space complexity of O(1).

Frequently Asked Questions

Can you search a linked list easily?

The structure makes adding and removing elements in a linked list easy since you need to change the links rather than create the array; however, searching for an element in a singly linked list is very difficult and often takes O(n) time.

Which search should be used for the linked list?

A list can be searched linearly. This takes O(N). A linear search can be performed on an ordered list. The second method is also O(N), but it's twice as fast because, on average, the item you're looking for will be somewhere in the middle, and if it's not found, that's the end.

Linked lists require a lot of time to search. What can we do to reduce this time? 

Using binary search is possible if the elements of your list are sorted and your list is indexable (i.e., getting an element at position i is O(1)). It's better to get the element at the ith position in a linked list than O(N).

Conclusion

In this blog, we have seen how to create a function to get the Nth Node data of a given LinkedList.

We hope that this blog has helped you enhance your knowledge about LinkedList and if you would like to learn more, check out our articles on the link

Recommended Problems -

You can use the Coding Ninjas Studio Guided Path to learn data structures and algorithms, programming languages, etc. Test your coding skills by participating in the Coding Ninjas Studio contests and tests! But suppose you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Coding!

Live masterclass