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!
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.
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: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: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.
Bats fly at night, 'cause they aren't we. And if we tried, we'd hit a tree -- Ogden Nash (or should've been).
Articles by Winston can be found here