Can You Help Me Debug My Java LinkedList Stack Implementation?

[grouchy]

Hi, i need to use a list class (provided and complete) and then use a Linkedlist class (need to add the methods) to get a stack going. I am having trouble with my remove from head method although I ain't too sure if my addHead method is right... I'd appreciate it if someone could look over my code and give me some pointers. I wrote in bold and caps where I aint sure. thx.

class Link
{
public Object data;
public Link next;
public Link(Object d, Link n)
{
data = d; next = n;
}
}



//LINKEDLIST CLASS AND MAIN
import java.util.Scanner;

class LinkList
{
private Link head; // reference to first Link

private Link tail; // reference to last Link

private int size;

public LinkList()
{

tail = null;
head = null;

}

public Object peekHead() // return reference to first Object
{
return head.data;
}

public Object peekTail() // return reference to last Object
{
return tail.data;
}

//THE ADD METHOD, NOT SURE IF DONE RIGHT
public void addHead(Object newData)
{
if (head == null)
{
head = new Link(newData, tail);


}

else if (head != null && tail == null)
{
tail = head;
head = new Link (newData, tail);
}
else
{

head.next = head;
head = new Link (newData, head.next);

}
}

public void addTail(Object newData)
{

}

//THE REMOVE METHOD
public Object removeHead()
{
Link removing = head;
if (head != null)
{
head = head.next;
}

return removing.data;

}

//MAIN METHOD
public static void main (String[] args)
{
Scanner scan = new Scanner(System.in);

int choice = 0;

LinkList first = new LinkList();

while (choice != 6)
{

System.out.println("What would you like to do? (enter the number)");
System.out.println("1 - Push onto Head of Stack.");
System.out.println("2 - Remove from Head of Stack.");
System.out.println("3 - Peek at Head of Stack.");
System.out.println("4 - Push at Tail of Stack.");
System.out.println("5 - Peak at Tail of Stack.");
System.out.println("6 - Close Program.");
choice = scan.nextInt();


switch(choice)
{
case 1:
System.out.println("What do you want to push on Head?");
Object pushingHead = scan.next();

first.addHead(pushingHead);
break;

case 2:
System.out.println("Removing: " + first.removeHead());
break;

case 3:
System.out.println("Peeking at Head of Stack: " + first.peekHead());
break;

case 4:
System.out.println("What do you want to push on Tail?");
Object pushingTail = scan.next();

first.addHead(pushingTail);
break;

case 5:
System.out.println("Peeking at Tail of Stack: " + first.peekTail());
break;

case 6:
System.out.println("Good Bye!");
break;
}


}

}
}

 

[Coin]

Hmm...

Your removehead method looks generally right, but one question. Think about what happens when you remove the VERY LAST object in the whole linked list. What happens to "tail"?

Your addhead on the other hand contains a lot of problems. I'm just going to write in some comments noting the problems I see, let me know if I'm not clear enough:

public void addHead(Object newData)
{
if (head == null)
{
head = new Link(newData, tail); // If head is null, then won't tail also be null?
}

else if (head != null && tail == null) // It should never be possible for this case to be true. Head is supposed to be the first item of the list. Tail is supposed to be the last item of the list. If either head or tail is null, ever, then that implies the list is empty.
{
tail = head; // In other words, you just set the end of the list to be the new start of the list. Why?
head = new Link (newData, tail); // As required by the "if" statement above, tail is currently null. Is this what you want?
}

else
{
head.next = head; // Think about this: You are setting "the item after A" to be equal to "A". You just turned head into a very small linked list pointing to itself.
head = new Link (newData, head.next); // "Set the new head to be a Link object containing newData, and followed by the item AFTER the current head". Is this what you want?

}
}

I think you need to be more careful in general about thinking: What should head be pointing to? What should tail be pointing to? If at any given moment I start with the object pointed to by "head" and step forward until I hit null, which objects will I see on the way if the list is working properly?

One more thing: why *are* you keeping track of a tail pointer? Usually "tail" is something people use in conjunction with a doubly-linked list. Your list is singly-linked. And if you intend to use this linked list only as a stack, then there is no reason whatsoever to keep track of the tail.

 

[grouchy]

ok, i think I know what you mean. Also, about the tail pointer, I am supposed to have it reference my last object on the stack.

I tried to change somethings around to make more sense. The problem, for example if I addHead A, then B, then C, then D. When I go to remove,the first time it removes D, but the second attempt (and third, and fourth, etc) it just tells me its removing C but doesn't actually do it. I also tried to finishish addTail and it just adds to the front... so I need to keep working on that one.

Thx for the tips btw.

here is the updated code...


public void addHead(Object newData)
{
if (head == null && tail == null)
{
head = new Link(newData, tail);
tail = head;


}

else if (head != null && tail != null)
{
head.next = head;
head = new Link (newData, head.next);

if(head.next == null)
{
tail = head;
}
}
}

public void addTail(Object newData)
{
Link current;
if (head == null && tail == null)
{
head = new Link(newData, tail);
tail = head;
}
else
{
while (head != null)
{
head = head.next;
}
head = new Link(newData, tail);
tail = head;
}
}

public Object removeHead()
{
Link removing = head;
if (head != null)
{
head = head.next;
if(head.next == null)
{
tail = head;
}

}

return removing.data;

 

[grouchy]

UPDATE: Ok, I think my addHead and removeHead methods work as intended. They seem to add and remove (thx for pointing out that tail would remain in the end). Only problem I'm having now is addTail. it always seems to add to the head. Here is the code.

public void addHead(Object newData)
{

if (head == null && tail == null)
{
head = new Link(newData, tail);
tail = head;

}

else
{
head = new Link(newData,head);
}
}

public void addTail(Object newData)
{
if (head == null && tail == null)
{
head = new Link(newData, tail);
tail = head;


}

else if (head != null && tail != null)
{
while(head != null)
head = head.next;
head = new Link(newData,head);
tail = head;
}
}

public Object removeHead()
{
{
Link removing = head;
if (head != null)
{
head = head.next;
}
if (head == null)
tail = null;

return removing.data;

}

}

 

[Coin]

Hi Grouchy,

A clause from your AddTail... consider what this code does:

else if (head != null && tail != null)
{
	while(head != null) // Until the head pointer becomes equal to null,
		head = head.next; // Set the head pointer equal to the next item in the list.
	head = new Link(newData,head); // Set the head pointer to a new node, followed by the head pointer (which, after your last two lines will always be...?) 
	tail = head; // Set the tail pointer to the head pointer
}