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

Question

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

LinkedList listOfInts = new LinkedList();

然后我添加 Objects;

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

与以下 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;
 }
}

如果我这样做的话；

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 时，您的实现是 returning Node 对象，但是 Node 仍然引用了 "next" 中的位置原始堆栈。

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

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

这就是整个列表出现在新堆栈中的原因。

解决方案是完全不公开 Node 对象。不要在 push 中接受 Node，而是接受数据项，然后创建您自己的 Node。不要在 pop 和 peek 中 returning a Node，而是从 Node 和 return 中提取数据项。这样您就不会无意中冒着泄漏对所需节点中下一个 Node 的引用的风险。

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

Stack Implementation for Nodes containing Objects

java

stack

linked-list