リンクリストとは何ですか?リンクリストと配列の違いは何ですか?

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

リンク リストとは? リンク リストは、物理記憶装置上の非連続かつ非順次の記憶構造であり、データ要素の論理的順序は、ポインタのリンク順序によって実現されます。リンクされたリストにあります。リンク リストは一連のノードで構成され (リンク リストの各要素はノードと呼ばれます)、ノードは実行時に動的に生成できます。各ノードは 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つの単連結リストが交差するかどうかを判定する

9. 2つの単連結リストを見つける 交差する最初のノード

10. 単連結リストに環があることがわかっているので、最初のノードを見つけるリングに入るノード

11. 単結合リストヘッドポインタ pHead とノードポインタ pToBeDeleted を指定すると、時間計算量は O(1) 削除度ノード pToBeDeleted

さて、質問はここまでにします。ご質問があればお答えできます

以上がリンクリストとは何ですか?リンクリストと配列の違いは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。