Javaデータ構造のチェーンの添削を詳しく説明します。

一、チェーンの概念と構造
1.1チェーンの概念
簡単に言えば、チェーンは物理的に必ずしも連続しないが、論理的に一定の連続したデータ構造である。
1.2チェーンの分類
実際にはチェーンの構造が非常に多様で、以下の状況を組み合わせると、8つのチェーン構造があります。一方通行と双方向、先頭と非先頭、循環と非循環があります。配列の組み合わせと8種類があります。
しかし、私はこの二つの比較的難しいリンク表を実現するだけです。理解してから他の6つのタイプは比較的簡単です。
1.一方通行で率先しない非循環チェーン表
2.双方向が率先しない非循環チェーン表
二、一方通行で率先しないと循環チェーン表ではない。

2.1ノードタイプを作成する
私たちはListNodeクラスをノードタイプとして作成しました。中には2つのメンバー変数があります。valは数値を格納するために、nextは次のノードのアドレスを保存します。
もう一つのパラメータを持つ構造方法があります。実際のオブジェクトをvalに割り当てながら、次のノードのアドレスが分かりませんので、nextはデフォルトのnullです。

class ListNode {
    public int val;//  
    public ListNode next;//        

    public ListNode(int val) {
        this.val = val;
    }
}

私達はMyLinkdListの中でhead変数を作ってチェーンの頭を識別します。そしてシングルチェーンの添削を実現します。

2.2ヘッド挿入法
このヘッド挿入法は初めて挿入することを考慮しないでください。挿入するたびに、挿入するノードのnodeのnext値をヘッドノードに変えて、またヘッドノードをnodeに指します。

//   
public void addFirst(int data) {
    ListNode node = new ListNode(data);
    node.next = this.head;
    this.head = node;
}

2.3テールプラグ法
最後の挿し方はまず第1回が挿入するのではないかと考えます。もしそうなら、直接にheadをnodeに指したらいいです。初めて挿入しないなら、curを定義して尻尾のノードを探して、尻尾のノードのnext値をnodeに変えたらいいです。テイルノードがないとヘッドが見えなくなるからです。

//   
public void addLast(int data) {
    ListNode node = new ListNode(data);
    ListNode cur = this.head;
    //     
    if(this.head == null) {
        this.head = node;
    }else{
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

2.4チェーンの長さを取得する
カウンタcountを定義して、curがチェーンを遍歴した時に直接countに戻るといいです。

//        
public int size() {
    int count = 0;
    ListNode cur = this.head;
    while (cur != null) {
        cur = cur.next;
        count++;
    }
    return count;
}

2.5任意の位置に挿入する
チェーンの頭は0の位置から始まると仮定します。任意の位置に挿入するには何点を考慮する必要がありますか？
1.位置の合法性は、位置が0未満、またはチェーンの長さより大きい場合、位置が合法的ではない。
2.挿入するのが0の位置であれば、直接にヘッドセットを使用します。
3.挿入された位置がチェーンの長さに等しいなら、最後の挿入法を使います。このチェーンは0から始まります。
最も重要なのは、中間位置から挿入するには、挿入する前のノードの位置を見つける必要があります。それらの間に挿入します。

  /**
     *   cur     index - 1  
     * @param index
     * @return
     */
public ListNode findIndexSubOne(int index) {
    int count = 0;
    ListNode cur = this.head;
    while (count != index-1) {
        cur = cur.next;
        count++;
    }
    return  cur;
}
//      ,        0   
public void addIndex(int index,int data) {
    //     
    if(index < 0 || index > size()) {
            System.out.println("index     ");
            return;
    }
    //   
    if(index == 0) {
        this.addFirst(data);
        return;
    }
    //   
    if(index == size()) {
        this.addLast(data);
        return;
    }
    //   ,cur     index       
    ListNode cur = findIndexSubOne(index);
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = node;
}

2.6検索キーワード
チェーンテーブルにキーワードがあるかどうかを検索するには、最初から巡回するという定義が必要です。

//         key        
public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

2.7最初の出現値がkeyであるノードを削除する。
この考え方は実は簡単です。二つの状況を考慮すればいいです。
1.削除するのがヘッドノードなら、ヘッドノードだけをノードに向けるだけでいいです。
2.keyが存在しない場合もあるので、keyが存在するかどうかを判断する方法をここに書いています。存在するなら、keyの前のノードの位置に戻ります。
3.存在すると削除するノードの前駆のnextをそのnextに変更すればいいです。

/**
  *      key       
 * @return
 */
public ListNode searchPrev(int key) {
    ListNode prev = this.head;
    while (prev.next != null) {
        if (prev.next.val == key) {
            return prev;
        }
        prev = prev.next;
    }
    return null;
}
//           key   
public void remove(int key) {
    if(this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    //  key      
    ListNode prev = searchPrev(key);
    if(prev == null) {
        System.out.println("  key     ");
        return;
    }
    //  
    ListNode delete = prev.next;
    prev.next = delete.next;
}

2.8全ての値がkeyであるノードを削除する。

削除するものが3である場合、考え方:
二つのノードポイントタイプの変数を定義し、prevはheadを指し、curはheadの次のノードを指す。
curのval値が削除される値であると判定された場合、もしそうでなければ、直接にこのノードをスキップし、prevとcurをバックにして、チェーン全体が巡回されるまで前進させる。
最後に、ヘッドノードが巡回されていないことが分かります。ループが終了すると、ヘッドノードが削除されるべきノードかどうかを判断する必要があります。
必ず絵を描きながらコードを書くことを覚えてください。

//      key   
public void removeAllKey(int key) {
    ListNode prev = this.head;
    ListNode cur = this.head.next;
    while (cur != null) {
        if(cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        }else {
            prev = cur;
            cur = cur.next;
        }
    }
    //                
    if(this.head.val == key) {
        this.head = this.head.next;
    }
}

2.9巡回印刷チェーン表
curを定義して直接的に巡回印刷すればいいです。

//    
public void display() {
    ListNode cur = this.head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

空チェーンをセットする
チェーンを空にするには一つずつ置いてもいいです。直接にヘッドノードを空にするという暴力的なやり方は勧められません。

//    
public void clear() {
    ListNode cur = this.head;
    //     
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.next = null;
        cur = curNext;
    }
    this.head = null;
}

三、双方向が率先しないと循環チェーン表ではない。
双方向チェーンと一方向チェーンの最大の違いは、前駆ノードprevが一つ多くなり、同様に双方向チェーンの添削を実現することである。

public class TestLinkedList {
    public ListNode head;
    public ListNode last;
}

3.1ノードタイプを作成する
同様に、先にノードタイプを定義し、一方向チェーンより一つの前駆ノードが多くなっただけです。

class ListNode {
    public int val;
    public ListNode prev;
    public ListNode next;

    public ListNode (int val) {
        this.val = val;
    }
}

双方向チェーンテーブルはまた、リードノードを識別するためにlastを定義し、一方、シングルチェーンテーブルはヘッドノードを識別するだけである。

3.2ヘッド挿入法
これは双方向リンクなので、headとlastを同時に最初のノードに向けて挿入するのは初めてです。
初めて挿入しないと、必要です。
1.headの前駆ノードをnodeに変更し、
2.nodeのnextをheadに変更します。
3.そしてヘッドノードheadが新しいヘッドノードnodeを指す。

//   
public void addFirst(int data) {
    ListNode node = new ListNode(data);
    //     
    if(this.head == null) {
        this.head = node;
        this.last = node;
    }else {
        head.prev = node;
        node.next = this.head;
        this.head = node;
    }
}

3.3テール挿入法
双方向チェーンはlastを持っていて、尻尾ノードを識別しますので、最後に挿入する時はしっぽノードを探さなくてもいいです。ヘッドセットと似ています

//   
public void addLast(int data) {
    ListNode node = new ListNode(data);
    //     
    if(this.head == null) {
        this.head = node;
        this.last = node;
    }else {
        this.last.next = node;
        node.prev = this.last;
        this.last = node;
    }
}

3.4チェーンの長さを取得する
これはシングルチェーンと同じで、直接にキュール遍歴を定義します。

//       
public int size() {
    ListNode cur = this.head;
    int count = 0;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

3.5任意の位置に挿入する
任意の位置に挿入する場合も、シングルチェーンテーブルと同様に3つの場合があります。適法性とプラグの挿入が多くないと判断します。主に中間でランダムに挿入します。修正の順番に注意してください。
修正するところは全部で四つあります。必ず図面を描いて理解してください。

//          
public ListNode searchIndex(int index) {
    ListNode cur = this.head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    return  cur;
}
//      ,        0   
public void addIndex(int index,int data) {
    //  index      
    if(index < 0 || index > this.size()) {
        System.out.println("index      ");
        return;
    }
    //   
    if(index == 0) {
        this.addFirst(data);
        return;
    }
    //   
    if(index == this.size()) {
        this.addLast(data);
        return;
    }
    //    
    ListNode node = new ListNode(data);
    ListNode cur = searchIndex(index);
    node.next = cur;
    node.prev = cur.prev;
    cur.prev.next = node;
    cur.prev = node;
}

3.6キーワードを検索する
ここはシングルチェーンと同じです。直接にキュールを定義してチェーンの中にこの値があるかどうか見てください。

//         key        
public boolean contains(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

3.7最初に出現したキーワードkeyのノードを削除する
考え方：チェーンを通して初めてのノードを探して、returnを削除します。全部で三つの状況に分けられます。
1.ヘッドノードは削除するノードである。
2.尻尾ノードは削除するノードです。
3.中間ノードは削除するノードである。

//           key   
public void remove(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            //        
            if(this.head == cur) {
                this.head = this.head.next;
                this.head.prev = null;
            }else {
                //              
                cur.prev.next = cur.next;
                if(this.last == cur) {
                    //      
                    cur = cur.prev;
                }else {
                    cur.next.prev = cur.prev;
                }
            }
            //     
            return;
        }else {
            cur = cur.next;
        }
    }
}

3.8全ての値がkeyであるノードを削除する。
考え方はkeyの削除と似ていますが、2つの点に注意が必要です。
1.削除が終わったら、returnではなく、後に行くのです。ここではすべてを削除してkeyのためにリストを巡回しなければならないからです。
2.また、チェーン全体が削除される場合を考慮して、ifで判断してください。空の指針に異常が発生します。

//      key   
public void removeAllKey(int key) {
    ListNode cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            //        
            if(this.head == cur) {
                this.head = this.head.next;
                //           
                if(this.head != null) {
                    this.head.prev = null;
                }else {
                 //             
                 this.last = null;
                }
            }else {
                //              
                cur.prev.next = cur.next;
                if(this.last == cur) {
                    //      
                    cur = cur.prev;
                }else {
                    cur.next.prev = cur.prev;
                }
            }
            //   
            cur = cur.next;
        }else {
            cur = cur.next;
        }
    }
}

3.9巡回印刷チェーン表

//    
public void display() {
    ListNode cur = this.head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

空チェーンをセットする
チェーンを通して一つずつnullにして、頭のノードと尾のノード値はnullです。メモリの漏えいを防ぐ

//    
public void clear() {
    ListNode cur = this.head;
    //      
    while (cur != null) {
        ListNode curNext = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = curNext;
    }
    this.head = null;
    this.last = null;
}

四、まとめ
1.ここでは2つの比較的難しいチェーン表を実現しました。一方通行でリードしないと循環しないと双方向でリードしないと循環しないです。
2.チェーンは物理的には必ずしも連続していないが、論理的には一定の連続性がある。
3.増加：チェーンを挿入すると、指差を修正するだけで、時間の複雑さはO（1）です。
4：削除：チェーンは要素を削除します。同じ方向を修正するだけで、時間の複雑さはO（1）です。
5.チェック：チェーンが一つの要素を検索するにはチェーンを巡回する必要がありますので、時間の複雑さはO（n）です。
6.改：チェーンは修正する要素を見つけますので、時間の複雑度はO（n）です。
チェーンはいつ使いますか？
挿入と削除が頻繁な場合は、チェーンを使います。注意：移動データに触れない場合です。
ここで、Javaデータ構造の連鎖表の添削について詳しく解説した文章を紹介します。Javaチェーンの内容については以前の文章を検索してください。または下記の関連記事を引き続きご覧ください。これからもよろしくお願いします。