# Josephus Problem with circular link lists

Page 1 of 1

## 2 Replies - 10695 Views - Last Post: 10 April 2008 - 05:39 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=48674&amp;s=36987bfbec0e6ec45a817e7f52081f2e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

Reputation: 0
• Posts: 2
• Joined: 09-April 08

# Josephus Problem with circular link lists

Posted 09 April 2008 - 09:50 PM

``` class Link
{
public int iData;

// Constructor
public Link ( int item )
{
iData = item;
next = null;
}

// Print contents
public String toString ()
{
String str = "( " + iData + " ) ";
return str;
}

}

class CircularList
{

// Constructor
public CircularList ()
{
}

// Insert an element in the list
public void insert ( int item )
{
//new temp object made every time called
{

{
temp = temp.next;
}
}
{
}
}

// Find the link with the given key NOT FINISHED
public Link find ( int key )
{
while ( current.iData != key )
{
if ( current.next == null )
return null;
else
current = current.next;
}

return current;

}
// Delete a link with a given key
public Link delete ( int key )
{

while ( current.iData != key)
{
if ( current.next == null)

return null;
else
{
previous = current;
current = current.next;

}
}

if ( current == head )
else
previous.next = current.next;

if ( current != null)
{
if (current.next == current)
{
current = null;
return current;
}

if (current.next != current)
{
while(tail.next != current)
{
tail = tail.next;
}
current = current.next;
tail.next = current;
}
}
return current;
}
{

}

// Return a string representation of a Circular List
public String toString ()
{
StringBuffer buf = new StringBuffer();
int count = 0;

while ( current != null )
{
if ( count == 4 )
{
buf.append ( current.toString() + "\n" );
count = 0;
}
else
{
buf.append ( current.toString() + " " );
count++;
}

current = current.next;
}

return buf.toString();
}

}

public class Josephus
{
//  program  will read in the number of soldiers, the elimination number n, and the soldier from whom the counting starts.
//havent done this yet
}

```

[b]I am not sure if my logic is correct for a circular link list in my delete, insert, find and toString method. I am also slightly confused as to what should be done in delete after?! should i just call the delete method? delete the key and print the new link?

Is This A Good Question/Topic? 0

## Replies To: Josephus Problem with circular link lists

### #2 pbl

• There is nothing you can't do with a JTable

Reputation: 8365
• Posts: 31,956
• Joined: 06-March 08

## Re: Josephus Problem with circular link lists

Posted 10 April 2008 - 04:45 PM

then new need an insertAfter() and insertBefore() methods.

Reputation: 0
• Posts: 2
• Joined: 09-April 08

## Re: Josephus Problem with circular link lists

Posted 10 April 2008 - 05:39 PM

pbl, on 10 Apr, 2008 - 04:45 PM, said:

then new need an insertAfter() and insertBefore() methods.

i changed it, to have a head and a tail earlier today, but i keep getting a null pointer exception.

```import java.util.*;
{
public Object element;

// Constructor
{
element = o;
next = null;
}

}

class CircularList
{

// Constructor
public CircularList ()
{
tail = null;
}

public void insert ( Object o )
{
}

// Find the link with the given key. Assumes non-empty linked list
public Link find ( Object key )
{
while ( current.element != key )
{
current = current.next;
}
return current;
}

// Delete a link with a given key. Assumes non-empty linked list
public Link delete ( Object key )
{

while ( current.element != key )
{
previous = current;
current = current.next;
}

if ( current == head )
else
//not sure what this part does
previous.next = current.next;
return current;
}

// Return a string representation of a Linked List
public String toString ()
{
StringBuffer buf = new StringBuffer();
int count = 0;

while ( current != null )
{
if ( count == 4 )
{
buf.append ( current.toString() + "\n" );
count = 0;
}
else
{
buf.append ( current.toString() + " " );
count++;
}

current = current.next;
}

return buf.toString();
}

{

}
}

public class Josephus
{
public static void main (String[]args)
{
Scanner sc = new Scanner(System.in);
System.out.print( "Enter the Number of Soldiers:");
int numSoldiers= sc.nextInt();
//read in N the elimination number
System.out.print("Enter the Elimination Number N:");
int elimNum= sc.nextInt();
System.out.print("Enter the Starting Soldier's Capital Letter ID:" );
String iD = sc.next();
//assume input is only one character long
char ch = iD.charAt(0);
CircularList theList = new CircularList();

//fill list
for (int i = 0; i < numSoldiers; i++)
{
ch = (char)((int)ch + i);
Character charObj = new Character ( ch );
theList.insert(charObj);
System.out.println(" the " + i + " object inserted" +theList.toString());
}

}

}

```