Reputation: 11
Circular linked list help (Java)
I'm having some difficulty with a program I'm working on. I've tried to get help from some of my peers, but we can't figure it out. I'm sure its something simple, but I don't have quite enough experience to figure it out on my one. Here's the assignment:
In an ancient land, the beautiful princess Eve had many suitors. She decided on the following procedure to determine which suitor she would marry. First, all of the suitors would be lined up one after the other and assigned numbers. The first suitor would be number 1, the second number 2, and so on up to the last suitor, number n. Starting at the suitor in the first position, she would then count three suitors down the line (because of the three letters in her name), and the third suitor would be eliminated from winning her hand and removed from the line. Eve would then continue, counting three more suitors, and eliminate every third suitor. When she reached the end of the line, she would continue counting from the beginning.
For example, if there were six suitors, the elimination process would proceed as follows:
123456 Initial list of suitors: start counting from 1.
12456 Suitor 3 eliminated: continue counting from 4.
1245 Suitor 6 eliminated: continue counting from 1.
125 Suitor 4 eliminated: continue counting from 5.
15 Suitor 2 eliminated: continue counting from 5.
1 Suitor 5 eliminated: 1 is the lucky winner.
Write a program that creates a circular linked list of nodes to determine which position you should stand in to marry the princess if there are n suitors. Your program should simulate the elimination process by deleting the node that corresponds to the suitor that is eliminated for each step in the process.
Here's what I have so far:
public class CircularLinkedList
{
private class Node
{
private int candidate;
private Node next;
public Node()
{
candidate = 0;
next = null;
}
public Node(int newCandidate)
{
candidate = newCandidate;
next = null;
}
public Node(int newCandidate, Node nextValue)
{
candidate = newCandidate;
next = nextValue;
}
}//end inner class
private Node first;
private Node last;
public CircularLinkedList()
{
first = null;
last = null;
}
public boolean isEmpty() //checks to see if the list is empty
{
return first == null;
}
public int size() //checks the size
{
int count = 0;
Node p = first;
while(p != last)
{
count++;
p = p.next;
}
return count;
}
public void add(int e) //adds a Node to the list
{
Node newEntry = new Node(e, first);
if(first==null)
{
last = newEntry;
first = last;
}
else
{
last.next = newEntry;
last = last.next;
}
}
public void removeAfter(Node e) //removes the Node after the current Node
{
e.next = e.next.next;
}
public void remove() //removes every third Node
{
Node curNode = first;
int size = size();
while(size>1)
{
curNode = curNode.next;
removeAfter(curNode);
size -= 1;
}
}
public void print() //prints the list
{
Node ref = first;
for(int index = -1;index<size();index++)
{
System.out.print(ref.candidate + " ");
ref = ref.next;
}
}
}
And the main method...
import java.util.Scanner;
public class CircularDemo
{
public static void main(String[] args)
{
CircularLinkedList c = new CircularLinkedList();
System.out.println("How many candidates are there?");
Scanner keyboard = new Scanner(System.in);
int input = keyboard.nextInt();
if(input<=0)
System.out.println("No candidates presented.");
else if(input==1)
System.out.println("Candidate 1 is the only candidate and the winner.");
else
{
for(int i = 1; i<=input; i++)
{
c.add(i);
}
System.out.print("The candidates are: ");
c.print();
System.out.println("\n" + c.size()); //tests size
while(c.size()!=1)
{
c.remove();
c.print();
}
System.out.print("\nThe winner is: ");
c.print();
}
}
}
The main problem I'm having is the part where it tries to remove every 3rd Node in the main method (the while(c.size()!=1)). It'll print everything before this point correctly. Once it reaches this point, its like the program dies. If I take the while loop out, the winner part will print out, so something in the loop is messing up.
I think I know where the problem is. The first one is in the size() method. It prints one less than there really is. If I put 6, it thinks there are 5. Since this is a circular linked list, I can't just let it continue counting until it reaches a null. There will never be one. This is one issue, but I'm not sure how to fix it.
The second, I think is in the remove() and removeAfter() methods. I tried testing it out, but the program just ends when it tries to read it. I'm not really sure what's going on with these programs, and I had a difficult enough time trying to figure out how to create it... So this is the biggest issue.
Plus here's the output I've gotten so far, just to give you an idea:
How many candidates are there?
6 //user input
The candidates are: 1 2 3 4 5 6
5 //output for size()
1 2 6 //output first time through while loop
//output for winner still not showing up
edit 1 - updated while loop in delete. Output updated.
Upvotes: 0
Views: 1377
Answers (2)
Reputation: 141
Here's the gist of it, using an OOP approach and some input validation.
public class SuitorProblem
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int totalSuitors = 0;
boolean goodInput;
System.out.print("Enter the number of suitors: ");
//************************************ INPUT VALIDATION ***********************************************
do
{
try
{
totalSuitors = sc.nextInt();
while (totalSuitors <= 0)
{
System.out.print("Enter a positive integer value greater than 0: ");
totalSuitors = sc.nextInt();
}
goodInput = true;
}
catch (InputMismatchException e) // if not integer, prompt the user to go back
{
System.out.print("Enter a positive integer value greater than 0: ");
sc.nextLine(); // clear input
goodInput = false;
}
} while (!goodInput);
//********************************************************************************************************
ListOfSuitors suitorList = new ListOfSuitors();
for (int i = 1; i <= totalSuitors; i++)
suitorList.addEnd(i);
System.out.print("Before elimination process, the line-up of suitors is: ");
System.out.print(suitorList.toString());
System.out.println();
suitorList.deleteSuitors();
System.out.print("After elimination process, the winning suitor is: ");
System.out.print(suitorList.toString());
}
}
// I use an extension of CircularLinkedList of type Integer, so I can have access to the methods in CircularLinkedList to manipulate the ListOfSuitors, which is a LinkedList of ints.
class ListOfSuitors extends CircularLinkedList<Integer>
{
// default constructor
public ListOfSuitors()
{
}
// This method is used to find the next index that needs to be deleted
private int findIndexOfLoser(int element)
{
Node<Integer> current = head;
int index = 0;
while (current.element != element)
{
current = current.next;
index++;
}
return index;
}
// This method counts 3 spaces over then deletes a suitor by calling the delete method on the deletionIndex
public void deleteSuitors()
{
Node<Integer> current = head;
while (size != 1)
{
for (int i = 1; i < 3; i++)
{
current = current.next;
}
int deletionIndex = findIndexOfLoser(current.element);
current = current.next;
delete(deletionIndex);
}
}
}
// This is the generic circular linkedList that I extend my ListOfSuitors class from, and which holds the methods needed to manipulate the ListOfSuitors
class CircularLinkedList<E>
{
// since these will only be accessed by the subclass listOfSuitors, they are declared protected to increase security.
protected Node<E> head = null;
protected Node<E> tail = null;
protected int size;
public CircularLinkedList()
{
}
// method for adding a new end Node in circularLinkedList
public void addEnd(E element) // adapted from ch24 PowerPoint
{
if (size == 0)
{
head = tail = new Node<E>(element, head);
}
else
{
tail = tail.next = new Node<E>(element, head);
}
size++;
}
// Method for deleting a Node at a specified index in the circularLinkedList. May cause IndexOutOfBounds, so that must be handled within the method
public void delete(int index)
{
if (index < 0 || index > size - 1)
throw new IndexOutOfBoundsException("That's not a correct index.");
else if (index == 0)
deleteFirst();
else if (index == size - 1)
deleteEnd();
else
{
Node<E> previous = head;
Node<E> current = head.next;
for (int i = 1; i < index; i++)
{
previous = previous.next;
current = current.next;
}
previous.next = current.next;
current.next = null;
size--;
}
}
// method for deleting the end Node in circularLinkedList
public void deleteEnd()
{
if (size == 1)
{
head = tail;
tail.next = null;
} else if (size > 1)
{
Node<E> current = head;
while (current.next != tail)
current = current.next;
tail.next = null;
current.next = head;
tail = current;
}
size--;
}
// method for deleting the first Node in circularLinkedList
public void deleteFirst()
{
if (size == 1)
{
head = tail;
tail.next = null;
} else if (size > 1)
{
Node<E> current = head;
head = head.next;
current.next = null;
tail.next = head;
}
size--;
}
// In this method, I create my own toString in order to elegantly print the output of the suitorList in an efficient way, using StringBuilder.
public String toString()
{
Node<E> current = head;
StringBuilder suitorList = new StringBuilder();
if (size >= 1)
{
suitorList.append(current.element);
current = current.next;
}
for (int i = 1; i < size; i++)
{
suitorList.append(" ").append(current.element.toString());
current = current.next;
}
return suitorList.toString();
}
}
// this class is for the Node, which is what each int suitor is turned into when it is added to the ListOfSuitors
class Node<E>
{
protected E element = null;
protected Node<E> next = null;
// default constructor
public Node()
{
}
// overloaded constructor
public Node(E element, Node<E> next)
{
this.element = element;
this.next = next;
}
public Node(E element)
{
this.element = element;
}
public Node(Node<E> next)
{
this.next = next;
}
}
Upvotes: 0
Reputation: 199
Try assigning your last node to the first node, so that it becomes a circular linked list. (Assigning last.next=first in add())
Upvotes: 2
Related Questions
- Implementing Circular Linked List in java
- How to make a circular list in Java
- Circular linked list logic
- Java Circular Linked List
- Circular LinkedList implementation in Java
- Java Programming - Circular LinkedList
- Circular Doubly Linked List Program in Java (Homework Help)
- Circular Linked List in Java
- Help with a doubly linked circular list
- Need help with Circular Linked List in Java!