Home > OS >  How to write a constructor of random integers for a Linked List
How to write a constructor of random integers for a Linked List

Time:10-17

I am working on a project for my Data Structures class that asks me to write a class to implement a linked list of ints. Use an inner class for the Node. Include the methods below. Write a tester to enable you to test all of the methods with whatever data you want in any order. I have to create three different constructors. One of the constructors is meant to be a constructor that creates a linked list of N random integers between low and high. I've written methods that do what the constructor is asking for and therefore wrote the code I would have in a method as a constructor. However, I don't think I'm right. Can someone let me know If I'm doing the right thing? If not tell me what I need to do?

import java.util.Random;

public class LinkedListOfInts {
    Node head;

    private class Node {
        int value;
        Node nextNode;

        public Node(int value, Node nextNode) {
            this.value = value;
            this.nextNode = nextNode;
        }

    }

    public LinkedListOfInts() {

    }

    public LinkedListOfInts(int N, int low, int high) {
        Random random = new Random();

        int[] result = new int[N];

        for (int i = 0; i < N; i  )
            result[i] = random.nextInt(high - low)   low;
    }

    public void addToFront(int x) {
        head = new Node(x, head);
    }

    public String toString() {
        String result = " ";
        for (Node ptr = head; ptr != null; ptr = ptr.nextNode)
            result  = ptr.value   " ";
        return result;
    }

    public static void main(String[] args) {
        LinkedListOfInts list = new LinkedListOfInts();
        for (int i = 0; i < 15; i  )
            list.addToFront(i);
        System.out.println(list);
    }

}

CodePudding user response:

Instead of creating an unused array, you should call addToFront for each random integer to initialize the LinkedListOfInts. Additionally, you should use random.nextInt(high - low 1) low so that high is not excluded.

public LinkedListOfInts(int N, int low, int high) {
    Random random = new Random();
    for (int i = 0; i < N; i  )
        this.addToFront(random.nextInt(high - low   1)   low);
}

To test it:

public static void main(String[] args) {
    LinkedListOfInts list = new LinkedListOfInts(5, 1, 10);
    System.out.println(list);
}

CodePudding user response:

// Java program to select a random node from singly linked list

import java.util.*;

// Linked List Class
class LinkedList {

    static Node head; // head of list

    /* Node Class */
    static class Node {

        int data;
        Node next;

        // Constructor to create a new node
        Node(int d) {
            data = d;
            next = null;
        }
    }

    // A reservoir sampling based function to print a
    // random node from a linked list
    void printrandom(Node node) {

        // If list is empty
        if (node == null) {
            return;
        }

        // Use a different seed value so that we don't get
        // same result each time we run this program
        Math.abs(UUID.randomUUID().getMostSignificantBits());

        // Initialize result as first node
        int result = node.data;

        // Iterate from the (k 1)th element to nth element
        Node current = node;
        int n;
        for (n = 2; current != null; n  ) {

            // change result with probability 1/n
            if (Math.random() % n == 0) {
                result = current.data;
            }

            // Move to next node
            current = current.next;
        }

        System.out.println("Randomly selected key is "   result);
    }

    // Driver program to test above functions
    public static void main(String[] args) {

        LinkedList list = new LinkedList();
        list.head = new Node(5);
        list.head.next = new Node(20);
        list.head.next.next = new Node(4);
        list.head.next.next.next = new Node(3);
        list.head.next.next.next.next = new Node(30);

        list.printrandom(head);

    }
}

Algorithm: (1) Initialize result as first node

result = head->key

(2) Initialize n = 2

(3) Now one by one consider all nodes from 2nd node onward.

(3.a) Generate a random number from 0 to n-1. 

     Let the generated random number is j.

(3.b) If j is equal to 0 (we could choose other fixed number 

      between 0 to n-1), then replace result with current node.

(3.c) n = n 1

(3.d) current = current->next
  • Related