Issues with Linked List Add methods

[Kd Martin]

Hi all. I created a Linked List and a Node class and I'm having some errors with my append and prepend method. For some reason, Instead of getting the output "dog, cat, bird" I'm getting "dog, dog, cat" and tail.next points to bird rather than null. When I start with an empty list and add cat, the head, tail, and tail.next nodes are correct, but once I try to prepend dog, everything gets messed up. Could someone please help me figure out whats wrong with these methods? Thanks!
SLL<T> class

	//add to end of list
	public void append(T data) {
		if (isEmpty()) {//is it empty?
			prepend(data);
		}
		else {
			tail.next = new Node<T>(data); //add new node to end
			tail = tail.next; //point tail to this node
		}
	}

	//add to front of list
	public void prepend(T data) {
		if(isEmpty()) { //if newNode is the only node
			head = tail = new Node<T>(data);
			tail.next = null;
		}
		else {
			head = new Node<T>(data, head); 

		}
	}

Node<T>

public class Node<T> {
	public T data; //data stored
	public Node<T> next; //reference to next node

	public Node() {
		data = null;
		next = null;
	}

	public Node(T data) {
		this.data = data;
		next = null;
	}

	public Node(T data, Node<T> next) {
		this.data = data;
		this.next = next;
	}

	public String toString() {
		return " " + data;
	}
}
	

Driver

public class Driver {
	public static void main(String[] args) {

		SLL<String> list = new SLL<String>();
		
		System.out.println("***Add cat");
		list.append("cat");
		
		System.out.println("***Add dog to front");
		list.prepend("dog");
		
		System.out.println("***Add bird to end");
		list.append("bird");

		for(int i=0; i<list.size(); i++) {
			System.out.println((list.get(i)).toString());
		}

	}
}

[Anayonkar Shivalkar]

Hi Kd Martin,

Can you give the complete listing of class SLL?

Also, I think your prepend method is not proper. It is simply changing head to the new value, but what about the original list? Ideally, it should assign new head's tail to old head, and then assign new value to new head.

I hope this helps.

[Winston Gutkowski]

Kd Martin wrote:Could someone please help me figure out whats wrong with these methods?

As Anayonkar said, we really need to see the SLL code; however, one thing you might want to think about is adding an insert() method to your Node, viz:

final Node<T> insert(T data) {
   return (next = new Node(data, next));
}

which inserts a value between the current Node and the one following it (or after it, if it's the tail), returning the inserted Node. This allows you to insert a value anywhere you like in the SLL; not just at the beginning or end.
Note that I didn't make it public, because it's only likely to be used by the SLL; but there's nothing to stop you doing so if you want.

Also, you can use it to implement your append() method, viz:

public void append(T data) {
   if (isEmpty()) { //is it empty?
      prepend(data);
   } else {
      tail = tail.insert(data); //add new node to end
   }
}

I'd also suggest adding an addFirst(T data) method for adding the first Node to the list. It isn't absolutely required, but I think it'll make your code a bit clearer - the fact that the operation is very similar to a prepend() is an implementation detail.

Another thing: I see that your SLL has a size() method, but I don't see anywhere that you're updating it in your prepend/append methods. Now it may be that you're doing it somewhere else (again, code please), but they would seem to me to be the obvious place to do it.

Finally, you might consider making Node a static nested class, since it really only has any meaning to your SLL. It also allows you to make virtually everything, including its constructors, private, which increases security.

HIH

Winston