23

単純なコードだと思うでしょう

llist1.Last.Next = llist2.First;
llist2.First.Previous = llist1.Last;

動作しますが、明らかに C# の LinkedList では、First、Last、およびそれらのプロパティは Get のみです。

私が考えることができる他の方法は

llist1.AddLast(llist2.First);

ただし、これも機能しません。llist2 の最初のノードが既にリンクされたリストにあるため、失敗します。

これは、llist2 の各ノードを llist1 に手動で AddLast するループが必要ということですか? これは連結リストの効率を損ないませんか????

4

3 に答える 3

18

はい、残念ながらループする必要があります。これは O(n) 操作です - 追加されたエントリごとに O(1)。バッファのサイズ変更やコピーなどを必要とするリスクはありません - もちろん、ガベージ コレクションは大まかにそれを行うかもしれませんが:) 便利な拡張メソッドを書くことさえできます:

public static class LinkedListExtensions   
{
    public static void AppendRange<T>(this LinkedList<T> source,
                                      IEnumerable<T> items)
    {
        foreach (T item in items)
        {
            source.AddLast(item);
        }
    }

    public static void PrependRange<T>(this LinkedList<T> source,
                                       IEnumerable<T> items)
    {
        LinkedListNode<T> first = source.First;
        // If the list is empty, we can just append everything.
        if (first is null)
        {
            AppendRange(source, items);
            return;
        }

        // Otherwise, add each item in turn just before the original first item
        foreach (T item in items)
        {
            source.AddBefore(first, item);
        }
    }
}

編集: Erich のコメントは、これが非効率的であると考える理由を示唆しています。最初のリストの末尾の「次の」ポインターと 2 番目の先頭の「前の」ポインターを更新して、2 つのリストを結合しないのはなぜですか? さて、2 番目のリストがどうなるか考えてみてください...それも変わっていたでしょう。

それだけでなく、それらのノードの所有権はどうなりますか? それぞれが本質的に 2 つのリストの一部になりました... しかし、LinkedListNode<T>.Listプロパティはそれらの 1 つについてのみ話すことができます。

場合によってはこれを行う理由はわかりますが、.NETLinkedList<T>型が構築された方法では、基本的に禁止されています。このドキュメントのコメントが最もよく説明していると思います：

このLinkedList<T>)クラスは、連鎖、分割、循環、またはリストを一貫性のない状態にする可能性のあるその他の機能をサポートしていません。

于 2009-07-07T19:57:04.207 に答える
8 
llist1 = new LinkedList<T>(llist1.Concat(llist2));

これにより、2つのリストが連結されます（.NET 3.5が必要です）。欠点は、LinkedListの新しいインスタンスが作成されることです。これは、希望するものではない可能性があります...代わりに次のようなことを行うことができます。

foreach(var item in llist2)
{
    llist1.AddLast(item);
}
于 2009-07-07T19:52:42.750 に答える
5

ここでは、O(1) 連結および分割時間を使用した連結リストの実装を見つけることができます。

.NET LinkedList が Concat および Split 操作をサポートしないのはなぜですか?

短い要約

利点 vs .NET LinkedList:

  • メモリ消費量が少ないため、すべてのノード SimpleLinkedListNode には、元の .NET 実装とは異なり、4 つのポインター (前、次、リスト、値) ではなく 3 つのポインター (前、次、値) があります。

  • O(1) での Concat および Split 操作をサポート

  • O(1) で IEnumarable Reverse() 列挙子をサポートします。ちなみに、.NET LinkedList でネイティブに提供されていない理由はわかりません。適切な拡張方法には O(n) が必要です。

短所:

  • カウントをサポートしていません。
  • 連結操作により、2 番目のリストが一貫性のない状態のままになります。
  • 分割操作により、元のリストが一貫性のない状態のままになります。
  • リスト間でノードを共有できます。

他の：

  • より冗長で純粋に読みやすい元の実装ではなく、列挙および検索操作を実装するための代替戦略を選択しました。パフォーマンスへの悪影響が軽微であることを願っています。
于 2011-07-18T13:47:44.797 に答える