Java：如何遍历类型链表的数组并将它们附加到数组

Question

对于算法 class 中的家庭作业，我们必须编写一个实现基数排序算法的程序。我最终以一种循环的方式实现了它，并且它运行正常。但是，我的代码中有一部分看起来很糟糕，如果 else 阻塞在 for 循环中。我必须以正确的顺序从链表数组中检索项目，并将元素添加回整数数组。我的一个 class 伙伴和我花了很长时间试图弄清楚如何将这个块放入 for 循环中，但就是想不出一个办法来做到这一点。这就是我的问题，我如何将数组中链表的对象放入不同的数组中。我为排序方法提出的代码如下：

private static Integer[] sort(Integer[] input, int place){
    //create an array of linked lists
    LinkedList<Integer>[] bucketsOut = new LinkedList[10];

    //initialize the linked lists
    for(int i=0; i < 10; i++){
        bucketsOut[i] = new LinkedList<Integer>();
    }

    int bucketPlacement = 0;
    //place every input into the correct bucket
    for(int i = 0; i < input.length; i++){
        bucketPlacement = getDigit(input[i].intValue(), place);
        bucketsOut[bucketPlacement].add(input[i]);
    }

    //Place the elements out of the linked lists into the correct place in input[]
    for(int i = 0; i < input.length; i++){ //for each input number
        if(bucketsOut[0].peekFirst() != null){  
            input[i] = bucketsOut[0].pollFirst().intValue();
        }else if(bucketsOut[1].peekFirst() != null){    
            input[i] = bucketsOut[1].pollFirst().intValue();
        }else if(bucketsOut[2].peekFirst() != null){    
            input[i] = bucketsOut[2].pollFirst().intValue();
        }else if(bucketsOut[3].peekFirst() != null){    
            input[i] = bucketsOut[3].pollFirst().intValue();
        }else if(bucketsOut[4].peekFirst() != null){    
            input[i] = bucketsOut[4].pollFirst().intValue();
        }else if(bucketsOut[5].peekFirst() != null){    
            input[i] = bucketsOut[5].pollFirst().intValue();
        }else if(bucketsOut[6].peekFirst() != null){    
            input[i] = bucketsOut[6].pollFirst().intValue();
        }else if(bucketsOut[7].peekFirst() != null){    
            input[i] = bucketsOut[7].pollFirst().intValue();
        }else if(bucketsOut[8].peekFirst() != null){    
            input[i] = bucketsOut[8].pollFirst().intValue();
        }else if(bucketsOut[9].peekFirst() != null){    
            input[i] = bucketsOut[9].pollFirst().intValue();
        }
    }
    //return sorted list for digit
    return input;
}

Answer 1

当你有一系列的操作除了改变一个索引外完全相同，这意味着你可以在一个for循环中完成：

第一次尝试

for (int j = 0; j < bucketsOut.length; j++ ) {
    // The part that is repeated again and again
    if (bucketsOut[j].peekFirst() != null) {
        input[i] = bucketsOut[j].pollFirst().intValue();
    }
}

但是等等！这将在所有桶中继续。您原来的 if 结构实际上意味着一旦您点击右侧 if，您将不会查看任何其他 else。

这可以通过在条件变为真时跳出循环来完成：

改进版

for (int j = 0; j < bucketsOut.length; j++ ) {
    if (bucketsOut[j].peekFirst() != null) {
        input[i] = bucketsOut[j].pollFirst().intValue();
        break; // Now the j loop will stop when we hit the first non-null.
    }
}

或者您可以使用增强型 for - 逻辑是相同的：

for ( LinkedList<Integer> bucket : bucketsOut ) {
    if (bucket.peekFirst() != null) {
        input[i] = bucket.pollFirst().intValue();
        break; 
    }
}

Answer 2

感谢 greybeard 指出上面的 elses 实际上导致第一个桶首先被完全清空。

考虑到这一点，将其变成一个循环并不难。请记住，您的基本想法是首先要复制第一个存储桶中的所有项目。这很容易通过 while 循环完成。

     while( bucketsOut[bucketIndex].peekFirst() != null &&
             inputIndex < input.length ) 
     {
        input[inputIndex++] = bucketsOut[bucketIndex].pollFirst();
     }

所以在这里，对于每个桶，我们复制直到 peek 值为空。请注意，我在数组索引中使用了 post-increment。当您需要将一定数量的元素复制到数组中时，这非常常见。它允许我复制到增加的元素，而不必事先用 for 循环固定确切的数字。

有了这些，剩下的就很简单了。我只是在 while 循环周围添加了一个 for 循环以递增到下一个桶。 while 循环检查 inputIndex 所以我们不会不小心尝试复制超出 input.

的末尾

  for( int inputIndex = 0, bucketIndex = 0; bucketIndex < bucketsOut.length;
          bucketIndex++ ) 
  {
     while( bucketsOut[bucketIndex].peekFirst() != null &&
             inputIndex < input.length ) 
     {
        input[inputIndex++] = bucketsOut[bucketIndex].pollFirst();
     }
  }

如果你想要花哨的（或者如果你有更多的元素）你可以在 while 循环之后添加一个手动测试这样你就不必测试更多的桶如果 input 是已满

     if( inputIndex >= input.length ) break;

Java：如何遍历类型链表的数组并将它们附加到数组

Java: How to iterate through an array of type linked lists and append those to an array

java

arrays

algorithm

linked-list

radix