Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 10 of 10

Thread: trouble with add and remove method on doubly linked list

  1. #1
    Junior Member
    Join Date
    Jul 2012
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default trouble with add and remove method on doubly linked list

    Hello,

    I'm new to this forum so I apologize for any mistakes I'm going to make, I'm still learning the ropes. I am writing a token ring simulation program and am using a circular doubly linked list in the process. I seem to be having issues with the add and remove methods however.

    My TokenRingList class:
    import support.DLLNode;
     
    /**
     * A specialized circular doubly linked list for a token ring simulation. 
     */
    public class TokenRingList implements TokenRingListInterface {
    	// The start of the token ring list:
    	private DLLNode<Workstation> list;
    	// The location used to search this list:
    	private DLLNode<Workstation> location;
    	// The size of this list:
    	private int size;
    	// clockwise/counterclockwise - true if clockwise, false if counterclockwise:
    	private boolean clockwise = true;
     
    	/**
    	 * Creates a new TokenRingList object.
    	 */
    	public TokenRingList() {
    		list     = null;
    		location = null;
    	}
     
    	/**
    	 * Returns the size of the token ring.
    	 */
    	public int size() {
    		return size;
    	}
     
    	/**
    	 * Adds a Workstation object to this token ring.
    	 */
    	public void add(Workstation element) {
    		DLLNode<Workstation> newNode = new DLLNode<Workstation>(element);
    		if(list==null)
    		{
    			list = newNode;
    			newNode.setForward(list);
    		}
    		else
    		{
    			newNode.setBack(location.getBack());
    			newNode.setForward(location);
    			location.getBack().setForward(newNode);
    			location.setBack(newNode);
    		}
    	}
     
    	/**
    	 * Removes a Workstation object from this token ring.
    	 */
    	public boolean remove(Workstation element) {
    		DLLNode<Workstation> newNode = new DLLNode<Workstation>(element);
    		boolean test = false;
    		if (contains(element))
    		{
    			newNode.getBack().setForward(newNode.getForward());
    			newNode.getForward().setBack(newNode.getBack());
    			test = true;
    		}
    		else
    		  test = false;	
    		size--;
    		return test;
    	}
     
     
    	/**
    	 * Returns true if this token ring has the workstation; false otherwise.
    	 */
    	public boolean contains(Workstation element) {
    		// Is the list empty?
    		if (list == null)
    			return false;
     
    		// Find the element if it exists:
    		DLLNode<Workstation> t = list;
    		do {
    			if (element == t.getInfo())
    				return true;
    			t = t.getForward();
    		} while (t != list);
     
    		// Not found:
    		return false;
    	}
     
    	/**
    	 * Returns the workstation if it is in this token ring; null otherwise.
    	 */
    	public Workstation get(Workstation element) {
    		// Is the list empty?
    		if (list == null)
    			return null;
     
    		// Find the element if it exists:
    		DLLNode<Workstation> t = list;
    		do {
    			if (element == t.getInfo())
    				return element;			
    			t = t.getForward();
    		} while (t != list);
     
    		// Not found:
    		return null;
    	}
     
    	public void reset() {
    		location = list;
    	}
     
    	/**
    	 * Returns the next workstation in the token ring.
    	 */
    	public Workstation getNext() {
    		if (clockwise) {
    			return getClockwise(); 
    		}
    		else {
    			return getCounterClockwise();
    		}
    	}
     
    	/**
    	 * Returns the current workstation and advances location clockwise. 
    	 */
    	private Workstation getClockwise() {
    		DLLNode<Workstation> t = location;
    		location = location.getForward();
    		return t.getInfo();
    	}
     
    	/**
    	 * Returns the current workstation and advances location counterclockwise. 
    	 */
    	private Workstation getCounterClockwise() {
    		DLLNode<Workstation> t = location;
    		location = location.getBack();
    		return t.getInfo();
    	}
     
    	/**
    	 * Sets the token ring to retrieve workstations in a clockwise fashion.
    	 */
    	public void setClockwise() {
    		clockwise = true;
    	}
     
    	/**
    	 * Sets the token ring to retrieve workstations in a counterclockwise fashion.
    	 */
    	public void setCounterClockwise() {
    		clockwise = false;
    	}
     
    }

    this is the DLLNode class I'm using
     
    public class DLLNode<T> {
    	private DLLNode<T> back;
    	private DLLNode<T> forward;
    	private T info;
     
    	public DLLNode(T info) {
    		this.info = info;
    		this.back = null;
    		this.forward = null;
    	}
     
    	public void setInfo(T info)
    	// Sets info of this LLNode.
    	{
    		this.info = info;
    	}
     
    	public T getInfo()
    	// Returns info of this LLONode.
    	{
    		return info;
    	}
     
    	public void setBack(DLLNode<T> back)
    	// Sets back link of this DLLNode.
    	{
    		this.back = back;
    	}
     
    	public DLLNode<T> getBack()
    	// Returns back link of this DLLNode.
    	{
    		return back;
    	}
     
    	public void setForward(DLLNode<T> forward)
    	// Sets forward link of this DLLNode;
    	{
    		this.forward = forward;
    	}
     
    	public DLLNode<T> getForward()
    	// Returns forward link of this DLLNode.
    	{
    		return forward;
    	}
    }

    Any advice or pointers would be great. Thank you.


  2. #2
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: trouble with add and remove method on doubly linked list

    As your posted code is, lets call it lengthy-for-a-forum-post, it would be most helpful to the forum peoples if you post more specific details about the error. Few have the time to take your code on as a project and figure out what is broken, then how to fix it. Any hints you can provide about the problem, error messages, and a smaller chunk of code that demonstrates the problem if possible.

  3. #3
    Junior Member
    Join Date
    Jul 2012
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: trouble with add and remove method on doubly linked list

    Thanks for the advice

    The error message I am receiving is:
    Exception in thread "main" java.lang.NullPointerException
    	at cs187.asn03.TokenRingList.add(TokenRingList.java:47)
    	at cs187.asn03.TokenRingList.add(TokenRingList.java:1)
    	at cs187.asn03.TokenRingSimulator.main(TokenRingSimulator.java:89)

    the method that is the source of the error is my add method:
    public void add(Workstation element) {
    		DLLNode<Workstation> newNode = new DLLNode<Workstation>(element);
    		if(list==null)
    		{
    			list = newNode;
    			newNode.setForward(list);
    		}
    		else
    		{
    			newNode.setBack(list.getBack());
    			newNode.setForward(list);
    			list.getBack().setForward(newNode);
    			list.setBack(newNode);
    		}
    	}

    I am attempting to add and element to a doubly linked list.

  4. #4
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

    Default Re: trouble with add and remove method on doubly linked list

    Which is line 47?

  5. #5
    Junior Member
    Join Date
    Jul 2012
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: trouble with add and remove method on doubly linked list

    list.getBack().setForward(newNode);

  6. #6
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

    Default Re: trouble with add and remove method on doubly linked list

    You get a NullPointerException when you use an expression as if it had a non null value when it is really null. A common example of this is calling a method like "foo.bar()" when foo is null. (Arrays provide another occasion for error: "arr[0]" when arr is null).

    The first thing to do is to figure out what expression is null. We can rule out list because of the if statement. So it looks very much as if list.getBack() is null. You can check that with:

    System.out.println("About to set list's links, list.getBack()=" + list.getBack());
    list.getBack().setForward(newNode);

    If it turns out that list.getBack() is null then you have two things to consider (1) list.getBack() should really not be null. In that case you will have to go back through your code to where you thought you had assigned it a non null value and figure out why that didn;t happen. Or (2) It is quite possible for list not to be null but list.getBack() to be null. In that case you have another state of affairs that has to be handled slightly differently within the else block.

  7. #7
    Junior Member
    Join Date
    Jul 2012
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: trouble with add and remove method on doubly linked list

    Thank you for the advice

    However, if I treat the insertion like a would if I was adding the element to the end of the list the code runs through once.

    public void add(Workstation element)  {
    		DLLNode<Workstation> newNode = new DLLNode<Workstation>(element);
            if(list == null)
            {
            	list = newNode;
            }
            else if(list.getBack() == null)	
            {
            	newNode.setForward(list);
            	list = newNode;
            }
            else
            {
            	newNode.setBack(list.getBack());
            	newNode.setForward(list);
            	list.getBack().setForward(newNode);
            	list.setBack(newNode);
     
            }
            location = list;
            size++;
        }

    I receive an error though later on in the code when the getBack() method is called again.

    private Workstation getCounterClockwise() {
    		DLLNode<Workstation> t = location;
    		location = location.getBack();
    		return t.getInfo();
    	}

    The error now is:
    Exception in thread "main" java.lang.NullPointerException
    	at cs187.asn03.TokenRingList.getCounterClockwise(TokenRingList.java:150)
    	at cs187.asn03.TokenRingList.getNext(TokenRingList.java:132)
    	at cs187.asn03.TokenRingList.getNext(TokenRingList.java:1)
    	at cs187.asn03.TokenRingSimulator.main(TokenRingSimulator.java:140)

  8. #8
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    987
    Thanks
    6
    Thanked 206 Times in 182 Posts

    Default Re: trouble with add and remove method on doubly linked list

    if I treat the insertion like a would if I was adding the element to the end of the list...
    Doesn't that code add the new node to the start? Perhaps you should test the add() method to make sure it is doing exactly what you intend. It might be a good idea to write a small method that starts at list and follows getForward() printing the node info until it gets to the end. That way you can tell that the node is getting added, and is being added exactly where you intend.

    The error now is:
    Avoid the temptation to have your code writing driven by the main() method and the runtime errors it (inevitably!) throws at you. Instead check each method as you write it. As indicated above have a method that "dumps" the ring's data, then write a small main() method that adds a few things, dumping the ring's data each time so you can check that everything is going OK.

    In any case, another NullPointerException. And the story is the same... I'm guessing the problem is with t.getInfo() (you should say). It would appear that you are calling this method when location is at the start of the ring. So location.getBack() is null. And calling getInfo() on it throws the NullPointerException.

  9. #9
    Junior Member
    Join Date
    Jul 2012
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: trouble with add and remove method on doubly linked list

    Thanks for your patience

  10. #10
    Junior Member
    Join Date
    Jul 2012
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: trouble with add and remove method on doubly linked list

    Okay so I'm trying to add an element to the start of a circular doubly-linked list and I am not sure how I am suppose to go about writing this method. Any advice or direction would be greatly appreciated, the code I am using is the same as above basically.

Similar Threads

  1. trouble with add and remove method on doubly linked list
    By BetterCallSaul in forum What's Wrong With My Code?
    Replies: 1
    Last Post: July 20th, 2012, 02:51 PM
  2. From Doubly to Single linked list
    By Spamik in forum Collections and Generics
    Replies: 2
    Last Post: May 4th, 2011, 05:41 AM
  3. Sorting a doubly linked list
    By snufkin in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 26th, 2010, 12:01 PM
  4. Sorted Doubly linked List
    By student in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 15th, 2010, 09:52 PM
  5. ClassCastException in Double Linked List toString
    By Rastabot in forum Collections and Generics
    Replies: 2
    Last Post: April 24th, 2009, 11:48 AM

Tags for this Thread