配列&コレクション

[C#] LinkedListの使い方をわかりやすく解説

C#のLinkedListは、双方向連結リストを実装したデータ構造です。

LinkedList<T>は、要素を順序付きで格納し、各要素が前後の要素への参照を持つため、挿入や削除が効率的です。

AddFirstやAddLastで要素をリストの先頭や末尾に追加でき、Removeで特定の要素を削除できます。

FirstやLastプロパティで先頭や末尾の要素にアクセス可能です。

リスト内の要素を順にたどるにはforeachループが便利です。

目次から探す

LinkedListとは

LinkedListは、C#のコレクションの一つで、要素をノードとして管理するデータ構造です。

各ノードは、データと次のノードへの参照を持ち、双方向リストとしても利用できます。

これにより、要素の追加や削除が効率的に行える特徴があります。

LinkedListの基本構造

LinkedListは、以下のような基本構造を持っています。

ノード(Node): 各要素を表す構造体で、データと次のノードへの参照を持つ。
ヘッド(Head): リストの最初のノードを指す参照。
テイル(Tail): リストの最後のノードを指す参照。

以下は、LinkedListのノードの基本的な構造を示すサンプルコードです。

public class Node<T>
{
    public T Data; // ノードのデータ
    public Node<T> Next; // 次のノードへの参照
    public Node(T data)
    {
        Data = data;
        Next = null; // 初期状態では次のノードはnull
    }
}

配列やListとの違い

LinkedListは、配列やListと異なる特性を持っています。

以下の表に、主な違いを示します。

特徴	LinkedList	配列/List
メモリ管理	動的にメモリを確保	固定サイズまたは動的サイズ
要素の追加/削除	O(1)で効率的	O(n)で非効率的
ランダムアクセス	O(n)で非効率的	O(1)で効率的
メモリ使用量	各ノードにポインタが必要	連続したメモリ領域を使用

LinkedListのメリットとデメリット

LinkedListには、以下のようなメリットとデメリットがあります。

メリット

要素の追加や削除が高速(O(1))。
サイズが動的に変化するため、メモリの無駄が少ない。

デメリット

ランダムアクセスが遅い(O(n))。
各ノードにポインタを持つため、メモリ使用量が多くなる。

LinkedListの基本操作

LinkedListでは、要素の追加、削除、検索、取得が簡単に行えます。

ここでは、これらの基本操作について詳しく解説します。

要素の追加

LinkedListに要素を追加するためのメソッドはいくつかあります。

AddFirstメソッド

AddFirstメソッドは、リストの先頭に新しい要素を追加します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        
        linkedList.AddFirst("要素1"); // 先頭に要素を追加
        linkedList.AddFirst("要素2"); // 先頭に要素を追加
        foreach (var item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

要素2
要素1

AddLastメソッド

AddLastメソッドは、リストの末尾に新しい要素を追加します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        
        linkedList.AddLast("要素1"); // 末尾に要素を追加
        linkedList.AddLast("要素2"); // 末尾に要素を追加
        foreach (var item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

要素1
要素2

AddBefore/AddAfterメソッド

AddBeforeメソッドとAddAfterメソッドは、指定したノードの前または後に要素を追加します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("要素1");
        linkedList.AddLast("要素2");
        
        LinkedListNode<string> node = linkedList.Find("要素1");
        linkedList.AddAfter(node, "要素3"); // 要素1の後に要素3を追加
        foreach (var item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

要素1
要素3
要素2

要素の削除

LinkedListから要素を削除するためのメソッドもいくつか用意されています。

Removeメソッド

Removeメソッドは、指定した要素をリストから削除します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("要素1");
        linkedList.AddLast("要素2");
        
        linkedList.Remove("要素1"); // 要素1を削除
        foreach (var item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

要素2

RemoveFirst/RemoveLastメソッド

RemoveFirstメソッドはリストの先頭の要素を、RemoveLastメソッドは末尾の要素を削除します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("要素1");
        linkedList.AddLast("要素2");
        
        linkedList.RemoveFirst(); // 先頭の要素を削除
        foreach (var item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

要素2

要素の検索

LinkedList内の要素を検索するためのメソッドも用意されています。

Containsメソッド

Containsメソッドは、指定した要素がリストに含まれているかどうかを確認します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("要素1");
        linkedList.AddLast("要素2");
        
        bool exists = linkedList.Contains("要素1"); // 要素1が存在するか確認
        Console.WriteLine($"要素1は存在するか: {exists}");
    }
}

要素1は存在するか: True

Find/FindLastメソッド

Findメソッドは、指定した要素を検索し、最初に見つかったノードを返します。

FindLastメソッドは、最後に見つかったノードを返します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("要素1");
        linkedList.AddLast("要素2");
        
        LinkedListNode<string> node = linkedList.Find("要素2"); // 要素2を検索
        Console.WriteLine($"見つかった要素: {node.Value}");
    }
}

見つかった要素: 要素2

要素の取得

LinkedListから要素を取得するためのプロパティやノードの使い方について説明します。

Firstプロパティ

Firstプロパティは、リストの最初の要素を取得します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("要素1");
        linkedList.AddLast("要素2");
        
        string firstElement = linkedList.First.Value; // 最初の要素を取得
        Console.WriteLine($"最初の要素: {firstElement}");
    }
}

最初の要素: 要素1

Lastプロパティ

Lastプロパティは、リストの最後の要素を取得します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("要素1");
        linkedList.AddLast("要素2");
        
        string lastElement = linkedList.Last.Value; // 最後の要素を取得
        Console.WriteLine($"最後の要素: {lastElement}");
    }
}

最後の要素: 要素2

LinkedListNodeの使い方

LinkedListNodeは、LinkedListの要素を表すノードです。

ノードを使って、要素の追加や削除を行うことができます。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        LinkedListNode<string> node = linkedList.AddLast("要素1"); // 要素1を追加
        
        linkedList.AddAfter(node, "要素2"); // 要素1の後に要素2を追加
        foreach (var item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

要素1
要素2

LinkedListの応用操作

LinkedListは、基本的な操作だけでなく、さまざまな応用操作にも対応しています。

ここでは、要素の挿入位置を指定する方法、要素の逆順処理、要素の並び替え、複数のLinkedListを結合する方法について解説します。

要素の挿入位置を指定する

LinkedListでは、特定の位置に要素を挿入することができます。

AddBeforeメソッドやAddAfterメソッドを使用して、指定したノードの前または後に要素を追加します。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("要素1");
        linkedList.AddLast("要素3");
        
        LinkedListNode<string> node = linkedList.Find("要素3");
        linkedList.AddBefore(node, "要素2"); // 要素3の前に要素2を追加
        foreach (var item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

要素1
要素2
要素3

要素の逆順処理

LinkedListの要素を逆順に処理するには、各要素を一時的に保存し、逆順で新しいLinkedListに追加する方法があります。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("要素1");
        linkedList.AddLast("要素2");
        linkedList.AddLast("要素3");
        LinkedList<string> reversedList = new LinkedList<string>();
        foreach (var item in linkedList)
        {
            reversedList.AddFirst(item); // 逆順に追加
        }
        foreach (var item in reversedList)
        {
            Console.WriteLine(item);
        }
    }
}

要素3
要素2
要素1

要素の並び替え

LinkedListの要素を並び替えるには、要素を一時的に配列に格納し、並び替えた後に再度LinkedListに追加する方法が一般的です。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<int> linkedList = new LinkedList<int>();
        linkedList.AddLast(3);
        linkedList.AddLast(1);
        linkedList.AddLast(2);
        // LinkedListの要素を配列に格納
        int[] array = new int[linkedList.Count];
        linkedList.CopyTo(array, 0);
        
        // 配列を並び替え
        Array.Sort(array);
        // 並び替えた要素をLinkedListに追加
        LinkedList<int> sortedList = new LinkedList<int>();
        foreach (var item in array)
        {
            sortedList.AddLast(item);
        }
        foreach (var item in sortedList)
        {
            Console.WriteLine(item);
        }
    }
}

1
2
3

複数のLinkedListを結合する

複数のLinkedListを結合するには、AddLastメソッドを使用して、他のLinkedListの要素を一つずつ追加する方法があります。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        LinkedList<string> list1 = new LinkedList<string>();
        list1.AddLast("要素1");
        list1.AddLast("要素2");
        LinkedList<string> list2 = new LinkedList<string>();
        list2.AddLast("要素3");
        list2.AddLast("要素4");
        // list1にlist2の要素を追加
        foreach (var item in list2)
        {
            list1.AddLast(item);
        }
        foreach (var item in list1)
        {
            Console.WriteLine(item);
        }
    }
}

要素1
要素2
要素3
要素4

LinkedListのパフォーマンス

LinkedListは、特定の操作において非常に効率的ですが、他のデータ構造と比較した場合のパフォーマンス特性を理解することが重要です。

ここでは、挿入・削除の計算量、検索の計算量、メモリ使用量の特徴について解説します。

挿入・削除の計算量

LinkedListでは、要素の挿入や削除が非常に効率的です。

具体的には、以下のような計算量になります。

挿入: O(1)
リストの先頭または末尾に要素を追加する場合、ポインタの更新だけで済むため、定数時間で処理できます。
削除: O(1)
指定したノードを削除する場合も、ポインタの更新だけで済むため、定数時間で処理できます。

ただし、特定の位置に挿入または削除する場合は、その位置を見つけるためにO(n)の時間がかかることがあります。

検索の計算量

LinkedListにおける要素の検索は、リストの先頭から順にノードを辿っていく必要があるため、計算量は以下のようになります。

検索: O(n)
要素を見つけるためには、最悪の場合リストの全てのノードを確認する必要があるため、線形時間がかかります。

このため、LinkedListはランダムアクセスが必要な場合には不向きです。

メモリ使用量の特徴

LinkedListは、各ノードがデータと次のノードへの参照を持つため、メモリ使用量に関しては以下の特徴があります。

メモリオーバーヘッド: 各ノードにポインタが必要なため、配列やListに比べてメモリのオーバーヘッドが大きくなります。

特に、要素数が少ない場合は、オーバーヘッドが相対的に大きくなります。

動的メモリ管理: LinkedListは動的にメモリを確保するため、要素数が変動する場合に柔軟に対応できますが、メモリの断片化が発生する可能性があります。
メモリ使用量の計算: 各ノードが持つデータのサイズに加え、ポインタのサイズ(通常は4バイトまたは8バイト)を考慮する必要があります。

例えば、整数型のデータを持つLinkedListの場合、各ノードはデータのサイズ(4バイト)に加え、ポインタのサイズを持つため、合計で8バイトまたは12バイトのメモリを消費します。

このように、LinkedListは特定の操作において優れたパフォーマンスを発揮しますが、検索やメモリ使用量に関しては注意が必要です。

LinkedListを使った実践例

LinkedListは、その特性を活かしてさまざまなデータ構造や機能を実装するのに適しています。

ここでは、キュー、スタック、双方向リストを使ったナビゲーション、Undo/Redo機能の実装例を紹介します。

キューの実装

キューは、先入れ先出し(FIFO)方式で要素を管理するデータ構造です。

LinkedListを使用してキューを実装することができます。

using System;
using System.Collections.Generic;
class QueueExample
{
    private LinkedList<string> queue = new LinkedList<string>();
    public void Enqueue(string item)
    {
        queue.AddLast(item); // 末尾に要素を追加
    }
    public string Dequeue()
    {
        if (queue.Count == 0)
            throw new InvalidOperationException("キューが空です。");
        string value = queue.First.Value; // 先頭の要素を取得
        queue.RemoveFirst(); // 先頭の要素を削除
        return value;
    }
    public int Count => queue.Count; // 要素数を取得
}
class Program
{
    static void Main()
    {
        QueueExample queue = new QueueExample();
        queue.Enqueue("要素1");
        queue.Enqueue("要素2");
        Console.WriteLine(queue.Dequeue()); // 要素1を出力
        Console.WriteLine(queue.Dequeue()); // 要素2を出力
    }
}

要素1
要素2

スタックの実装

スタックは、後入れ先出し(LIFO)方式で要素を管理するデータ構造です。

LinkedListを使用してスタックを実装することができます。

using System;
using System.Collections.Generic;
class StackExample
{
    private LinkedList<string> stack = new LinkedList<string>();
    public void Push(string item)
    {
        stack.AddFirst(item); // 先頭に要素を追加
    }
    public string Pop()
    {
        if (stack.Count == 0)
            throw new InvalidOperationException("スタックが空です。");
        string value = stack.First.Value; // 先頭の要素を取得
        stack.RemoveFirst(); // 先頭の要素を削除
        return value;
    }
    public int Count => stack.Count; // 要素数を取得
}
class Program
{
    static void Main()
    {
        StackExample stack = new StackExample();
        stack.Push("要素1");
        stack.Push("要素2");
        Console.WriteLine(stack.Pop()); // 要素2を出力
        Console.WriteLine(stack.Pop()); // 要素1を出力
    }
}

要素2
要素1

双方向リストを使ったナビゲーション

双方向リストを使用すると、前後の要素に簡単にアクセスできるため、ナビゲーション機能を実装するのに適しています。

using System;
using System.Collections.Generic;
class NavigationExample
{
    private LinkedList<string> pages = new LinkedList<string>();
    private LinkedListNode<string> currentPage;
    public void AddPage(string page)
    {
        pages.AddLast(page); // ページを追加
        if (currentPage == null)
            currentPage = pages.First; // 最初のページを現在のページに設定
    }
    public string GoBack()
    {
        if (currentPage?.Previous != null)
        {
            currentPage = currentPage.Previous; // 前のページに移動
            return currentPage.Value;
        }
        return "前のページはありません。";
    }
    public string GoForward()
    {
        if (currentPage?.Next != null)
        {
            currentPage = currentPage.Next; // 次のページに移動
            return currentPage.Value;
        }
        return "次のページはありません。";
    }
}
class Program
{
    static void Main()
    {
        NavigationExample navigation = new NavigationExample();
        navigation.AddPage("ページ1");
        navigation.AddPage("ページ2");
        navigation.AddPage("ページ3");
        Console.WriteLine(navigation.GoBack()); // 前のページはありません。
        Console.WriteLine(navigation.GoForward()); // ページ2を出力
        Console.WriteLine(navigation.GoForward()); // ページ3を出力
        Console.WriteLine(navigation.GoBack()); // ページ2を出力
    }
}

前のページはありません。
ページ2
ページ3
ページ2

Undo/Redo機能の実装

Undo/Redo機能は、ユーザーの操作を取り消したり再実行したりするために、LinkedListを使用して実装できます。

using System;
using System.Collections.Generic;
class UndoRedoExample
{
    private LinkedList<string> actions = new LinkedList<string>();
    private LinkedListNode<string> currentAction;
    public void PerformAction(string action)
    {
        if (currentAction != null && currentAction.Next != null)
        {
            // 現在のアクションの後のアクションを削除
            var nextNode = currentAction.Next;
            while (nextNode != null)
            {
                var temp = nextNode;
                nextNode = nextNode.Next;
                actions.Remove(temp);
            }
        }
        actions.AddLast(action); // 新しいアクションを追加
        currentAction = actions.Last; // 現在のアクションを更新
    }
    public string Undo()
    {
        if (currentAction?.Previous != null)
        {
            currentAction = currentAction.Previous; // 前のアクションに移動
            return currentAction.Value;
        }
        return "Undoできるアクションはありません。";
    }
    public string Redo()
    {
        if (currentAction?.Next != null)
        {
            currentAction = currentAction.Next; // 次のアクションに移動
            return currentAction.Value;
        }
        return "Redoできるアクションはありません。";
    }
}
class Program
{
    static void Main()
    {
        UndoRedoExample undoRedo = new UndoRedoExample();
        undoRedo.PerformAction("アクション1");
        undoRedo.PerformAction("アクション2");
        undoRedo.PerformAction("アクション3");
        Console.WriteLine(undoRedo.Undo()); // アクション2を出力
        Console.WriteLine(undoRedo.Redo()); // アクション3を出力
    }
}