[C#] 連結リストを自前で実装する方法

連結リストを自前で実装する

連結リストとは

連結リスト – Wikipedia

連結リスト (Linked List) とは基本的なデータ構造の1つです。配列のようなインデックスで順序が決まるのではなく、各オブジェクトが持つポインタによって順序を決めるデータ構造です。

連結リストにはいくつかの種類があります。一方向と双方向、循環と非循環などです。今回実装していくのは 双方向連結リスト です。

双方向連結リスト

双方向連結リストの各要素(ノード)は格納する値と2つのポインタ(Next, Prev)を持ちます。ノード x について x.Next が次のノード、x.Prev が直前のノードを指します。

双方向連結リストは先頭ノードと末尾ノードを保持します。こうすることで先頭、末尾に追加や削除を O(1) で実現できます。

C# だと LinkedList<T> として標準ライブラリで提供されています。が勉強のために実装していきます。

実装

using System;
using System.Collections;
using System.Collections.Generic;

public class LinkedList<T> : IEnumerable<T>
{
    private LinkedListNode<T> Dummy;
    public LinkedListNode<T> First => this.Dummy.Next;
    public LinkedListNode<T> Last => this.Dummy.Previous;
    public int Length { get; private set; }

    public LinkedList()
    {
        this.Dummy = new LinkedListNode<T>();
        this.Dummy.Next = this.Dummy;
        this.Dummy.Previous = this.Dummy;
    }

    public LinkedListNode<T> Find(T x)
    {
        var node = this.First;
        while (node != null && !EqualityComparer<T>.Default.Equals(node.Value, x))
        {
            node = node.Next;
        }
        return node;
    }

    public void InsertAfter(LinkedListNode<T> node, T value)
    {
        var newNode = new LinkedListNode<T>();
        newNode.Value = value;
        newNode.Next = node.Next;
        newNode.Previous = node;

        node.Next.Previous = newNode;
        node.Next = newNode;

        this.Length += 1;
    }

    public void InsertBefore(LinkedListNode<T> node, T value)
    {
        var newNode = new LinkedListNode<T>();
        newNode.Value = value;
        newNode.Next = node;
        newNode.Previous = node.Previous;

        node.Previous.Next = newNode;
        node.Previous = newNode;

        this.Length += 1;
    }

    public void AddFirst(T value) => this.InsertBefore(this.First, value);
    public void AddLast(T value) => this.InsertAfter(this.Last, value);

    public void Remove(LinkedListNode<T> node)
    {
        node.Previous.Next = node.Next;
        node.Next.Previous = node.Previous;

        this.Length -= 1;
    }

    public IEnumerator<T> GetEnumerator()
    {
        var node = this.First;
        while (node != this.Dummy)
        {
            yield return node.Value;
            node = node.Next;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

public class LinkedListNode<T>
{
    public LinkedListNode<T> Next { get; internal set; }
    public LinkedListNode<T> Previous { get; internal set; }
    public T Value { get; set; }
}

番兵

非循環の連結リストの場合、挿入や削除を行う際に先頭と末尾の境界条件を判定していい感じに処理しなければなりません。そこで番兵を使った双方向循環リストにしておくのがいいやり方です。

番兵は先頭と末尾をつなぐダミーノード(Dummy)です。ダミーノードの次の要素は先頭ノード、前のノードは末尾のノードを指すようにします。この連結リストが循環するようになります。

先頭 <-------> 末尾
 ↑↓             ↓↑
 -----ダミー-----

初期状態ではダミーノードの Next も Prev もダミーノード自身を指すようにします。

Find – 連結リストを探索する

連結リストから指定した値に一致するノードを返します。連結リストについては先頭からたどりながら一致する値が入っているノードを見つけます。

末尾のノードはダミーノードを介して循環しているのでダミーノードを見つけたら終了とします。

public LinkedListNode<T> Find(T x)
{
    var node = this.First;
    while (node != null && !EqualityComparer<T>.Default.Equals(node.Value, x))
    {
        node = node.Next;
    }
    return node;
}

比較には EqualityComparer<T>.Default.Equals() を使います。

EqualityComparer Class (System.Collections.Generic) | Microsoft Docs

プロパティDefaultは、型TがSystem.IEquatable IEquatable.Equals ジェネリックEqualityComparerインターフェイスを実装しているかどうかを確認し、存在する場合は、メソッドの実装を呼び出すを返します。 それ以外の場合はEqualityComparer、によっTて提供されるを返します。

Insert – 挿入

// 引数で渡したノードの直後に挿入
public void InsertAfter(LinkedListNode<T> node, T value)
{
    var newNode = new LinkedListNode<T>();
    newNode.Value = value;
    newNode.Next = node.Next;
    newNode.Previous = node;

    node.Next.Previous = newNode;
    node.Next = newNode;

    this.Length += 1;
}
// 引数で渡したノードの直前に挿入
public void InsertBefore(LinkedListNode<T> node, T value)
{
    var newNode = new LinkedListNode<T>();
    newNode.Value = value;
    newNode.Next = node;
    newNode.Previous = node.Previous;

    node.Previous.Next = newNode;
    node.Previous = newNode;

    this.Length += 1;
}

// 先頭と末尾にデータを追加
public void AddFirst(T value) => this.InsertBefore(this.First, value);
public void AddLast(T value) => this.InsertAfter(this.Last, value);

挿入については、挿入するノードの場所がわかっていれば簡単です。慎重に書き換えれば間違わずにできると思います。

特定のノードの直前直後に挿入する方法がわかれば先頭末尾にデータを追加するのも簡単です。

Remove – 削除

public void Remove(LinkedListNode<T> node)
{
    node.Previous.Next = node.Next;
    node.Next.Previous = node.Previous;

    this.Length -= 1;
}

指定したノードを連結リストから削除する方法は上記の通りです。番兵があるためNULL参照を起こす心配がありません。各ノードの Prev Next には必ず別ノード(あるいはダミーノード)への参照が入っています。

以上。