11 replies to this topic

[bloodchains]

I'm trying to make a circularly linked list where you have to delete every third node. Here's my code for a LinkedListNode class:

public class LinkedListNode
{
    public int info;
    public LinkedListNode link;
    public LinkedListNode head;

    public LinkedListNode()
    {
        info = 0;
        head = null;
        link = null;
    }

    public void insert(int item)
    {
        LinkedListNode newNode = new LinkedListNode();
    LinkedListNode current = head;
    if (isEmpty())
    {
            head = newNode;
            newNode.info = item;
            newNode.link = head;
    }
    else
    {
            while (current.link != head)
            {
                current = current.link;
            }
            current.link = newNode;
            newNode.info = item;
            newNode.link = head;
    }
    }
    
    public void remove(int item)
    {
        LinkedListNode current = head;
        
        while ((current.link != head) && (current.link.info != item))
        {
            current = current.link;
        }
        if (current.link == head)
            System.out.println(item + " is not in the list.");
        else
        {
            current.link = current.link.link;
            current = null;
        }
    }

    public boolean isEmpty()
    {
        return head == null;
    }

    public void printList()
    {
        LinkedListNode current = head;
        
        while (current.link != head)
        {
            System.out.print(current.info + " ");
            current = current.link;
        }
        
        System.out.print(current.info);
        System.out.println();
    }
    
    public int getSize()
    {
        int size = 0;
        LinkedListNode current = head;
        
        while (current.link != head)
        {
            current = current.link;
            size += 1;
        }
        
        if (current.info != 0)
            size += 1;
        
        return size;
    }
    
    public void removeThirdItem()
    {
        LinkedListNode thirdItem = head.link.link.link;
        LinkedListNode current = head.link.link;
        
        current.link = thirdItem.link;
        thirdItem = null;
    }
}

And this is my main program:

public class test
{
    public static void main(String[] args)
    {
        LinkedListNode list = new LinkedListNode();

        list.insert(5);
        list.insert(14);
    list.insert(7);
    list.insert(45);
        list.insert(21);
        
        System.out.println("Size of list: " + list.getSize());
        
        list.printList();
        
        list.removeThirdItem();
        list.printList();
        
        list.removeThirdItem();
        list.printList();
        
        list.removeThirdItem();
        list.printList();
    }
}

The problem is that when I try to remove a third item for the 3rd time, it just keeps printing the linked list, and I have to manually quit the program. Can anyone help me with this? Also, I need some way to remember the position of the node before the node to be removed, so that's were I start counting to another third node, and so on.

[fread]

Initially:

5 14 7 45 21

After run 1:

5 14 7 21

After run 2:

5 14 7

Which means you are deleting the fourth number which happens to be node three (counting from zero).

Also I prefer to not write:

node.link.link.link; 

I like to stretch things out, makes it easier to read:

public void removeThirdElement()
    {
        LinkedListNode current = null;
        LinkedListNode prev = null;
        LinkedListNode lead = head;

        for(int i = 0; i <= 3; i++) /* removing fourth node; modify as you so choose */
        {
            prev = current;
            current = lead;
            lead = lead.link;
        }
        prev.link = lead;
        if (lead.link == prev) head = lead; /* update head with the changes */
    }

[bloodchains]

fread said:

Initially:

5 14 7 45 21

After run 1:

5 14 7 21

After run 2:

5 14 7

Which means you are deleting the fourth number which happens to be node three (counting from zero).

Also I prefer to not write:

node.link.link.link; 

I like to stretch things out, makes it easier to read:

public void removeThirdElement()
    {
        LinkedListNode current = null;
        LinkedListNode prev = null;
        LinkedListNode lead = head;

        for(int i = 0; i <= 3; i++) /* removing fourth node; modify as you so choose */
        {
            prev = current;
            current = lead;
            lead = lead.link;
        }
        prev.link = lead;
        if (lead.link == prev) head = lead; /* update head with the changes */
    }

I'm not sure it's updating the head right. I added an output of the head:

public void removeThirdElement()
    {
        LinkedListNode current = null;
        LinkedListNode prev = null;
        LinkedListNode lead = head;

        for(int i = 0; i <= 3; i++) /* removing fourth node; modify as you so choose */
        {
            prev = current;
            current = lead;
            lead = lead.link;
        }
        prev.link = lead;
        
        if (lead.link == prev)
            head = lead; /* update head with the changes */
        
        System.out.println("head is " + head.info);
    }

The head is whatever the first node is.

[fread]

I'm not sure it's updating the head right. I added an output of the head

If this list is circular and and you intend to delete the third element when there is only two left: That is why i updated the head. Try to delete the third element in a circular list with only two elements and see what happens.
If you want the head to be whatever the first node is then you must not allow deletions when the size of the list is less than three.
This is the output after deleting the third element continuously until the loop has but one element.

Size of list: 8
5 14 7 45 21 1 6 2
5 14 45 21 1 6 2
5 14 21 1 6 2
5 14 1 6 2
5 14 6 2
5 14 2
5 14
14

As you can see the head is only updated on the when the list is less than three.

[bloodchains]

This is how I modified it:

public void removeThirdElement()
    {
        LinkedListNode current = null;
        LinkedListNode prev = null;
        LinkedListNode lead = head;

        if(isEmpty())
            System.out.println("The list is empty");
        else
        {
            for(int i = 0; i < 3; i++)
            {
                prev = current;
                current = lead;
                lead = lead.link;
            }
            System.out.print("removing " + current.info + ", head is now ");
            prev.link = lead;
            current = null;
            
            head = prev;
            System.out.println(head.info);
        }
    }

And this is my output:

Size of list: 6
5 14 7 45 21 60
removing 7, head is now 14
14 45 21 60 5
removing 21, head is now 45
45 60 5 14
removing 5, head is now 60
60 14 45
removing 45, head is now 14
14 60
removing 14, head is now 60
60

prev becomes head, and it readjusts the way it prints. It's fine now, I think I got what I want. What do you think?

[fread]

the statement:

prev.link = lead

skips the 'current' node.
Now why would you want to do this

head = prev;

Do you want to make the head the node before the head?

Should be more like:

public void removeThirdElement()
    {
        LinkedListNode current = null;
        LinkedListNode prev = null;
        LinkedListNode lead = head;

        for(int i = 0; i <= 2; i++) /* removing item in location 3 */
        {
            prev = current;
            current = lead;
            lead = lead.link;
        }
        System.out.print("removing " + current.info + ", head is now ");
        prev.link = lead;
        if (lead.link == prev) head = lead; /* rejoin to list */
        System.out.println(head.info);
    }

}

with output:

Size of list: 8
5 14 7 45 21 1 6 2
removing 7, head is now 5
5 14 45 21 1 6 2
removing 45, head is now 5
5 14 21 1 6 2
removing 21, head is now 5
5 14 1 6 2
removing 1, head is now 5
5 14 6 2
removing 6, head is now 5
5 14 2
removing 2, head is now 5
5 14
removing 5, head is now 14
14

[bloodchains]

Well I did that because I want to start counting at the node before the current. The reason is because I'm doing this problem:

Quote

According to legend, the 1st-century Jewish historian, Flavius Josephus, was captured along with a band of 40 compatriots by Roman soldiers during the Jewish-Roman war. The Jewish soldiers decided that they preferred suicide to being captured and devised a plan for their demise. They were to form a circle and kill every third soldier until they were all dead. Joseph and one other decided they wanted no part of this and quickly calculated where they needed to place themselves in the circle so that they would both survive. Write a program that allows you to place n people in a circle and specify that every mth person will be killed. The program should determine the number of the last person left in the circle. Use a circularly linked list to solve the problem.

See, if I did it the way you did, then those two would just position themselves in the first and second place, and that looks like it defeats the purpose of those guys forming a circle. What I think, if they were to form a circle, they would just pick a random guy from whom to start counting. So all they need to do is know who they're gonna start counting from, and then figure out where to position themselves. If that weren't the case, then they would just pick themselves as the first and second people to start counting from. You get what I'm saying? Hmm, maybe it'd be better if the head becomes the node after the one removed.

[fread]

Quote

...The program should determine the number of the last person left in the circle. Use a circularly linked list to solve the problem...

This directly implies that you are deleting every element save the last, whichever one that may be. Another thing: I was following your lead. You made separate calls to remove the third element which suggest you remove the third element in each new list that was created.
To delete every mth element you need to traverse the entire list continuously and delete each mth element before circling again. You should adjust remove() to remove every mth element from the list. Stop when number of elements in the list is equal to 1 or 2, whichever you decide to go with.

[bloodchains]

fread said:

This directly implies that you are deleting every element save the last, whichever one that may be. Another thing: I was following your lead. You made separate calls to remove the third element which suggest you remove the third element in each new list that was created.
To delete every mth element you need to traverse the entire list continuously and delete each mth element before circling again. You should adjust remove() to remove every mth element from the list. Stop when number of elements in the list is equal to 1 or 2, whichever you decide to go with.

Are you saying I'm not supposed to delete every mth element as I traverse?

Ok, I've edited it, but I'm getting an error now. It wouldn't stop looping.

public void removeEveryThirdElement()
    {
        LinkedListNode current = null;
        LinkedListNode prev = null;
        LinkedListNode lead = head;

        if(isEmpty())
            System.out.println("The list is empty");
        else
        {
            while (lead.link != head)
            {
                for(int i = 0; i < 3; i++)
                {
                    prev = current;
                    current = lead;
                    lead = lead.link;
                }
                System.out.print("killing " + current.info + ", we now start counting at ");
                prev.link = lead;
                current = null;

                System.out.println(lead.info);
            }
        }
    }

I think I did it right the first time. If I go with what you're saying, the first soldier will never get killed.

Edited by bloodchains, 27 November 2011 - 08:11 PM.

[fread]

I think you are either not clear on the problem or you not clear on the solution.
Taking it from the top with the question in mind. Suppose this is the contents of our initial list:

1 2 3 4 5 6 7 8 9 10

In a circular list the last node points to the first. Then the node containing 10 initially points to 1.

10 ----> 1

Lets say the mth element is the 3rd element. This is what we expect to happen:

1 2 4 5 7 8 10 ---> 3 6 and 9 was deleted. At this point you are looking at the node with value 10, which in this case is the last node which
points to the first node.

Count from the element with value 10. 10(one) wraps around to  1(second) then  2(third). Two must be deleted and so on....

1 4 5 8 10

4 5 10

4 10

4

In this situation if the soldier stands at position 4 he will survive. (In this case where you want two people to survive; they would stand at 4 and 10)

Another point: In this instance you have a start node and a tail node initially. Once you start deleting, there is no guarantee that, the start node will be in the list. And if it is deleted a new node must assume the head position.

This:

Quote

...The program should determine the number of the last person left in the circle. Use a circularly linked list to solve the problem...

implies you delete all nodes save the last.

Quote

Are you saying I'm not supposed to delete every mth element as I traverse?

Deleting the mth element is required.

The solution is a bit more intuitive. Here is the main:

public class test
{
    public static void main(String[] args)
    {
        LinkedListNode list = new LinkedListNode();
        int mthPosition = 3;
        int numSoldiers = 10;

        for(int i = 1; i <= numSoldiers; i++)
        {
            list.insert(i);
        }

        System.out.println("Size of list: " + list.getSize());
        list.removeMthElement(mthPosition);
        System.out.print("Last Man Standing is: ");
        list.printList();
        System.out.println();
    }
}

Here is a modified version of remove:

public void removeMthElement(int mthPosition)
    {
        LinkedListNode current = null;
        LinkedListNode prev = null;
        LinkedListNode lead = head;
        int count = 0;


        while (getSize() > 1)
        {
            count++;
            prev = current;
            current = lead;
            lead = lead.link;
            
            if(count == mthPosition)
            {
                 System.out.println("deleting " + current.info);
                 prev.link = lead; /* make a connection such that current is left out */
                 lead = prev;  /* we have deleted current node; start over from previous node */
                 if (current == head) head = lead; /* necessary to set some node as the head */
                 prev = null;
                 current = null;               
                 count = -1;    /* restart counting */
            }
        }
    }

Adjust mthPosition and numSoldiers in main and see if the last man standing is correct.

[bloodchains]

I used your code and got the same result as my final code:

public void removeEveryThirdElement()
    {
        LinkedListNode current = null;
        LinkedListNode prev = null;
        LinkedListNode lead = head;

        if(isEmpty())
            System.out.println("The list is empty");
        else
        {
            for(int i = 0; i < 3; i++)
            {
                prev = current;
                current = lead;
                lead = lead.link;
            }
            System.out.print("killing " + current.info + ", we now start counting at ");
            prev.link = lead;
            current = null;
            head = lead;

            System.out.println(lead.info);
        }
    }

And this is the main, which has both our codes, commented out so you can select which code to use. Oh, and I changed the list to String and replaced them with Soldier1, Soldier2, etc.

public class test
{
    public static void main(String[] args)
    {
        LinkedListNode list = new LinkedListNode();

        for (int i = 1; i <= 41; i++)
        {
            String s  = Integer.toString(i);
            list.insert("Soldier" + s);
        }
        
        System.out.println("Starting size of list: " + list.getSize());
        System.out.print("Initial list: ");
        list.printList();
        
        String[] l = list.nameList();

        // This is where I have to use my code.
       /* int size = list.getSize();
        
        while (size > 2)
        {
            list.removeEveryThirdElement();
            list.printList();
            size = list.getSize();
            System.out.println("Soldiers remaining: " + size);
        } */
        
       // list.removeMthElement(3); This is your code.
        
        if (list.getSize() == 2)
        {
            String[] survivors = list.namesOfSurvivors();
            int pos1 = 0, pos2 = 0;

            for (int i = 0; i < l.length; i++)
            {
            if (survivors[0].equals(l[i]))
                pos1 = i + 1;
            if (survivors[1].equals(l[i]))
                pos2 = i + 1;
            }

            System.out.printf("The two survivors are %s and %s.\n", survivors[0], survivors[1]);
            System.out.printf("Their positions are %d and %d.\n", pos1, pos2);
        }
    }
}

[fread]

removeEveryThirdElement() is no longer applicable. This was before the problem was explained. Check the previous post for a main() and a remove() method.