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.
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.

## 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; }
}
{
{
// adding the data to new_node
Node new_node = new Node(val);
// initializing the next node as head node
// Now head node is equal to the new_node
}
public static void main(String[] args)
{
// 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){
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;
class Node
{
public:
int data;
Node* next;
};
// class for creating a LinkedList
{
// allocating new_node
Node* new_node =new Node();
new_node->data = val;
}
int length = 0;
while (currentPointer != NULL) {
if (length == value)
return (currentPointer->data);
length++;
currentPointer = currentPointer->next;
}
return -1;
}
int main(){
//printing the Nth Node data
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; }
}
{
{
// adding the data to new_node
Node new_node = new Node(new_data);
// initializing the next node as head node
// Now head node is equal to the new_node
}
public static void main(String[] args)
{
// Printing the Nth Node data of LinkedList by calling the getNthNode()
}
static int getNthNode(Node head, int value)
{
int length = 0;
// if head node is null then return -1
return -1;
// check if length of the LinkedList is equal to the index value
if (length == value)
// move to the next node and decrease the index value by 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;
class Node
{
public:
int data;
Node* next;
};
// class for creating a LinkedList
{
// allocating new_node
Node* new_node =new Node();
new_node->data = val;
}
int getNthNode(struct Node* head, int value)
{
// if head node is null then return -1
return -1;
// if index value is 0 then return data of the head node
if (value == 0)
// move the currentPointer to the next node and decrease the index value by 1
}
int main(){
//printing the Nth Node data of the LinkedList.
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).

#### 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.