Option 2 - Linked List - Josephus Problem Linked List Specification: Create a Templated/Generic Linked List....

Transcribed Image Text:

Option 2 - Linked List - Josephus Problem Linked List Specification: Create a Templated/Generic Linked List. This can be a Singly Linked List, a Singly Circular Linked List, a Doubly Linked List or a Doubly Circular Linked List. Any option is fine as long as it fits the required specification. Your linked list must have the following minimum specification: . Node<T> 。 Properties -data:T ■ -next:Node<T> 。 Methods +getData(): T ■ +setData(int):void ■ +getNext() : Node<T> ⚫ +setNext (Node<T>):void LinkedList<T> 。 Properties -size:int -head: Node<T> -tail:Node<T> 。 Methods: +addToFront (T):void +addToEnd (T):void +addAtIndex(value:T, index:int):void ⚫ Should throw an Exception if the index is larger than the size or a negative number ■ +deleteFront() : void ■ +deleteEnd():void ■+deleteIndex(int):void ⚫ Should throw an Exception if the index is larger than the size or a negative number ⚫ +deleteFirst(value:T): boolean • Finds and deletes the first matching value • Returns true if it worked, false if the value wasn't found ■ +empty():void ■ +contains(T): Boolean • Retuns true if the item is found in the list ■ +toString(): String • Return a string representing your LinkedList Extra credit Opportunity +5: Write a reverseList(): LinkedList<T> method that returns the singly linked list reversed. This is a common job interview challenge. Give an interface option to show it working. Josephus Problem: This is mathematical pattern problem based on a historical event: "There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom. The task is to choose the place in the initial circle so that you survive (are the last one remaining)." -- Wikipedia, http://en.wikipedia.org/wiki/Josephus problem Assume that the number of people in the circle may be any number between zero and one hundred. Assume that every Nth person around the circle is killed each turn, where N is an integer between one and twenty. Specifications: • Create an application in Java that uses a linked list to represent the circle of people, numbered from 1 to numberOfPeople. • Get the number of people and the skip value from the user via console input. Output the number of the individual that survives the mass execution. • Make sure you indicate if your skip value is inclusive or exclusive in your output. Inclusive: n 3-X0 0X00X ■ Every third person is killed with 2 skipped between 。 Exclusive: n-3-X000X000X Sample Output: ■ 3 people are skipped and the next is executed Welcome to the Josephus Problem. How many people in the circle (1100)? 5 Enter the number of people to skip between eliminations: 2 Running: Initial puzzle: 1-2-3-4-5 Eliminated #3 Remaining: 1-2-4-5 Eliminated #1 Remaining: 24-5 Eliminated #5 Remining: 2 - 4 Eliminated #2 Survivor: 4 Sample to help debug (note -inclusive, above example would be n = 5 and k = 3): https://www.geogebra.org/m/ExvvrBbR Option 2 - Linked List - Josephus Problem Linked List Specification: Create a Templated/Generic Linked List. This can be a Singly Linked List, a Singly Circular Linked List, a Doubly Linked List or a Doubly Circular Linked List. Any option is fine as long as it fits the required specification. Your linked list must have the following minimum specification: . Node<T> 。 Properties -data:T ■ -next:Node<T> 。 Methods +getData(): T ■ +setData(int):void ■ +getNext() : Node<T> ⚫ +setNext (Node<T>):void LinkedList<T> 。 Properties -size:int -head: Node<T> -tail:Node<T> 。 Methods: +addToFront (T):void +addToEnd (T):void +addAtIndex(value:T, index:int):void ⚫ Should throw an Exception if the index is larger than the size or a negative number ■ +deleteFront() : void ■ +deleteEnd():void ■+deleteIndex(int):void ⚫ Should throw an Exception if the index is larger than the size or a negative number ⚫ +deleteFirst(value:T): boolean • Finds and deletes the first matching value • Returns true if it worked, false if the value wasn't found ■ +empty():void ■ +contains(T): Boolean • Retuns true if the item is found in the list ■ +toString(): String • Return a string representing your LinkedList Extra credit Opportunity +5: Write a reverseList(): LinkedList<T> method that returns the singly linked list reversed. This is a common job interview challenge. Give an interface option to show it working. Josephus Problem: This is mathematical pattern problem based on a historical event: "There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom. The task is to choose the place in the initial circle so that you survive (are the last one remaining)." -- Wikipedia, http://en.wikipedia.org/wiki/Josephus problem Assume that the number of people in the circle may be any number between zero and one hundred. Assume that every Nth person around the circle is killed each turn, where N is an integer between one and twenty. Specifications: • Create an application in Java that uses a linked list to represent the circle of people, numbered from 1 to numberOfPeople. • Get the number of people and the skip value from the user via console input. Output the number of the individual that survives the mass execution. • Make sure you indicate if your skip value is inclusive or exclusive in your output. Inclusive: n 3-X0 0X00X ■ Every third person is killed with 2 skipped between 。 Exclusive: n-3-X000X000X Sample Output: ■ 3 people are skipped and the next is executed Welcome to the Josephus Problem. How many people in the circle (1100)? 5 Enter the number of people to skip between eliminations: 2 Running: Initial puzzle: 1-2-3-4-5 Eliminated #3 Remaining: 1-2-4-5 Eliminated #1 Remaining: 24-5 Eliminated #5 Remining: 2 - 4 Eliminated #2 Survivor: 4 Sample to help debug (note -inclusive, above example would be n = 5 and k = 3): https://www.geogebra.org/m/ExvvrBbR

Answer rating: 100% (QA)

Here is the completed code for this problem LinkedListjava LinkedList class public class LinkedList pointers to head and tail of the list private Node head private Node tail current size private int s... View the full answer