java - 包含对象的节点的堆栈实现

Question

我有一个 LinkedList 的 Nodes 包含整数对象。

LinkedList listOfInts = new LinkedList();

然后我添加对象；

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

使用以下 Node 类:

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;
 }
}

如果我这样做；

Node p = listOfInts.pop()

然后打印数据，

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

我得到正确答案:8。

但是如果我想把这个数字推到一个新的 LinkedList;

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

它推送整个 listOfInts，而不仅仅是第一个数据点 8。

 [8,5,3,4];

我的问题是为什么会这样？由于这是一个基本问题，我认为它与我的 push() 和 pop() 方法有关，但由于我编写的它们与我编写的方法类似在教科书上看到的，不知道是怎么回事。谁能帮我理解一下？

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;
}

编辑:按照建议返回对象而不是 Nodes，除了 push() 方法外，代码或多或少是相同的。因此，当我尝试将另一个对象添加到同一个 LinkedList 时，它会替换旧对象而不是添加到列表中。

 //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

Answer 1

当 pop 被调用时，您的实现返回了 Node 对象，但是 Node 仍然有一个对“下一个”位置的引用原始堆栈。

当您创建一个新的堆栈并压入弹出的项目时，原始的 Node 对象及其原始的 next 引用随行。

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

这就是为什么整个列表出现在新堆栈上的原因。

解决方案是根本不公开 Node 对象。不要在 push 中接受 Node，而是接受数据项，然后创建您自己的 Node。不是在 pop 和 peek 中返回一个 Node，而是从 Node 中提取数据项并返回它。这样您就不会无意中泄露对所需节点中下一个 Node 的引用。