LinkedList

System.Collections.Generic.LinkedListクラスは双方向の連結リストのデータ構造を提供するコレクションクラスです。　System.Collections名前空間ではLinkedListに相当するクラス、連結リストのデータ構造を持つ非ジェネリックコレクションクラスは提供されていません。

Listクラスとは異なりインデックスによるアクセスは出来ませんが、挿入と削除の操作はListクラスよりも高速に行えます(ListはO(n):要素数に比例、LinkedListはO(1):要素数によらず常に定数時間)。　LinkedListは、格納される要素の前後関係が重視され、かつ挿入・削除の操作が多いデータ群を扱う場合などに向いています。

基本的な操作

連結リストを実現するために、LinkedListクラスでは個々の要素がLinkedListNodeクラスで表されるノードとして格納されます。　LinkedListに値を追加する場合、その値をもつLinkedListNodeが作成され、LinkedList内の連結リストに追加されます。

各要素=個々のノードは前後のノードを互いに参照する状態で格納されます。　ノードの持つ値はLinkedListNode.Valueプロパティ、次のノードはLinkedListNode.Nextプロパティ、前のノードはLinkedListNode.Previousプロパティにそれぞれ格納されます。　Nextプロパティを次々にたどっていけば、連結リスト内の各ノードを先頭から順に参照していくことができます。　先頭のノード・末尾のノードでは次あるいは前のノードがないため、nullが設定されます。

LinkedList内のデータ構造
(null) [LinkedListNode] [LinkedListNode] [LinkedListNode] (null)
Value = "Alice" Value = "Bob" Value = "Charlie"
←Previous Next→ ←Previous Next→ ←Previous Next→

Listクラスとは異なり、LinkedListクラスでは要素(=ノード)の前後関係が大きな意味を持ちます。　LinkedListに値(ノード)が格納された後は、その順序を並べ替えることはできません。　並べ替えは削除と挿入によって行う必要があります。　また、LinkedListクラス内のノードは前と次のノードによってのみ位置関係が定まり、インデックスは持ちません。　そのため、インデックスを指定した要素へのアクセス(ランダムアクセス)はできません。　シーケンシャルアクセスのみを行うことができます。

LinkedListの先頭のノードはFirstプロパティ、末尾のノードはLastプロパティとして参照します。　LinkedListが空の場合、FirstプロパティとLastプロパティはともにnullとなります。

using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    LinkedList<string> list = new LinkedList<string>();

    list.AddFirst("Bob");     // LinkedListの先頭に"Bob"を追加
    list.AddLast("Charlie");  // LinkedListの末尾に"Charlie"を追加
    list.AddFirst("Alice");   // LinkedListの先頭に"Alice"を追加

    foreach (string e in list) {
      Console.WriteLine(e);
    }

    // Console.WriteLine(list[0]); // インデックスによるアクセスは出来ない
    Console.WriteLine("First => {0}", list.First.Value); // 最初のノードの値を表示
    Console.WriteLine("Last => {0}", list.Last.Value); // 最後のノードの値を表示
    Console.WriteLine("First.Next => {0}", list.First.Next.Value); // 最初のノードの、次のノードの値を表示
  }
}

Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim list As New LinkedList(Of String)()

    list.AddFirst("Bob")    ' LinkedListの先頭に"Bob"を追加
    list.AddLast("Charlie") ' LinkedListの末尾に"Charlie"を追加
    list.AddFirst("Alice")  ' LinkedListの先頭に"Alice"を追加

    For Each e As String In list
      Console.WriteLine(e)
    Next

    ' Console.WriteLine(list(0)); // インデックスによるアクセスは出来ない
    Console.WriteLine("First => {0}", list.First.Value) ' 最初のノードの値を表示
    Console.WriteLine("Last => {0}", list.Last.Value) ' 最後のノードの値を表示
    Console.WriteLine("First.Next => {0}", list.First.Next.Value) ' 最初のノードの、次のノードの値を表示
  End Sub
End Class
実行結果
Alice
Bob
Charlie
First => Alice
Last => Charlie
First.Next => Bob

ノードの追加

LinkedListへノードを追加するには、下記のメソッドを使います。　直接値を指定して追加することも、値が格納された状態のLinkedListNodeを追加することもできます。　位置を指定して追加するには、次または前となるノードを指定して追加します。

ノードを追加するためのメソッド
メソッド 動作
値の追加 AddFirst(value) 値valueを持つノードを作成してLinkedListの先頭に追加する
AddLast(value) 値valueを持つノードを作成してLinkedListの末尾に追加する
AddBefore(node, value) LinkedList内のノードnodeの前に、値valueを持つノードを作成して追加する
AddAfter(node, value) LinkedList内のノードnodeの後に、値valueを持つノードを作成して追加する
ノードの追加 AddFirst(node) LinkedListの先頭にノードnodeを追加する
AddLast(node) LinkedListの末尾にノードnodeを追加する
AddBefore(node, newNode) LinkedList内のノードnodeの前に、ノードnewNodeを追加する
AddAfter(node, newNode) LinkedList内のノードnodeの後に、ノードnewNodeを追加する

追加の際、既に他のLinkedListに属しているノードを追加しようとした場合はInvalidOperationExceptionがスローされます。　また、追加する値を指定するメソッドでは、戻り値として作成・追加されたノードが返されます。

using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    LinkedList<string> list = new LinkedList<string>();

    // LinkedListの先頭に"Alice"を追加
    LinkedListNode<string> alice = list.AddFirst("Alice");

    // ノード"Alice"の後に"Dave"を追加
    LinkedListNode<string> dave = list.AddAfter(alice, "Dave");

    // ノード"Dave"の前に"Charlie"を追加
    LinkedListNode<string> charlie = new LinkedListNode<string>("Charlie");

    list.AddBefore(dave, charlie);

    // LinkedListの末尾に"Eve"を追加
    list.AddLast("Eve");

    // ノード"Dave"の前の前に"Bob"を追加
    list.AddBefore(dave.Previous, "Bob");

    foreach (string e in list) {
      Console.WriteLine(e);
    }
  }
}

Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim list As New LinkedList(Of String)()

    ' LinkedListの先頭に"Alice"を追加
    Dim alice As LinkedListNode(Of String) = list.AddFirst("Alice")

    ' ノード"Alice"の後に"Dave"を追加
    Dim dave As LinkedListNode(Of String) = list.AddAfter(alice, "Dave")

    ' ノード"Dave"の前に"Charlie"を追加
    Dim charlie As New LinkedListNode(Of String)("Charlie")

    list.AddBefore(dave, charlie)

    ' LinkedListの末尾に"Eve"を追加
    list.AddLast("Eve")

    ' ノード"Dave"の前の前に"Bob"を追加
    list.AddBefore(dave.Previous, "Bob")

    For Each e As String In list
      Console.WriteLine(e)
    Next
  End Sub
End Class
実行結果
Alice
Bob
Charlie
Dave
Eve

ノードの削除

ノードを削除するには、次のメソッドを使います。　値を指定して削除する場合は、その値をもつ最初のノードが削除されます。

ノードを追加するためのメソッド
メソッド 動作
RemoveFirst() 先頭にあるノードを削除する
RemoveLast() 末尾にあるノードを削除する
Remove(value) 値valueを持つ最初のノード(もっとも前方にあるノード)を削除する
Remove(node) 指定されたノードnodeを削除する
nodeがLinkedListに属していない場合、InvalidOperationExceptionがスローされる		 
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    LinkedList<string> list = new LinkedList<string>(new string[] {
      "Alice", "Bob", "Charlie", "Dave", "Eve",
    });

    LinkedListNode<string> charlie = list.First.Next.Next;

    Console.WriteLine(string.Join(", ", list));

    // LinkedListからノード"Dave"を削除
    Console.WriteLine("[Remove Dave]");

    list.Remove("Dave");

    Console.WriteLine(string.Join(", ", list));

    // charlieの前のノードを削除
    Console.WriteLine("[Remove charlie.Previous]");

    list.Remove(charlie.Previous);

    Console.WriteLine(string.Join(", ", list));

    // LinkedListの末尾のノードを削除
    Console.WriteLine("[RemoveLast]");

    list.RemoveLast();

    Console.WriteLine(string.Join(", ", list));
  }
}

Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim list As New LinkedList(Of String)(New String() { _
      "Alice", "Bob", "Charlie", "Dave", "Eve" _
    })

    Dim charlie As LinkedListNode(Of String) = list.First.Next.Next

    Console.WriteLine(String.Join(", ", list))

    ' LinkedListからノード"Dave"を削除
    Console.WriteLine("[Remove Dave]")

    list.Remove("Dave")

    Console.WriteLine(String.Join(", ", list))

    ' charlieの前のノードを削除
    Console.WriteLine("[Remove charlie.Previous]")

    list.Remove(charlie.Previous)

    Console.WriteLine(String.Join(", ", list))

    ' LinkedListの末尾のノードを削除
    Console.WriteLine("[RemoveLast]")

    list.RemoveLast()

    Console.WriteLine(String.Join(", ", list))
  End Sub
End Class
実行結果
Alice, Bob, Charlie, Dave, Eve
[Remove Dave]
Alice, Bob, Charlie, Eve
[Remove charlie.Previous]
Alice, Charlie, Eve
[RemoveLast]
Alice, Charlie

このほかにも、Clearメソッドを使えばLinkedList内のすべてのノードを削除することができます。

push/pop, shift/unshiftに相当する操作

JavaScriptなどの配列ではpush/popおよびshift/unshiftといった操作を行うことができます。

JavaScriptにおけるpush/pop/shift/unshift
var arr = [0, 1, 2];
console.log(arr.toString());

arr.unshift(3);
console.log("unshift(3): " + arr);

console.log("shift() = " + arr.shift() + " : " + arr.toString());

arr.push(4);
console.log("push(4): " + arr);

console.log("pop() = " + arr.pop() + " : " + arr);
実行結果
0,1,2
unshift(3): 3,0,1,2
shift() = 3 : 0,1,2
push(4): 0,1,2,4
pop() = 4 : 0,1,2

LinkedListクラスでも同様の操作を行うことができますが、値の取得と同時に削除を行うpopとshiftに相当するメソッドは用意されていないので、取得と削除は個別に処理する必要があります。

push/pop, shift/unshiftに相当する操作
操作 LinkedListでの相当する操作
unshift LinkedList.AddFirst()
shift (get) LinkedList.First.Value + LinkedList.RemoveFirst()
push LinkedList.AddLast()
pop (get) LinkedList.Last.Value + LinkedList.RemoveLast()
LinkedListでpush/pop/shift/unshiftに相当する操作を行う
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    LinkedList<int> list = new LinkedList<int>(new int[] {
      0, 1, 2,
    });

    Console.WriteLine(string.Join(", ", list));
    Console.WriteLine();

    // unshift相当の操作
    list.AddFirst(3);

    Console.WriteLine("AddFirst(3): {0}", string.Join(", ", list));
    Console.WriteLine();

    // shift相当の操作
    Console.WriteLine("First.Value = {0}", list.First.Value);

    list.RemoveFirst();

    Console.WriteLine("RemoveFirst(): {0}", string.Join(", ", list));
    Console.WriteLine();

    // push相当の操作
    list.AddLast(4);

    Console.WriteLine("AddLast(4): {0}", string.Join(", ", list));
    Console.WriteLine();

    // pop相当の操作
    Console.WriteLine("Last.Value = {0}", list.Last.Value);

    list.RemoveLast();

    Console.WriteLine("RemoveLast(): {0}", string.Join(", ", list));
    Console.WriteLine();
  }
}
LinkedListでpush/pop/shift/unshiftに相当する操作を行う
Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim list As New LinkedList(Of Integer)(New Integer() {0, 1, 2})

    Console.WriteLine(String.Join(", ", list))
    Console.WriteLine()

    ' unshift相当の操作
    list.AddFirst(3)

    Console.WriteLine("AddFirst(3): {0}", String.Join(", ", list))
    Console.WriteLine()

    ' shift相当の操作
    Console.WriteLine("First.Value = {0}", list.First.Value)

    list.RemoveFirst()

    Console.WriteLine("RemoveFirst(): {0}", String.Join(", ", list))
    Console.WriteLine()

    ' push相当の操作
    list.AddLast(4)

    Console.WriteLine("AddLast(4): {0}", String.Join(", ", list))
    Console.WriteLine()

    ' pop相当の操作
    Console.WriteLine("Last.Value = {0}", list.Last.Value)

    list.RemoveLast()

    Console.WriteLine("RemoveLast(): {0}", String.Join(", ", list))
    Console.WriteLine()
  End Sub
End Class
実行結果
0, 1, 2

AddFirst(3): 3, 0, 1, 2

First.Value = 3
RemoveFirst(): 0, 1, 2

AddLast(4): 0, 1, 2, 4

Last.Value = 4
RemoveLast(): 0, 1, 2

push/popおよびshift/unshiftに相当する操作に関しては§.スタックとしての使用および§.キューとしての使用としても解説しています。

列挙操作

既に例にあげたとおり、LinkedListでもforeach文による列挙ができるようになっていますが、インデックスを指定したfor文による列挙は出来ません。　ただし、繰り返し構文とLinkedListNode.Nextプロパティ・LinkedListNode.Previousプロパティを組み合わせることで、任意のノードを起点として列挙を行うことが出来ます。

using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    LinkedList<string> list = new LinkedList<string>(new string[] {
      "Alice", "Bob", "Charlie", "Dave", "Eve",
    });

    // foreach文による列挙
    Console.WriteLine("[foreach]");

    foreach (string e in list) {
      Console.WriteLine(e);
    }

    // 末尾のノードから前方にたどって列挙する
    Console.WriteLine("[tail to head]");

    for (LinkedListNode<string> node = list.Last; node != null; node = node.Previous) {
      Console.WriteLine(node.Value);
    }

    // 先頭の次のノードから後方にたどって列挙する
    Console.WriteLine("[head to tail]");

    for (LinkedListNode<string> node = list.First.Next; node != null; node = node.Next) {
      Console.WriteLine(node.Value);
    }
  }
}

Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim list As New LinkedList(Of String)(New String() { _
      "Alice", "Bob", "Charlie", "Dave", "Eve" _
    })

    ' foreach文による列挙
    Console.WriteLine("[foreach]")

    For Each e As String In list
      Console.WriteLine(e)
    Next

    ' 末尾のノードから前方にたどって列挙する
    Console.WriteLine("[tail to head]")

    Dim node As LinkedListNode(Of String) = list.Last

    Do While Not node Is Nothing
      Console.WriteLine(node.Value)

      node = node.Previous
    Loop

    ' 先頭の次のノードから後方にたどって列挙する
    Console.WriteLine("[head to tail]")

    node = list.First.Next

    Do While Not node Is Nothing
      Console.WriteLine(node.Value)

      node = node.Next
    Loop
  End Sub
End Class
実行結果
[foreach]
Alice
Bob
Charlie
Dave
Eve
[tail to head]
Eve
Dave
Charlie
Bob
Alice
[head to tail]
Bob
Charlie
Dave
Eve

検索

LinkedList内の要素の検索を行うためには次のメソッドが使えます。　FindメソッドはLinkedList内にあるノードから指定された値を持つ最初のノードを返します。　FindLastメソッドは逆に、指定された値を持つ最後のノードを返します。　いずれのメソッドも、見つからない場合はnull(Nothing)が返されます。

Containsメソッドは、単に指定された値を持つノードがあるかどうかを返します。

using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    LinkedList<int> list = new LinkedList<int>(new int[] {
      0, 1, 2, 3, 2, 1, 0,
    });

    LinkedListNode<int> found;

    // 値に2を持つ最初のノードを取得する
    found = list.Find(2);

    Console.WriteLine("[Find]");
    Console.WriteLine("found.Previous: {0}", found.Previous.Value);
    Console.WriteLine("found.Next: {0}", found.Next.Value);

    // 値に2を持つ最後のノードを取得する
    found = list.FindLast(2);

    Console.WriteLine("[FindLast]");
    Console.WriteLine("found.Previous: {0}", found.Previous.Value);
    Console.WriteLine("found.Next: {0}", found.Next.Value);

    // 値に1を持つノードがあるかどうか
    Console.WriteLine();
    Console.WriteLine("Contains(1) = {0}", list.Contains(1));
  }
}

Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim list As New LinkedList(Of Integer)(New Integer() { _
      0, 1, 2, 3, 2, 1, 0 _
    })

    Dim found As LinkedListNode(Of Integer)

    ' 値に2を持つ最初のノードを取得する
    found = list.Find(2)

    Console.WriteLine("[Find]")
    Console.WriteLine("found.Previous: {0}", found.Previous.Value)
    Console.WriteLine("found.Next: {0}", found.Next.Value)

    ' 値に2を持つ最後のノードを取得する
    found = list.FindLast(2)

    Console.WriteLine("[FindLast]")
    Console.WriteLine("found.Previous: {0}", found.Previous.Value)
    Console.WriteLine("found.Next: {0}", found.Next.Value)

    ' 値に1を持つノードがあるかどうか
    Console.WriteLine()
    Console.WriteLine("Contains(1) = {0}", list.Contains(1))
  End Sub
End Class
実行結果
[Find]
found.Previous: 1
found.Next: 3
[FindLast]
found.Previous: 3
found.Next: 1

Contains(1) = True

スタックとしての使用

.NET Frameworkではスタックのデータ構造を構成するコレクションとしてStackクラスが個別に用意されていますが、LinkedListを使って連結リストをスタックのように扱うこともできます。

LinkedListの先頭に要素を追加していくことによりプッシュ操作となり、先頭から要素を参照・削除していくことでポップ操作となるため、スタックとしての操作を行うことができます。

LinkedListを使ったスタック操作
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    LinkedList<string> s = new LinkedList<string>();

    // スタックへのプッシュ操作
    // (LinkedListの先頭に値を追加していく)
    s.AddFirst("Alice");
    s.AddFirst("Bob");
    s.AddFirst("Charlie");

    // スタックからのポップ操作
    // (LinkedListの先頭から値を参照しノードを削除していく)
    Console.WriteLine(s.First.Value);

    s.RemoveFirst();

    Console.WriteLine(s.First.Value);

    s.RemoveFirst();

    Console.WriteLine(s.First.Value);

    s.RemoveFirst();
  }
}
LinkedListを使ったスタック操作
Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim s As New LinkedList(Of String)()

    ' スタックへのプッシュ操作
    ' (LinkedListの先頭に値を追加していく)
    s.AddFirst("Alice")
    s.AddFirst("Bob")
    s.AddFirst("Charlie")

    ' スタックからのポップ操作
    ' (LinkedListの先頭から値を参照しノードを削除していく)
    Console.WriteLine(s.First.Value)

    s.RemoveFirst()

    Console.WriteLine(s.First.Value)

    s.RemoveFirst()

    Console.WriteLine(s.First.Value)

    s.RemoveFirst()
  End Sub
End Class
Stackクラスを使ったスタック操作
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    Stack<string> s = new Stack<string>();

    // スタックへのプッシュ操作

    s.Push("Alice");
    s.Push("Bob");
    s.Push("Charlie");

    // スタックからのポップ操作

    Console.WriteLine(s.Pop());



    Console.WriteLine(s.Pop());



    Console.WriteLine(s.Pop());


  }
}
Stackクラスを使ったスタック操作
Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim s As New Stack(Of String)()

    ' スタックへのプッシュ操作

    s.Push("Alice")
    s.Push("Bob")
    s.Push("Charlie")

    ' スタックからのポップ操作

    Console.WriteLine(s.Pop())



    Console.WriteLine(s.Pop())



    Console.WriteLine(s.Pop())


  End Sub
End Class
実行結果
Charlie
Bob
Alice

データ構造としてのスタック、およびStackクラスについてはジェネリックコレクション(5) Stackを参照してください。

キューとしての使用

.NET Frameworkではキューのデータ構造を構成するコレクションとしてQueueクラスが個別に用意されていますが、LinkedListを使って連結リストをキューのように扱うこともできます。

LinkedListの末尾に要素を追加していくことによりエンキュー操作となり、先頭から要素を参照・削除していくことでデキュー操作となるため、キューとしての操作を行うことができます。

LinkedListを使ったキュー操作
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    LinkedList<string> q = new LinkedList<string>();

    // キューへのエンキュー操作
    // (LinkedListの末尾に値を追加していく)
    q.AddLast("Alice");
    q.AddLast("Bob");
    q.AddLast("Charlie");

    // キューからのデキュー操作
    // (LinkedListの先頭から値を参照しノードを削除していく)
    Console.WriteLine(q.First.Value);

    q.RemoveFirst();

    Console.WriteLine(q.First.Value);

    q.RemoveFirst();

    Console.WriteLine(q.First.Value);

    q.RemoveFirst();
  }
}
LinkedListを使ったキュー操作
Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim q As New LinkedList(Of String)()

    ' キューへのエンキュー操作
    ' (LinkedListの末尾に値を追加していく)
    q.AddLast("Alice")
    q.AddLast("Bob")
    q.AddLast("Charlie")

    ' キューからのデキュー操作
    ' (LinkedListの先頭から値を参照しノードを削除していく)
    Console.WriteLine(q.First.Value)

    q.RemoveFirst()

    Console.WriteLine(q.First.Value)

    q.RemoveFirst()

    Console.WriteLine(q.First.Value)

    q.RemoveFirst()
  End Sub
End Class
Queueクラスを使ったキュー操作
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    // キューへのエンキュー操作

    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue("Charlie");

    // キューからのデキュー操作

    Console.WriteLine(q.Dequeue());



    Console.WriteLine(q.Dequeue());



    Console.WriteLine(q.Dequeue());


  }
}
Queueクラスを使ったキュー操作
Imports System
Imports System.Collections.Generic

Class Sample
  Shared Sub Main()
    Dim q As New Queue(Of String)()

    ' キューへのエンキュー操作

    q.Enqueue("Alice")
    q.Enqueue("Bob")
    q.Enqueue("Charlie")

    ' キューからのデキュー操作

    Console.WriteLine(q.Dequeue())



    Console.WriteLine(q.Dequeue())



    Console.WriteLine(q.Dequeue())


  End Sub
End Class
実行結果
Alice
Bob
Charlie

データ構造としてのキュー、およびQueueクラスについてはジェネリックコレクション(6) Queueを参照してください。