Stack Implementation for Nodes containing Objects

Question

I have a LinkedList of Nodes that contain Integer Objects.

LinkedList listOfInts = new LinkedList();

And I add the Objects;

list.add(new Integer(8));
list.add(new Integer(5));
list.add(new Integer(3));
list.add(new Integer(4));

with the following Node class:

class Node {

 private Object data;
 private Node next;

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

 public Object getData() 
 {
   return data;
 }

 public Node getNext() 
 {
   return next;
 }

 public void setNext(Node next) 
 {
   this.next = next;
 }
}

If I do something as such;

Node p = listOfInts.pop()

And then print the data,

System.out.println(p.getData());

I get the right answer: 8.

But if I want to push this number onto a new LinkedList;

LinkedList newStack = new LinkedList();
newStack.push(p);

It pushes the entire listOfInts, not just the first data point, 8.

 [8,5,3,4];

My question is why this happens? Since this is such a basic problem, I assume it has to do with my push() and pop() methods, but since I wrote them similar to ones I've seen in textbooks, I don't know what's wrong with them. Could anyone help me understand?

public Node pop()
{
  Node item = peek(); //save item to return

  if(!isEmpty())
  {
    first = first.getNext(); //delete first node
  }
  size--;
  return item; //return first saved item
}

public void push(Node item)
{
  Node next = item.getNext();
  next = first;
  first = item;
  size++;

}

public Node peek()
{
  if (isEmpty())
  {
    System.out.println("Error: No element");
  }
  return first;
}

EDIT: Did as suggested with returning Objects instead of Nodes, and code is more or less the same except for push() method. So, when I try to add another object to the same LinkedList, it replaces the old one instead of adding to the list.

 //push node on top of the stack
 public void push(Object item)
 {

   Node newNode = new Node(item);
   Node next = newNode.getNext();
   next = first;
   first = newNode;

   size++;
  }//push

rgettman · Accepted Answer · 2015-07-30 20:29:34Z

4

Your implementation is returning the Node object when pop is called, but the Node still has a reference to the "next" position within the original stack.

When you create a new stack, and you push the popped item, the original Node object is along for the ride, with its original next reference.

listOfInts -----> { 5 } -> { 3 } -> { 4 }
                    ^
newStack  -> { 8 } -+

That is why the whole list appears on the new stack.

The solution is not to expose the Node object at all. Instead of accepting a Node in push, accept the data item, and create your own Node. Instead of returning a Node in pop and peek, extract the data item from the Node and return it. This way you don't inadvertently risk leaking the reference to the next Node in the desired node.

answered Jul 30, 2015 at 20:29

rgettman

179k30 gold badges282 silver badges365 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

kris Over a year ago

Thank-you for your suggestion! That makes a lot more sense. If I could ask another question though, I edited my push() method, but as I stated above, it seems to be over-writing the previous Objects when I add new Objects to the same LinkedList instead of forming a list. Any suggestions on how to fix this?

Collectives™ on Stack Overflow

Stack Implementation for Nodes containing Objects

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related