28

C# で循環リンク リストを作成する最良の方法は何でしょうか。LinkedList< T> コレクションから派生させる必要がありますか? この Linked List を使って連絡先を保存するための簡単なアドレス帳を作成する予定です (これは面倒なアドレス帳になりますが、使用するのは私だけなので気にしません)。私は主に、他のプロジェクトで再び使用できるように、決定的にリンクされたリストを作成したいだけです。

リンク リストが適切な方法でないと思われる場合は、どの方法がよいかお知らせください。

4

10 に答える 10

85

これらの回答のほとんどは実際には質問の内容に到達せず、意図にすぎないため、おそらくこれが役立ちます。

私が知る限り、リンク リストと循環リンク リストの唯一の違いは、リストの末尾または先頭に到達したときの反復子の動作です。循環リンク リストの動作をサポートする非常に簡単な方法は、リスト内の次のノードまたはそのようなノードが存在しない場合は最初のノードを返す LinkedListNode の拡張メソッドを作成することです。同様に、前のノードまたは最後のノードを取得します。そのようなノードが存在しない場合は 1 つ。私はテストしていませんが、次のコードはそれを達成するはずです:

static class CircularLinkedList {
    public static LinkedListNode<T> NextOrFirst<T>(this LinkedListNode<T> current)
    {
        return current.Next ?? current.List.First;
    }

    public static LinkedListNode<T> PreviousOrLast<T>(this LinkedListNode<T> current)
    {
        return current.Previous ?? current.List.Last;
    }
}

これで、myNode.Next の代わりに myNode.NextOrFirst() を呼び出すだけで、循環リンク リストのすべての動作が得られます。リスト内のすべてのノードの前後に、一定時間の削除や挿入を行うことができます。私が見逃している循環リンクリストの重要なビットが他にある場合は、お知らせください。

于 2010-04-19T19:29:42.870 に答える
5

BCL の LinkedList クラスから派生させるのは、おそらくお勧めできません。そのクラスは非循環リストになるように設計されています。循環させようとすると、問題が発生するだけです。

おそらく、自分で書いた方がはるかに良いでしょう。

于 2009-04-04T01:23:06.593 に答える
4

循環リンク リストは、連絡先リストの適切なデータ構造ではないと思います。単純な List<> または Collection<> で十分です。

于 2009-04-04T01:22:04.737 に答える
4

循環リンク リストを使用するための特定の要件はありますか (宿題など)? List<T>そうでない場合は、単純なクラスを使用して連絡先を保存することをお勧めします。

于 2009-04-04T01:23:31.007 に答える
3 
class CircularArray<T> : IEnumerator<T>
{
    private readonly T[] array;
    private int index = -1;
    public T Current { get; private set; }

    public CircularArray(T[] array)
    {
        Current = default(T);
        this.array = array;
    }

    object IEnumerator.Current
    {
        get { return Current; }
    }

    public bool MoveNext()
    {
        if (++index >= array.Length)
            index = 0;
        Current = array[index];
        return true;
    }

    public void Reset()
    {
        index = -1;
    }

    public void Dispose() { }
}
于 2012-02-26T19:18:13.817 に答える
3

循環リンク リストは配列を使用して実装されることが多く、非常に高速であり、その性質上、動的なサイズ変更は必要ありません。読み取りインデックスと書き込みインデックスを簡単にチェックして、最後から外れていないかどうかを確認し、そうであればゼロ (または 1 など) にリセットする必要があります。

ただし、これらは通常、一度読み取ったデータには実際の値がない入力バッファーなどに使用されます。連絡先リストには永続的な価値があり、リストがいっぱいになると新しい連絡先が古い連絡先を上書きします。

リンクされたリストが循環バッファーを使用するための最も効率的な方法であるとは思いません (元の質問)。

循環バッファの目的は速度であり、循環バッファのコンテキストでは配列の速度に勝るものはありません。最後にアクセスしたリンク リスト項目へのポインターを保持していても、配列の方が効率的です。リストには、循環バッファーには不要な動的サイズ変更機能 (オーバーヘッド) があります。そうは言っても、あなたが言及したアプリケーション（連絡先リスト）にとって、循環バッファはおそらく正しい構造ではないと思います。

于 2009-04-04T02:52:04.677 に答える
2

弾性率ベースのソリューション。

循環バッファが生の配列として実装されている場合 (または重要な他の種類のコレクション)

T[] array;

現在のアイテムのインデックスに保存するint current_indexと、次のようにバッファを上下に循環できます。

T NextOrFirst()
{
    return array[(current_index + 1) % array.Length];
}

T PreviousOrLast()
{
    return array[(current_index + array.Length - 1) % array.Length];
}

任意の XAML バインディング コレクションで同じアプローチを使用できます。

于 2016-05-19T08:38:46.900 に答える
1

このCList ベースの循環リストはどうですか。

于 2009-04-04T01:24:31.863 に答える
0

この問題の最も正しいデータ構造は、循環二重リンクリストだと思います。このデータ構造を使用すると、連絡先リストを自由に上下に移動できます

于 2011-11-13T01:34:43.503 に答える
0 
class Program
{
    static void Main(string[] args)
    {
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7 };

        IEnumerable<int> circularNumbers = numbers.AsCircular();

        IEnumerable<int> firstFourNumbers = circularNumbers
            .Take(4); // 1 2 3 4

        IEnumerable<int> nextSevenNumbersfromfourth = circularNumbers
            .Skip(4).Take(7); // 4 5 6 7 1 2 3 
    }
}

public static class CircularEnumerable
{
    public static IEnumerable<T> AsCircular<T>(this IEnumerable<T> source)
    {
        if (source == null)
            yield break; // be a gentleman

        IEnumerator<T> enumerator = source.GetEnumerator();

        iterateAllAndBackToStart:
        while (enumerator.MoveNext()) 
            yield return enumerator.Current;

        enumerator.Reset();
        if(!enumerator.MoveNext())
            yield break;
        else
            yield return enumerator.Current;
goto iterateAllAndBackToStart;
    }
}

さらに進みたい場合はCircularList、同じ列挙子を作成して保持Skip()し、サンプルのように回転するときにスキップします。

于 2012-03-31T04:09:22.090 に答える