Basic Circular Linked List - addFirst() method works improperly

Hello everyone!

I've been working on Linked Lists for about 4 hours now, and I'm stuck on my Circular Linked List's addFirst() method. Basically, my output should be:

Michael
Hannah
Jacob

However, it only prints out the first name: Michael. It appears there is something wrong that happens when I add a second Node (perhaps the Links aren't properly connected?) I believe there is something wrong with my logic in creating the addFirst() method. I have three total classes: Node, CircularLinkedList, and CircularLinkedListTest.

Below is the code for my addFirst() method in my CircularLinkedList class:

Code:

---

        public void addFirst(Object o)
        {
                if (isEmpty())
                {
                        tail = new Node(o, tail);
                }
                else // This is the part that's messing up.
                {
                        Node current = new Node(o, tail.getNextNode());
// Creates a reference variable "current" which points
//to a new Node where parameter 'o' is an object, and
//tail.getNextNode() is a pointer (to the next Node object)

                        tail.setNextNode(current);
// Once the tail has established a link to the "tail"
//node's pointer, the nextNode of the "tail" is pointed
//to the Node that is being/referenced by "current"
                }
        }

---

Below is part of my Tester Class (the main() method portion):

Code:

---

public static void main(String[] args) {
                // TODO Auto-generated method stub
                CircularLinkedList cll = new CircularLinkedList();
               
                cll.addFirst("Michael");
                cll.addFirst("Hannah");
                cll.addFirst("Jacob");
               
                System.out.println(cll);
               
       
        }

---

All of the three classes that I've written that may help you even further can be found at: carlodm[dot]com/cll/

Thank you for any help that you can give me.

Have a close look at a portion of your CircularLinkedList class's toString method:

Code:

---

      Node current = tail;
      while (current != tail)
      {
        //...  will this code ever be reached?
      }

---

Notice anything wrong here?

Ah I see. The while loop does not even execute once since current is equal to tail!

I edited my code to reflect the following:

Code:

---

Node current = tail.getNextNode();
                        while (current != tail)
                        {
                                ...
                        }

---

So that the pointer 'current' will be at the first Node of the list (compared to being at the 'tail' or the last).

However, it gives me a java.lang.NullPointerException (the tail's pointer is void? that doesn't make sense though).

Thanks for your help so far Fubarable!

I have finally found my error.

For future reference:

Here's the revised addLast() method.

Code:

---

public void addLast(Object o)
        {
                if (isEmpty())
                {
                        tail = new Node(o, tail);
                        tail.setNextNode(tail);
                }
                else
                {
                Node current = new Node(o, tail.getNextNode());
                tail.setNextNode(current);
                tail = current;
                }
        }

---

The error(s) in the previous code hovered around this next statement:

Code:

---

tail = new Node(o, tail);

---

It makes sense for the first node to be created to point to itself(first, create a node that has object 'o' and its pointer will point to the existing tail. now, make this node the new tail.)

For some reason, Java doesn't just like that. You have to add this next statement:

Code:

---

tail.setNextNode(tail);

---

We have to explicitly tell java, that "Hey, Java, I want the tail Node that tail's being referenced to, to set the nextNode as itself.

FOR FUTURE REFERENCE FOR THOSE WHO NEED THE SOLUTIONS TO THE JOSEPHUS PROBLEM:

Code:

---

public class Node {
        private Object myValue;
        private Node myNextNode;
               
        public Node(Object aValue, Node aNextNode)
        {
                this.myValue = aValue;
                this.myNextNode = aNextNode;
        }
       
        public Object getValue()
        {
                return myValue;
        }
       
        public Node getNextNode()
        {
                return this.myNextNode;
        }
       
        public void setValue(Object aValue)
        {
                this.myValue = aValue;
        }
       
        public void setNextNode(Node aNextNode)
        {
                this.myNextNode = aNextNode;
        }
       
}

---

Code:

---

public class CircularLinkedList {

        private Node tail;
       
        public CircularLinkedList()
        {
                tail = null;
        }
       
        public boolean isEmpty()
        {
                return tail == null;
        }
       
        public Node getLast()
        {
                return tail;
        }
       
        public void setLastNode(Node aNode)
        {
                this.tail = aNode;
        }
       
        public void addFirst(Object o)
        {
                if (isEmpty())
                {
                        tail = new Node(o, tail);
                        tail.setNextNode(tail);
                        System.out.println("The tail Node has a String object named " + o + " and it points to " + tail.getNextNode().getValue());
                }
                else
                {
                        Node current = new Node(o, tail.getNextNode());
                        tail.setNextNode(current);
                        System.out.println("The Node just added contained the object: " + o);
                        System.out.println("The Node with object " + o + " points to the node named: " + current.getNextNode().getValue());
                }
        }
       
        public void addLast(Object o)
        {
                if (isEmpty())
                {
                        tail = new Node(o, tail);
                        tail.setNextNode(tail);
                }
                else
                {
                Node current = new Node(o, tail.getNextNode());
                tail.setNextNode(current);
                tail = current;
                }
        }
       
        public void removeLast()
        {
                Node current = tail;
               
                while (current.getNextNode() != tail)
                {
                        current = current.getNextNode();
                        current.setNextNode(tail.getNextNode());
                }
        }

        //Precondition - n != 1 <-- this would be pointless if it was.
        public void removeByPosition(int n)
        {
                Node current = tail;
               
                while (current.getNextNode() != tail)
                {
                        for (int i = 1; i < n; i++)
                        {
                                current = current.getNextNode();
                        }
                        current.setNextNode(current.getNextNode().getNextNode());
                        System.out.println("The person at position " + n + " is now removed.");
                       
                }
        }
       
        public void removeByIteration(int n)
        {
                Node current = tail;
                               
                while (current.getNextNode() != current)
                {
                        for (int i = 1; i < n; i++)
                        {
                                current = current.getNextNode();
                        }
                       
                        if (current.getNextNode() == tail)
                        {
                                Node twoNodesFromNow = current.getNextNode().getNextNode();
                                current.setNextNode(twoNodesFromNow);
                                tail = current;
                                printList();
                        }
                        else
                        {
                                Node twoNodesFromNow = current.getNextNode().getNextNode();
                                current.setNextNode(twoNodesFromNow);
                                printList();
                        }               
                }
        }
       
        public void printList()
        {
                System.out.println(this);
        }
       
        public String toString()
        {
                if (isEmpty())
                {
                        return "The list is empty.";
                }
                else
                {
                        String s = "";
                        Node current = tail.getNextNode();
                        while (current != tail)
                        {
                                s += current.getValue() + " ";
                                current = current.getNextNode();
                        }
                        s += current.getValue();
                return s;
                }
        }
       
}

---

Code:

---

import java.util.*;

public class CircularLinkedListTest {
       
        static Scanner sc = new Scanner(System.in);
                public static void main(String[] args) {
                // TODO Auto-generated method stub
               
               
                int numTotalNames, theN;
                boolean userEscape = false;
                String response1 = "";
               
                do
                {
                CircularLinkedList cll = new CircularLinkedList();
                       
                System.out.println("Enter the number of names: ");
                numTotalNames = sc.nextInt();
               
                for (int i = 1; i <=numTotalNames; i++)
                {
                        cll.addLast(i + "");
                }               
               
                System.out.println("Enter the N: ");
                theN = sc.nextInt();
                cll.removeByIteration(theN);
               
                System.out.println("Continue? Y/N");
                response1 = sc.next();
               
                if (response1.equalsIgnoreCase("N"))
                        userEscape = true;

                }
                while (userEscape != true);
        }
}

---

See Josephus problem - Wikipedia, the free encyclopedia to read about this interesting topic.

I have a question with your code, carlo. Is it really necessary to use the "this" keyword on the Node class?

Code:

---

public class Node {
    private Object myValue;
    private Node myNextNode;
       
    public Node(Object aValue, Node aNextNode)
    {
        this.myValue = aValue;
        this.myNextNode = aNextNode;
    }
   
    public Object getValue()
    {
        return myValue;
    }
   
    public Node getNextNode()
    {
        return this.myNextNode;
    }
   
    public void setValue(Object aValue)
    {
        this.myValue = aValue;
    }
   
    public void setNextNode(Node aNextNode)
    {
        this.myNextNode = aNextNode;
    }
   
}

---

What's gonna happen if we don't use "this"? I'm still trying to get my head wrapped around this whole node stuff.

I'm not the original poster but I can say that in this situation, it is not necessary to use "this".

I see, thanks. I had a feeling all those "this" keywords are unnecessary. But the way it's written, I think we still have to use it in the constructor, right?

Code:

---

    public Node(Object aValue, Node aNextNode)
    {
        this.myValue = aValue;
        this.myNextNode = aNextNode;
    }

---

Quote:

---

Originally Posted by shyronnie

I see, thanks. I had a feeling all those "this" keywords are unnecessary. But the way it's written, I think we still have to use it in the constructor, right?

Code:

---

    public Node(Object aValue, Node aNextNode)
    {
        this.myValue = aValue;
        this.myNextNode = aNextNode;
    }

---

---

Try it with and without and you'll see that in this instance, "this" is not needed. Can you figure out and tell us why it's not needed here?

Quote:

---

Originally Posted by Fubarable

Try it with and without and you'll see that in this instance, "this" is not needed. Can you figure out and tell us why it's not needed here?

---

Ah yes, you're right. I didn't notice that the values passed in the constructor have different names. I was thinking of my own code, and I made it so the values passed on the constructor have the same name as the instance variables. But you're right, "this" is not needed in carlo's constructor.