Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024

# Select a Random Node from a Linked List

## Introduction

Data Structures and Algorithms are a very prominent part of tech interviews to test the candidateâ€™s problem-solving ability. To test this aspect, interviewers usually present the candidate with a programming question.

In this blog, we will discuss one such question.

Recommended Topic, Floyds Algorithm

### Problem Statement

You are given a Linked List, a Singly Linked List specifically. You are supposed to return a random node value from the Linked List. Each node should have an equal possibility of getting selected.

### Explanation of the Problem Statement

So, basically, you are given a Singly Linked List. You are to write a function that returns a random node value from the Linked List every time it is called.

But, the catch here is that, letâ€™s say there are â€˜nâ€™ nodes in the Linked List. Then, the probability of every node getting selected should be 1/n. You should keep in mind to maintain this.

You cannot return as you feel like. You should think of such a mechanism that actually makes it random.

### Sample Example

Consider a Linked List(Singly Linked List) with 4 nodes. This means that its length is 4. Something like this:

If the above-Linked List is considered, then on call of the function, letâ€™s say random_node(). Every time, it should return a different node value, like 3 on the first call, 1 on the second call, and so on.

## Approach - 1: Brute Force Approach

So, there is the use of the word random in the question itself, which leads to a hint on using some function or way of generating some random value.

Also, you may have observed till now that it is about being random implicitly through some mechanism.

For that, letâ€™s assign index value for understanding sake to the nodes of the singly Linked List.

So, let us say we know the length and therefore, we have indexed it accordingly. Now, we generate a random value in [0,length_of_linked_list).

Now, whatever value we get we return that specific node value.

For example: If the random value produced is 3, then 4 is returned.

Now, there are two sub-tasks- finding the length of the Linked List and generating a random value less than the length of the Linked List.
The length can be found using a loop till the next node is not null.

For random value, every language has some function that produces random value. So that can be employed for this. Then, to reduce that value to be less than the length of the Linked List, the modulus can be taken with the length of the Linked List.

### Steps of the Algorithm

1. Find the length of the Linked List. To do so, initialize a variable to 0 and traverse the Linked List till the end of it and increment the variable every time a node is encountered.
2. Generate a random value using the rand() function(in C++) and make it less than the length of the Linked List, let us say this is stored in rand_val.
3. Now, traverse the Linked List till you cover the number of nodes equal to the rand_val.
4. Return the value of this node.

### Implementation in C++

Code for the above-explained approach in C++ is as follows:

``````#include<bits/stdc++.h>
using namespace std;

class Node    //Nodes of the Linked List
{
public:
int value;
Node* next;
Node(int num)
{
this->value=num;
this->next=NULL;
}
};

{
int length=0;
public:
{
}
void insert(int num);
void find_length();
void rand_value();
};

void linked_list::insert(int num)   //insert nodes in Linked List
{
Node* newNode=new Node(num);

{
return;
}

while(t->next!=NULL)
{
t=t->next;
}
t->next=newNode;
}

void linked_list::find_length()   //finding length of he Linked List
{
while(t!=NULL)
{
t=t->next;
length++;
}
}

void linked_list::rand_value()    //producing random node value
{
if(length==0)
return;

time_t current_time;
srand(time(&current_time));
int rand_val=(rand()%length);
for(int i=0;i<rand_val;i++)
{
t=t->next;
}
cout<<"Random value is: "<<t->value<<"\n";
}

int main()
{
cout<<"First make a Linked List\n";
return 0;
}``````

Input:

``````linked_list l;
l.insert(1);
l.insert(2);
l.insert(3);
l.insert(4);
l.insert(5);
l.find_length();
l.rand_value(); ``````

Output:

``````First make a Linked List
Random value is: 2    //Time is 23:20 25/5/2022

First make a Linked List
Random value is: 1    //Time is 23:21 25/5/2022 ``````

#### Complexity Analysis

Time Complexity: O(n)

So, we see that we traverse the whole Linked List once for length and once for the random value of the node. Therefore, the Time Complexity is O(n+n) or O(n). Here, â€˜nâ€™ is the number of nodes in the Linked List.

Space Complexity: O(n)

Space complexity is also linear as the memory required increases linearly with the addition of each node. But, one thing to note here is that we traverse the Linked List twice.
Of course, you can make small changes to run the code for the required number of test cases.

## Approach - 2: Optimized Approach

So, the approach discusses above uses linear time complexity, which is very good.

But, now let us try to further think of an approach where only one traversal is used. That is, somehow eliminates the need of finding the length of the Linked List.

For that, a technique similar to Reservoir Sampling can be used. But, of course, it is not exactly that. Even if you do not know about it. You can understand the approach to this question very well.

This approach takes a node of the Linked List and tries to take the random node from the, instead of all the â€˜nâ€™ nodes of the Linked List. It basically, randomly chooses any node from the n nodes, if this node is not selected previously, then it is the node whose value is considered as the random node value.

Proof of the probability part:

Let there be total â€˜nâ€™ nodes in the Linked List. Letâ€™s take the last node.

The probability that the last node value returned is simply 1/n as for the last node, that is, the nth node, a random number in [0,n) is produced and the last node value is returned if the number is 0.

According to the question, the probability of each node should be 1/n. So, taking for the second last node,

The probability for the second lat node value to be returned

= Probability that the second last node value is returned * Probability that the last node value is not returned

= (1/(n-1)) * ((n-1)/n)

= 1/n

In a similar way, it can be proved for other nodes as well.

### Steps of the Algorithm

1. Declare a variable â€˜ansâ€™ as the first node value.
2. Assume another variable with value 2, say i=2.
3. Traversing from the second node onwards till end of Linked List

3.1. Generate a random number from 0 to i-1 and store it in k

Let the generated random number is j.

3.2.  If k is equal to 0, then update â€˜ansâ€™ with this node.

3.3.  i=i+1

3.4. Move to next node

### Implementation in C++

The C++ code for the above explanation is as follows:

``````#include<bits/stdc++.h>
using namespace std;

class Node    //Nodes of the Linked List
{
public:
int value;
Node* next;
Node(int num)
{
this->value=num;
this->next=NULL;
}
};

{
int length=0;
public:
{
}
void insert(int num);
void rand_value();
};

void linked_list::insert(int num)   //insert nodes in Linked List
{
Node* newNode=new Node(num);

{
return;
}

while(t->next!=NULL)
{
t=t->next;
}
t->next=newNode;
}

void linked_list::rand_value()    //producing random node value
{
if (head == NULL)
return;

srand(time(NULL));
int ans = head->value;
Node *t = head;
int i;
for(i=2;t!=NULL;i++)
{
if (rand()%i==0)
ans=t->value;
t=t->next;
}
cout<<"Random node value is:"<<ans<<"\n";

}

int main()
{
cout<<"First make a Linked List\n";
return 0;
}``````

Input:

``````linked_list l;
l.insert(1);
l.insert(2);
l.insert(3);
l.insert(4);
l.insert(5);
l.rand_value(); ``````

Output:

``````First make a Linked List
Random node value is:3 ``````

#### Complexity Analysis

Time Complexity: O(n)

It traverses the whole Linked List only once. Tie complexity is O(n), with only one traversal of the whole Linked List. It reduces the traversal by one, which is of great importance in large programs.
Space Complexity: O(n)

## Frequently Asked Questions

### What is a Linked List?

A Linked List is a data structure that is a collection of nodes having some data/information and associated with each other through pointers.

### What are the different types of Linked Lists?

There are mainly 4(four) types of Linked List:

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Circular Doubly Linked List

### What are the advantages of Linked Lists?

A few advantages of Linked Lists include:

1. Reduce memory wastage
2. Easy implementation
3. Dynamic Data Structure
4. Allow non-linear relation between data

### What is Reservoir Sampling?

It is a collection of randomized algorithms that are used to produce a group of random values from a given set of values.

## Conclusion

This article extensively discusses different approaches to a question related to Linked List along with their pseudocode, implementation, and time trade offs

We hope that this blog has helped you enhance your knowledge regarding Selecting a Random Node from a Linked List, and if you would like to learn more, check out our articles on Coding Ninjas Blogs

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSQLSystem Design, and many more!
If you want to test your competency in coding, you may check out the Mock Test Series and participate in the Contests organized on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the Problems, Interview Experiences, and Interview Bundle for placement preparations.

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

Do upvote our blog to help other ninjas grow.

Happy Coding!

Topics covered
1.
Introduction
1.1.
Problem Statement
1.2.
Explanation of the Problem Statement
1.3.
Sample Example
2.
Approach - 1: Brute Force Approach
2.1.
Steps of the Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Approach - 2: Optimized Approach
3.1.
Steps of the Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.