My question is (in Java) how could the Josephus problem code below implement an array-based linked list implementation? Please let me know if I am missing any classes, thanks!

Programs:

import java.util.Scanner;

class Node { //Node Constructor int numb; Node next;

public Node() { numb = 0; next = null; }

public int getNumber() { return numb; }

public void setNumber(int numb) { this.numb = numb; }

public Node getNext() { return next; }

public void setNext(Node next) { this.next = next; } }

class LinkedList { //LinkedList Constructor private Node head; private Node tail; private int n; private int k;

public LinkedList(int n,int k) { this.n = n; this.k = k;

for(int i = 1;i <= n; i++) { Node node = new Node(); node.setNumber(i);

if(head == null) { head = node; tail = head; }

else { tail.next=node; tail = node; } }

tail.next = head; //Circular LinkedList }

public int SavingJosephus() { Node prevous = tail; int i = 1;

while(prevous.getNext() != prevous) {

while(i != k) { i++;

prevous = prevous.getNext(); }

i = 1; prevous.setNext(prevous.getNext().getNext()); }

return prevous.getNumber(); } }

public class JosephusProblem {

public static void main(String[] args) { //Main Method Scanner input = new Scanner(System.in); // Input Scanner int i = input.nextInt();

while(i >= 1) { int n = input.nextInt(); int k = input.nextInt();

LinkedList circle = new LinkedList(n,k); //LinkedList name circle System.out.println(circle.SavingJosephus()); i--; } } }

//---------------------------------------------------------------------------- // ArrayRefSortedList.java by Dale/Joyce/Weems Chapter 7 // // Implements an array-based sorted linked list of String //----------------------------------------------------------------------------

import ch06.lists.*; public class ArrayRefSortedStringList implements ListInterface { protected static final int NUL = -1; // End of list symbol protected class AListNode { private String info; // The info in a list node private int next; // A link to the next node on the list } protected AListNode[] nodes; // Array of AListNode holds the linked list protected int list; // Reference to the first node on the list protected int free; // Reference to the first node on the free list protected int numElements; // Number of elements in the list protected int currentPos; // Current position for iteration

// set by find method protected boolean found; // true if element found, else false protected int location; // node containing element, if found protected int previous; // node preceding location

public ArrayRefSortedStringList(int maxElements) // Instantiates and returns a reference to an empty list object with // room for maxElements elements { nodes = new AListNode[maxElements]; for (int index = 0; index < maxElements; index++) nodes[index] = new AListNode(); // Link together the free nodes. for (int index = 1; index < maxElements; index++) nodes[index - 1].next = index; nodes[maxElements - 1].next = NUL; list = NUL; free = 0; numElements = 0; currentPos = NUL; }

protected int getNode() // Returns the index of the next available node from the free list // and updates the free list index { int hold; hold = free; free = nodes[free].next; return hold; }

protected void freeNode(int index) // Frees the node at array position index by linking it into the // free list { nodes[index].next = free; free = index; }

public boolean isFull() // Determines whether this list is full { return (free == NUL); }

public boolean remove (String element) // Removes an element e from this list such that e.equals(element) // and returns true; if no such element exists, returns false { int hold; // To remember removed node index find(element); if (found) { hold = location; if (list == location) list = nodes[list].next; // remove first node else nodes[previous].next = nodes[location].next; freeNode(hold); numElements--; } return found; }

}

//---------------------------------------------------------------------------- // ListInterface.java by Dale/Joyce/Weems Chapter 6 // // The lists are unbounded and allow duplicate elements, but do not allow // null elements. As a general precondition, null elements are not passed as // arguments to any of the methods. // // The list has a special property called the current position - the position // of the next element to be accessed by getNext during an iteration through // the list. Only reset and getNext affect the current position. //----------------------------------------------------------------------------

package ch06.lists;

public interface ListInterface { int size(); // Returns the number of elements on this list.

void add(T element); // Adds element to this list.

boolean remove (T element); // Removes an element e from this list such that e.equals(element) // and returns true; if no such element exists, returns false. boolean contains (T element); // Returns true if this list contains an element e such that // e.equals(element); otherwise, returns false. T get(T element); // Returns an element e from this list such that e.equals(element); // if no such element exists, returns null. String toString(); // Returns a nicely formatted string that represents this list. void reset(); // Initializes current position for an iteration through this list, // to the first element on this list.

T getNext(); // Preconditions: The list is not empty // The list has been reset // The list has not been modified since the most recent reset // // Returns the element at the current position on this list. // If the current position is the last element, then it advances the value // of the current position to the first element; otherwise, it advances // the value of the current position to the next element. }