Results 1 to 10 of 10
Like Tree1Likes
  • 1 Post By shyronnie

Thread: Basic Circular Linked List - addFirst() method works improperly

  1. #1
    carlodelmundo is offline Member
    Join Date
    Aug 2008
    Posts
    31
    Rep Power
    0

    Default 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:

    Java 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):

    Java 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.
    Last edited by carlodelmundo; 11-23-2008 at 07:48 AM.

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default

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

    Java Code:
          Node current = tail;
          while (current != tail)
          {
            //...  will this code ever be reached?
          }
    Notice anything wrong here?

  3. #3
    carlodelmundo is offline Member
    Join Date
    Aug 2008
    Posts
    31
    Rep Power
    0

    Default

    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:

    Java 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!

  4. #4
    carlodelmundo is offline Member
    Join Date
    Aug 2008
    Posts
    31
    Rep Power
    0

    Default

    I have finally found my error.

    For future reference:

    Here's the revised addLast() method.

    Java 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:

    Java 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:

    Java 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.

  5. #5
    carlodelmundo is offline Member
    Join Date
    Aug 2008
    Posts
    31
    Rep Power
    0

    Default

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

    Java 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;
    	}
    	
    }
    Java 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;
    		}
    	}
    	
    }
    Java 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.

  6. #6
    shyronnie is offline Member
    Join Date
    Nov 2011
    Posts
    3
    Rep Power
    0

    Default Re: Basic Circular Linked List - addFirst() method works improperly

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

    Java 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.

  7. #7
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default Re: Basic Circular Linked List - addFirst() method works improperly

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

  8. #8
    shyronnie is offline Member
    Join Date
    Nov 2011
    Posts
    3
    Rep Power
    0

    Default Re: Basic Circular Linked List - addFirst() method works improperly

    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?

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

  9. #9
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,315
    Blog Entries
    1
    Rep Power
    26

    Default Re: Basic Circular Linked List - addFirst() method works improperly

    Quote Originally Posted by shyronnie View Post
    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?

    Java 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?

  10. #10
    shyronnie is offline Member
    Join Date
    Nov 2011
    Posts
    3
    Rep Power
    0

    Default Re: Basic Circular Linked List - addFirst() method works improperly

    Quote Originally Posted by Fubarable View Post
    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.
    Fubarable likes this.

Similar Threads

  1. Circular Double Linked List
    By theonly in forum Advanced Java
    Replies: 3
    Last Post: 12-06-2009, 06:10 PM
  2. Linked List Manipulation
    By chrisdb89 in forum New To Java
    Replies: 3
    Last Post: 11-21-2008, 07:07 PM
  3. Linked List help
    By neobie in forum New To Java
    Replies: 8
    Last Post: 12-22-2007, 04:15 AM
  4. Linked List
    By rnavarro9 in forum New To Java
    Replies: 0
    Last Post: 11-29-2007, 04:42 AM
  5. Help with linked list
    By trill in forum New To Java
    Replies: 1
    Last Post: 08-07-2007, 08:29 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •