In this guide, you will discover the process of choosing a random node from a singly linked list in C++. To pick a random node from a singly linked list, adhere to the following steps:
Define the layout of a node within the linked list initially. Each node must consist of a data field along with a reference to the next node.
Example
struct Node {
int data;
Node* next;
// Constructor to initialize the node
Node(int value) : data(value), next(nullptr) {}
};
Create a Singly Linked List:
- Following that, create a class that will serve as the representation of the singly linked list. This class must include functions for the addition of nodes and executing necessary operations.
Example
class LinkedList {
public:
Node* head;
// Constructor to initialize the linked list
LinkedList() : head(nullptr) {}
// Method to insert a node at the end of the list
void insertNode(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}
};
Selecting a Random Node:
- Subsequently, it is essential to iterate through the linked list to select a node at random. A common approach is to count the nodes and generate a random index within that count. Iterate through the list again, halting at the randomly selected index.
Example:
Example
#include <iostream>
#include <cstdlib>
#include <ctime>
struct Node {
int data;
Node* next;
// Constructor to initialize the node
Node(int value) : data(value), next(nullptr) {}
};
class LinkedList {
public:
Node* head;
// Constructor to initialize the linked list
LinkedList() : head(nullptr) {}
// Method to insert a node at the end of the list
void insertNode(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}
// Method to select a random node from the list
Node* getRandomNode() {
if (!head) {
return nullptr; // Return nullptr for an empty list
}
// Count the number of nodes
int count = 0;
Node* temp = head;
while (temp) {
count++;
temp = temp->next;
}
// Generate a random index within the range [0, count-1]
int randomIndex = rand() % count;
// Traverse the list to the randomly selected index
temp = head;
for (int i = 0; i < randomIndex; ++i) {
temp = temp->next;
}
return temp;
}
};
int main() {
srand(time(nullptr)); // Seed for random number generation
LinkedList list;
list.insertNode(1);
list.insertNode(2);
list.insertNode(3);
list.insertNode(4);
list.insertNode(5);
Node* randomNode = list.getRandomNode();
if (randomNode) {
std::cout << "Random Node Value: " << randomNode->data << std::endl;
} else {
std::cout << "The list is empty." << std::endl;
}
return 0;
}
Output:
Output
Random Node Value: 4
Explanation:
Prior to calling getRandomNode, the script imports necessary libraries, seeds the random number generator using srand(time(nullptr)), and inserts some example nodes into the linked list within the main function.
