java - LinkedList 存储节点的 LinkedList

Question

我写了一个LinkedList接受 Nodes 的类存储 Integers .

然后我创建了一个 LinkedList stack = new LinkedList() ，并添加了 Node s 如果 Node 的数据s 小于 Node 的数据stack 中已存在的 s .

如果没有，我想把这个旧的stack进入新LinkedList叫LinkedList pilesOfStacks ，并创建一个newStack叫LinkedList newStack = new LinkedList() ，并添加较大的 Node进入此newStack这也将进入 LinkedList pilesOfStacks .

我的问题是；因为我已经创建了我的 LinkedList类接受Node s，我该如何将其变成新的LinkedList接受LinkedList其中Nodes ，本质上是创建不同的 LinkedList 堆位于 LinkedList ？

这是我到目前为止所拥有的:

public void sort(LinkedList listOfInts)
{

  LinkedList<LinkedList> piles = new LinkedList<LinkedList>();

  LinkedList stack = new LinkedList();

  for(int i = 0; i < listOfInts.getSize(); i++)
  {
    Node x = listOfInts.pop();
    for(int j = 0; j < piles.getSize(); j++)
    {
      Node y = piles.peek(); //check first element of each pile

      if( ( ((Comparable)y.getData()).compareTo(x.getData()) ) <= 0)
      {
        stack.push(x);
        break;
      }
    }
    stack.push(x); //put value in stack
    piles.add(stack);
  }
}

编辑:如果我可以使用数组，我会创建一个 double 组来达到某种效果 Node[][] array = new Node[20][20];然后用 Node[i][0] 搜索它，但因为我只能使用 LinkedList ，我想知道如何做到这一点？

Answer 1

好吧，我只是尝试了一下 - 使用 Kami 和 Roman C 提到的 Java Collection Framework。为了避免混淆，我总是使用所涉及的接口(interface)/类的完整限定名称 - 即使这会使代码看起来又大又难看。

我使用了java.util.LinkedList，它实现了java.util.List以及java.util.Deque接口(interface)。后一个为您提供了将其视为堆栈的方法。

从方法名称来看，我假设您实际上想要对堆栈中的节点进行排序。为此，我必须更改原始示例的某些部分，因为它的行为似乎不像您所描述的那样。

我最终得到了您的示例的以下变体:

public void sort(java.util.Deque<Node> stackOfIntNodes) {
    java.util.List<java.util.Deque<Node>> piles =
            new java.util.LinkedList<java.util.Deque<Node>>();
    java.util.Deque<Node> currentStack = new java.util.LinkedList<Node>();
    inputLoop : while (!stackOfIntNodes.isEmpty()) {
        Node currentNode = stackOfIntNodes.pop();
        for (java.util.Deque<Node> singlePile : piles) {
            // check first element of each pile
            Node smallestNodeInSinglePile = singlePile.peek();
            Object valueOfSmallestNodeInSinglePile =
                    smallestNodeInSinglePile.getData();
            if ((((java.lang.Comparable) valueOfSmallestNodeInSinglePile)
                    .compareTo(currentNode.getData())) <= 0) {
                singlePile.push(currentNode);
                continue inputLoop;
            }
        }
        piles.add(currentStack);
        currentStack = new java.util.LinkedList<Node>();
        currentStack.push(currentNode); // put value in stack
    }
    piles.add(currentStack);
    java.util.Deque<Node> sortedStackOfIntNodes = new java.util.LinkedList<Node>();
    for (java.util.Deque<Node> singlePile : piles) {
        while (!singlePile.isEmpty()) {
            sortedStackOfIntNodes.push(singlePile.pop());
        }
    }
    // RESULT: you got all your Node elements in sorted order
}

但是，如果您确实使用 java.util.LinkedList 而不是您自己的实现，则可以轻松使用以下等效方法:

public void sort(java.util.Deque<Node> stackOfIntNodes) {
    java.util.LinkedList<Node> sortedListOfIntNodes =
            new java.util.LinkedList<Node>(stackOfIntNodes);
    java.util.Collections.sort(sortedListOfIntNodes,
            new Comparator<Node>() {
                @Override
                public int compare(Node nodeOne, Node nodeTwo) {
                    return ((java.lang.Comparable) nodeOne.getData())
                            .compareTo(nodeTwo.getData());
        }
    });
    // RESULT: you got all your Node elements in sorted order
}

根据您实际的 Node 类和/或自己的 LinkedList，您可能需要在此处应用进一步的更改。