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