Thread: 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.

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.

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.

Which is line 47?

list.getBack().setForward(newNode);

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.

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)

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.

Thanks for your patience

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.