.Net 框架提供了兩種List類型，一種是基於鏈表的LinkedList, 一種是基於數組的List。那麼在實際應用中到底采用哪種List，如何取捨呢？本文對兩種類型在隊列，堆棧和簡單插入三種簡單算法中的效率進行了一個比較。
首先先讓我們來看一下List的初始容量Capacity對List的性能是否有影響。
測試方法：分別設置初始容量為0，64，255，1024. List插入的最大長度為1000，循環1000次，得到如下結果，單位為ms，下同。
算法/初始容量 0 64 255 1024 隊列 35837 35753 37171 35711 堆棧 302 279 298 289 簡單插入 100 105 100 100
從上面數據中我們可以看出List的初始容量對效率沒有明顯影響。
隊列算法比較
測試方法：對LinkedList和List采用先進先出的隊列算法，分別設置隊列最大長度為10，30，50，100，1000，10000，並循環1000次，得到如下結果。
List類型/隊列最大長度 10 30 50 100 1000 10000 LinkedList 0.7659 0.8768 1.1041 2.0401 61 691 List 0.3326 1.1677 1.9985 12 443 37516
從測試結果中我們可以看出LinkedList 隨著最大隊列長度的增加，所用時間基本成線性增長。而List則成指數增長。我分析主要原因應該是每次刪除List的數組頭時，List都要做一次整個數數組的拷貝，而鏈表類型則不存在這個問題。有趣的是當隊列長度小於30時，List的效率要比LinkedList要高，這主要是因為鏈表在增刪元素時需要額外創建鏈表指針，而數組不需要這個操作。在隊列長度較小時，這種開銷就會顯得很明顯。
堆棧算法比較
測試方法：對LinkedList和List采用先進後出的堆棧算法，分別設置隊列最大長度為10，30，50，100，1000，10000，並循環1000次，得到如下結果。
List類型/堆棧最大長度 10 30 50 100 1000 10000 LinkedList 0.8515 0.9295 1.1123 2.1874 58 714 List 0.1109 0.3104 0.5118 1.2256 29 284
從測試結果看兩種類型都是線性增長，但List的性能更高一些。我分析這主要是因為List類型在增長到最大值後在從尾部刪除元素，其並不重新分配內存，除非你強行讓它壓縮。所以List從尾部刪除只是將Count改變了一下，因此效率很高。而鏈表類型的效率和隊列方式基本相當，這也是在預料之中的，其效率比List低的原因主要還是在增刪時創建和刪除節點的額外開銷。
簡單插入算法比較
測試方法：對LinkedList和List采用向後追加若干元素的算法，分別設置插入最大長度為10，30，50，100，1000，10000，並循環1000次，得到如下結果。
List類型/插入最大長度 10 30 50 100 1000 10000 LinkedList 0.6778 0.765 0.938 1.7783 40 535 List 0.0864 0.1661 0.2509 0.4312 10 109
其測試結果和堆棧算法基本類似，且List的效率更高，這裡不再重復論述。
總結
如果采用隊列算法建議采用LinkedList類型，除非隊列長度小於30.
如果采用堆棧或簡單插入算法，建議采用List類型。但有一點需要說明，如果應用對內存占用有限制，建議采用LinkedList類型。
測試代碼
class Program
{
const int TEST_TIMES = 1000;
static private void TestQueue(int count)
{
TestQueue(count, 0);
}
static private void TestQueue(int count, int capacity)
{
Console.WriteLine("Count:" + count.ToString());
LinkedList<int> linkList = new LinkedList<int>();
List<int> list = new List<int>(capacity);
Stopwatch watch = new Stopwatch();
watch.Start();
for (int i = 0; i < TEST_TIMES; i++)
{
for (int j = 0; j < count; j++)
{
linkList.AddLast(j);
}
for (int j = 0; j < count; j++)
{
int test = linkList.First.Value;
linkList.RemoveFirst();
}
}
watch.Stop();
String duration;
if (watch.ElapsedMilliseconds < 10)
{
duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms";
}
else
{
duration = watch.ElapsedMilliseconds.ToString() + "ms";
}
Console.WriteLine("LinkedList:" + duration);
watch.Reset();
watch.Start();
for (int i = 0; i < TEST_TIMES; i++)
{
for (int j = 0; j < count; j++)
{
list.Add(j);
}
for (int j = 0; j < count; j++)
{
int test = list[0];
list.RemoveAt(0);
}
}
if (watch.ElapsedMilliseconds < 10)
{
duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms";
}
else
{
duration = watch.ElapsedMilliseconds.ToString() + "ms";
}
Console.WriteLine("List:" + duration);
}
static private void TestStack(int count)
{
TestStack(count, 0);
}
static private void TestStack(int count, int capacity)
{
Console.WriteLine("Count:" + count.ToString());
LinkedList<int> linkList = new LinkedList<int>();
List<int> list = new List<int>(capacity);
Stopwatch watch = new Stopwatch();
watch.Start();
for (int i = 0; i < TEST_TIMES; i++)
{
for (int j = 0; j < count; j++)
{
linkList.AddLast(j);
}
for (int j = 0; j < count; j++)
{
int test = linkList.Last.Value;
linkList.RemoveLast();
}
}
watch.Stop();
String duration;
if (watch.ElapsedMilliseconds < 10)
{
duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms";
}
else
{
duration = watch.ElapsedMilliseconds.ToString() + "ms";
}
Console.WriteLine("LinkedList:" + duration);
watch.Reset();
watch.Start();
for (int i = 0; i < TEST_TIMES; i++)
{
for (int j = 0; j < count; j++)
{
list.Add(j);
}
for (int j = 0; j < count; j++)
{
int test = list[list.Count-1];
list.RemoveAt(list.Count - 1);
}
}
if (watch.ElapsedMilliseconds < 10)
{
duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms";
}
else
{
duration = watch.ElapsedMilliseconds.ToString() + "ms";
}
Console.WriteLine("List:" + duration);
}
static private void TestInsert(int count)
{
TestInsert(count, 0);
}
static private void TestInsert(int count, int capacity)
{
Console.WriteLine("Count:" + count.ToString());
LinkedList<int> linkList = new LinkedList<int>();
List<int> list = new List<int>(capacity);
Stopwatch watch = new Stopwatch();
watch.Start();
for (int i = 0; i < TEST_TIMES; i++)
{
for (int j = 0; j < count; j++)
{
linkList.AddLast(j);
}
linkList.Clear();
}
watch.Stop();
String duration;
if (watch.ElapsedMilliseconds < 10)
{
duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms";
}
else
{
duration = watch.ElapsedMilliseconds.ToString() + "ms";
}
Console.WriteLine("LinkedList:" + duration);
watch.Reset();
watch.Start();
for (int i = 0; i < TEST_TIMES; i++)
{
for (int j = 0; j < count; j++)
{
list.Add(j);
}
list.Clear();
}
if (watch.ElapsedMilliseconds < 10)
{
duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms";
}
else
{
duration = watch.ElapsedMilliseconds.ToString() + "ms";
}
Console.WriteLine("List:" + duration);
}
static void Main(string[] args)
{
//capacity
TestQueue(10000, 0);
TestQueue(10000, 64);
TestQueue(10000, 255);
TestQueue(10000, 1024);
TestStack(10000, 0);
TestStack(10000, 64);
TestStack(10000, 255);
TestStack(10000, 1024);
TestInsert(10000, 0);
TestInsert(10000, 64);
TestInsert(10000, 255);
TestInsert(10000, 1024);
//compare LinkedList and List
TestQueue(10);
TestQueue(30);
TestQueue(50);
TestQueue(100);
TestQueue(1000);
TestQueue(10000);
TestStack(10);
TestStack(30);
TestStack(50);
TestStack(100);
TestStack(1000);
TestStack(10000);
TestInsert(10);
TestInsert(30);
TestInsert(50);
TestInsert(100);
TestInsert(1000);
TestInsert(10000);
}
}
