リンクリストの関連知識のまとめ

リンクリストとは? リンクリストは、物理記憶装置上の非連続かつ非順次の記憶構造であり、データ要素の論理的順序は、ポインタのリンク順序によって実現されます。リンクされたリストにあります。リンクリストは一連のノードで構成され (リンクリストの各要素はノードと呼ばれます)、ノードは実行時に動的に生成できます。各ノードは 2 つの部分で構成されます。1 つはデータ要素を格納するデータフィールドで、もう 1 つは次のノードのアドレスを格納するポインタフィールドです。

リンクリストと配列の違い

配列の概念を思い出してください。いわゆる配列は、特定の順序で配置された同じデータ型の要素の集合です。この概念によれば、配列はメモリ内で連続的ですが、リンクされたリストは連続的ではなく、格納方法が異なるため、配列は静的にメモリを割り当て、リンクされたリストは動的にメモリを割り当てます。配列要素はスタック領域にあり、リンクされたリスト要素はメモリ内にあります。ヒープ領域では配列が連続しているため、添字を使用して位置を特定できますが、リンクされたリスト内の要素の位置を特定する時間は O(n) です。配列の連続性、配列への要素の挿入または削除の時間計算量は O(n)、リンクリストの時間計算量は O(n) です。配列とリンクリストの違いをまとめると以下の通りです

1. 配列は静的にメモリを割り当て、リンクリストは動的にメモリを割り当てます

2. 配列はメモリ内で連続的ですが、リンクリストは不連続です
3. 配列要素はスタック内にあります領域、およびリンクされたリスト要素はヒープ領域にあります
4. 配列は添字を使用して配置され、時間計算量は O(1) です。リンクされたリスト内の要素を配置する時間計算量は O(n) です。配列内の要素の挿入または削除の計算量は O(n)、リンクされたリストの時間計算量は O(1) です。

C# はリンクリストの基本操作を実装します

単一リンクリストを例として、リンクリストの定義に従って、最初にリンクリストノードのデータ構造を定義します

    public class Node<T>
    {
        private T data;
        private Node<T> next;

        //有参构造函数
        //主要用例实例化需要处理的节点用
        public Node(T item, Node<T> next)
        {
            data = item;
            this.next = next;
        }

        //无参构造函数，用例实例化Node节点
        public Node()
        {
            data = default(T);
            next = null;
        }

        public Node<T> Next
        {
            get { return next; }
            set { this.next = value; }
        }

        public T Data
        {
            get { return data; }
            set { this.data = value; }
        }
    }

ログイン後にコピー

次に実装しますリンクリストの操作を実行し、リンクリストを構築します。構築されたリンクリストで、ヘッドノードのオブジェクトを定義します。これは、後続のコードで徐々に実現できます。リンクされたリストの長さを見つけます。アイデアは、最後のノードまでヘッドノードに逆方向にアクセスすることです。コードは次のとおりです。 2. リンクリストをクリアします。これは比較的単純で、ヘッドノードを設定するだけです。 null に設定する場合、コードは次のようになります

    public class MyLinkList<T>
    {
       public Node<T> Head { get; set; }

        //构造器  
        public MyLinkList()
        {
            Head = null;
        }
    }

ログイン後にコピー

3. 同様にリンクリストが空かどうかを判断しますヘッドノードも使用します

       public int Length()
        {
            var p = Head;
            int len = 0;
            while (p != null)
            {
                ++len;
                p = p.Next;
            }
            return len;
        }

ログイン後にコピー

4. リンクリストの最後に新しい要素を追加します。新しい要素を追加するには、まずリンクされたリストが空かどうかを判断する必要があります。空の場合は、ヘッドノードに値を割り当てる必要があります。空でない場合は、最後の要素の次のポイントを変更する必要があります。コードは次のとおりです

        public void Clear()
        {
            Head = null;
        }

ログイン後にコピー

5. 単一リンクリストの i 番目のノードの前に指定したノードを挿入します。まず、挿入位置を見つけてから、隣接するノードの点を変更する必要があります。つまり、はい、コードは次のとおりです

        public bool IsEmpty()
        {
            if (Head == null)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

ログイン後にコピー

6. 指定したノードを削除するには、まず削除する前のノードを見つけてから、ノードの次の点を変更します。コードは省略されています。。。。

・ 7. リンクリストにも削除、取得、検索などの操作がありますので、基本的な考え方は同じなので、一つ一つ紹介しません

リンクリストに関する古典的な質問

1. の数を求めます。単連結リストのノードを検索

2. 単連結リストを反転します

3. 単連結リストの最後から K 番目のノードを見つけます (k > 0)

4. 単連結リストの中間ノードを見つけます

5. 単一リンクリストを最後から先頭まで出力します

6. 2 つの単一リンクリスト pHead1 と pHead2 がそれぞれ順番にあることはすでにわかっています。それらを 1 つのリンクリストにマージしても、順番は変わりません

7. あるかどうかを確認します。単連結リストの循環

8. 2つの単連結リストが交差するかどうかを判定する