用于存储节点的LinkedList的LinkedList

Question

我已经编写了一个接受存储Integers的Nodes的LinkedList类。

然后，我创建了一个LinkedList stack = new LinkedList()，如果Nodes的数据小于此stack中已存在的Nodes的数据，则将Nodes添加到其中。

如果没有，我想将这个旧的stack放到一个名为LinkedList pilesOfStacks的新LinkedList中，创建一个名为LinkedList newStack = new LinkedList()的newStack，并将更大的Node添加到这个newStack中，它也将进入LinkedList pilesOfStacks中。

我的问题是:既然我已经创建了接受Node的LinkedList类，那么我如何使它成为一个新的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);
  }
}

编辑:如果我可以使用一个数组，我会创建一个类似Node[][] array = new Node[20][20];的双精度数组，然后用Node[i][0]搜索它，但由于我只能使用LinkedList，我想知道怎么做？

Answer 1

好吧，我只是尝试了一下-使用Kami和Roman C提到的Java集合框架-为了避免混淆，我总是使用所涉及的接口/类的全限定名-即使这会使代码看起来又大又丑陋。

我使用了实现java.util.List和java.util.Deque接口的java.util.LinkedList。后者为您提供了将其视为堆栈的方法。

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

我以你的例子的以下变体结束：

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
}

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