What Data Structure is Being Used in this Algorithm?

Question

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);
   }
}

Answer 1

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 :)

Answer 2

This is data structure is Circular Linked Lists

Answer 3

The problem here can give good idea of the datastructure used. The Josephus problem is basically a game in which soldiers stand in a circle and every kth person is eliminated until only 1 soldier is left. Now here we need to simulate a list of soldiers standing in a circle hence it is appropriate assumption that datastructure used is a circular link list.