Which ADT is used in the following code, and how would you come to that conclusion? I have a hunch feeling that it's a circular linked list, but don't have an exact reasoning as to why.
public class Josephus {
private final int M = 3;
private class Soldier {
int num;
Soldier next;
Soldier(int n) {
num = n;
}
}
public void survivor(int N) {
System.out.println("Number of soldiers = " + N);
if (N <= 0)
return;
Soldier first = new Soldier(0);
Soldier curr = first;
for (int i =1; n<N; i++) {
curr.next = new Soldier(i);
curr = curr.next;
}
curr.next = first;
Soldier prev = curr;
int d = 0;
int m = 0;
while (curr != prev) {
if(++m >= M){
d++;
System.out.println("Dead soldier = " + curr.num);
if (curr.num == 0) {
System.out.println("You died as number = " + d);
}
prev.next = curr.next;
m = 0;
} else
prev = curr;
curr = curr.next;
}
System.out.println("Final survivor is = " + curr.num);
}
}
I am no data structures expert, but I believe your circular linked list intuition is correct. First, I notice that the following part of the code represents a typical "node" for a data structure:
private class Soldier {
int num;
Soldier next;
Soldier(int n) {
num = n;
}
}
Here we can see that Soldier next; is the reference to the next node. A dead giveaway is usually when you see a class that is composed of an object of itself. Now, there is no "previous" field or "left/right child" field. This suggests that we are not dealing with a binary tree, doubly linked list, or anything of that nature. Which leaves singly linked list or circularly linked list.
Here is where the linked list is constructed:
Soldier first = new Soldier(0);
Soldier curr = first;
for (int i =1; n<N; i++) {
curr.next = new Soldier(i);
curr = curr.next;
}
We can see that each iteration of the for loop creates a new Soldier object, then assigns the node's reference, from the previous iteration, to this new Soldier:
curr.next = new Soldier(i);
Next, we assign the newly constructed Soldier object to curr, so that in our next iteration we can make it point to the next node in the list:
curr = curr.next;
At the end of the loop we end up with the final node pointing to null. If this was not addressed, then we would have a singly linked list. This, however, is not the case as we can see in the line that immediately follows:
curr.next = first;
Here is were the reference of the last added node gets assigned to the first node in the list (which was initialized here: Soldier first = new Soldier(0);), thus making the list circular.
The rest of the code just seems to be iterating over the list and doesn't have an impact on the data structure itself. Sorry if I said some painstakingly obvious things, I just wanted to be thorough :)