作者：Flyingis
數組和鏈表是數據結構中老生常談的問題，在指針或是引用這些概念出來之前，數組就能用來實現鏈表的功能。這里所說的鏈表指的就是用指針或對象的引用來設計的鏈表。
在實際的應用開發中，數組由于它天生的種種特性(參考《Java容器分析—數組》)，更多的會被開發人員所想到用到，但所有的數據結構都有它特定的適用場合。眾所周知，數組和鏈表最大的區別在于，使用數組能夠快速訪問數組中的每個元素，而使用鏈表可以方便的操縱每個數據項。下面通過兩個很有趣的例子說明了它們各自的區別與優勢。
雖然在JDK中Java提供了List接口及其接口的實現(ArrayList/LinkedList)對鏈表數據結構提供了有力的支持，具體可以參考《Java容器分析—List和Set》但下面數學上關于Josephus問題的實現僅使用了自定義的最簡單的鏈表結構。
/**
* 根據命令行輸入的N值，計算出所有小于N的素數
* 是素數將數組元素值設為true，否則設為false
*/
class ArrayApp {
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
boolean[] a = new boolean[N];
for (int i = 2; i < N; i++)
a[i] = true;
for (int i = 2; i < N; i++)
if (a[i] != false)
for (int j = i; j*i < N; j++)
a[i*j] = false;
for (int i = 2; i < N; j++)
if (a[i])
System.out.println(“” + i);
}
}
/**
* N個有編號的小球圍成一圈，每個M-1個就拿去一個小球，計算最后剩下的球的位置
*/
class LinkApp {
static class Node {
int value;
Node next;
Node (int v) { v = value; }
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
int M = Integer.parseInt(args[1]);
Node first = new Node(1);
Node x = first;
for (int i = 2; i <= N; i++)
x = (x.next = new Node(i));
x.next = first;
while (x != x.next) {
for (int i = 1; i < M; i++)
x = x.next;
x.next = x.next.next;
}
System.out.println(“最后剩下的小球：” + x.value);
}
}