Skip to content

List と LinkedList の性能差

数年前から Java やその他の言語を書く機会がめっきり減り、（自分で選択出来るのであれば）C# で書くようになりました。「Eclipse よりも、Visual Studio が好きだから」という理由が大きいのですが・・・川俣晶さんのプログラミング関連書籍は興味深いものが多く、しばしば拝見させて頂いていますが、C# を書く機会が増えたので以下の書籍は購入させて頂きました。ちょうど上から順に "C# 2.0", "3.0", "4.0" がテーマとして取り上げられています。

そもそも、System.Collections.Generic.List も System.Collections.Generic.LinkedList も一次元リストを扱うものですが、List はインデックスを指定することで任意の位置にアクセス出来るが、LinkedList はインデックス指定ではリストにアクセス出来ず、先頭か、もしくは末尾から順に目的のデータ位置まで辿っていかなければならない、という機能差があります。「究極のC#プログラミング」では System.Collections.Generic.List と System.Collections.Generic.LinkedList の性能差について言及してあり、面白そうだったので検証してみました。

List のサンプル

System.Collections.Generic.List を使ったサンプルは以下の通りです。ほぼ書籍のサンプル通りで「10,000 回の挿入を 100 回、繰り返す」というものですが、プログラム終了直前に GC.GetTotalMemory(false) でメモリの消費量を取得して表示させています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using System;
using System.Collections.Generic;

class Program
{
  static void Main(string[] args)
  {
    // List
    var start1 = DateTime.Now;
    for (int i = 0; i < 100; i++)
    {
      var list1 = new List<string>();
      list1.Add("First");
      list1.Add("Last");

      for (int j = 0; j < 10000; j++)
      {
        list1.Insert(1, "Inserted");
      }
    }
    var end1 = DateTime.Now;
    Console.WriteLine(end1 - start1);

    Console.WriteLine("Memory: {0:N0}", GC.GetTotalMemory(false));
  }
}

LinkedList のサンプル

System.Collections.Generic.LinkedList を使ったサンプルは以下の通りです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using System;
using System.Collections.Generic;

class Program
{
  static void Main(string[] args)
  {
    // LinkedList
    var start2 = DateTime.Now;
    for (int i = 0; i < 100; i++)
    {
      var list2 = new LinkedList<string>();
      list2.AddFirst("First");
      list2.AddLast("Last");

      for (int j = 0; j < 10000; j++)
      {
        list2.AddAfter(list2.First, "Inserted");
      }
    }
    var end2 = DateTime.Now;
    Console.WriteLine(end2 - start2);

    Console.WriteLine("Memory: {0:N0}", GC.GetTotalMemory(false));
  }
}

実行結果の比較

System.Collections.Generic.List を使ったサンプルの実行結果は以下の通りです。

1
2
3
> ListSample.exe
00:00:03.5758200
Memory: 775,008

System.Collections.Generic.LinkedList を使ったサンプルの実行結果は以下の通りです。

1
2
3
> LinkedListSample.exe
00:00:00.0635050
Memory: 2,455,652

両者を比較すると以下のような特徴があるのが、一目瞭然です。

  • System.Collections.Generic.LinkedList の方が挿入処理は圧倒的に早い
  • System.Collections.Generic.List の方がメモリ消費量が圧倒的に少ない