Data Structure in Java Circular linked list game In an ancient land, a King had
ID: 3752524 • Letter: D
Question
Data Structure in Java
Circular linked list game
In an ancient land, a King had many prisoners. He decided on the following procedure to determine which prisoner to grand freedom. First, all of the prisoners would be lined up one after the other and assigned numbers. The first prisoner would be number 1, the second number 2, and so on up to the last prisoner, number n .
Starting at the prisoner in the first position, he would then count k prisoners down the line, and the kth prisoner would be eliminated from winning her/his freedom removed from the line. The King would then continue, counting k more prisoners, and eliminate every kth prisoner. When he reached the end of the line, he would continue counting from the beginning.
For example, if there were six prisoners, the elimination process would proceed as follows (with step k=2):
1->2->3->4->5->6 Initial list of prisoners; start counting from 1.
1->2->4->5->6 Prisoner 3 eliminated; continue counting from 4.
1->2->4->5 Prisoner 6 eliminated; continue counting from 1.
1->2->5 Prisoner 4 eliminated; continue counting from 5.
2 1->5 Prisoner 2 eliminated; continue counting from 5.
1 Prisoner 5 eliminated; 1 is the lucky winner.
Write a program that creates a circular linked list of nodes to determine which position you should stand in to win your freedom if there are n prisoners. Your program should simulate the elimination process by deleting the node that corresponds to the prisoner that is eliminated for each step in the process.
Create appropriate JUnits to test your program.
Explanation / Answer
Copy paste it and run in your IDE . I was able to print the list elements till the winner is elected has becomne a little problem. Try to fix it yourself if possible. import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class CircularLinkedList { public static void main(String args[]){ // Assigning LinkedList using Data Structures java collections List circularlist = new LinkedList(); ((LinkedList) circularlist).addFirst(1); circularlist.add(2);circularlist.add(3); circularlist.add(4);circularlist.add(5); circularlist.add(6); boolean checkflag = false; //Prompting the king to enter the k value to eliminate prisoners System.out.println("Please enter the valid value of k greater than or eqaul to 0"); Scanner scanner = new Scanner(System.in); int k = scanner.nextInt(); if(k < 0){ System.out.println("Please enter the valid value of k greater than or eqaul to 0"); }else{ System.out.println("You have entered the following value of k " + k); System.out.println(" Printing the arraylist as given below "); printList((LinkedList) circularlist); int tracker = 0; int ktracker = 0; while(circularlist.size() != 1){ //Saves the previous state and removes the element from the list if(ktracker+k == tracker){ circularlist.remove(tracker); ktracker = tracker; printList((LinkedList) circularlist); } tracker++; // Circular Linkedlist property // When leads to last element in the circular list reset the trackers state to 0 if(tracker >= circularlist.size()){ tracker = 0; ktracker = 0; } } } if(!checkflag){ for(int h=0;h 0){ System.out.println("The winner is ---> " + circularlist.get(h) ); } } } } public static void printList(LinkedList e){ StringBuffer buffer= new StringBuffer(); for(int i=0;iRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.