Java プログラミング スキル - データ構造とアルゴリズム「単方向リンク リスト」

[[386512]]

基本的な紹介

リンクリストは順序付きリストですが、メモリ内に次のように保存されます。

1. リンクリストはノードの形式で保存されます。
2. 各ノードにはデータ フィールドと次のフィールド (次のノードを指す) が含まれます。
3. 図に示すように、各リンクリストのノードは必ずしも連続して格納されるわけではないことがわかります。
4. リンク リストは、ヘッド ノードを持つリンク リストとヘッド ノードを持たないリンク リストに分けられ、実際のニーズに応じて決定されます。

単連結リストの紹介

単一リンクリスト（ヘッドノード付き）の論理構造図は次のようになります。

単連結リストの応用例

ヘッド付きの一方向リンクリストを使用してウォーター・マージンヒーローランキング管理を実装する

パッケージ com.structures.linkedlist; 
 
パブリッククラスSingleLinkedListDemo {
公共 静的void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "Song Jiang" , "Timely Rain" );
        HeroNode heroNode2 = new HeroNode(2, "Lu Junyi" , "Yu Qilin" );
        HeroNode heroNode3 = new HeroNode(3, "Wu Yong" , "Zhi Duo Xing" );
        HeroNode heroNode4 = new HeroNode(4, "Lin Chong" , "Leopard Head" );
        シングルリンクリスト singleLinkedList = 新しいシングルリンクリスト();
        シングルリンクリストを追加します(heroNode3);
        シングルリンクリストを追加します(heroNode2);
        シングルリンクリストを追加します(heroNode4);
        単一のLinkedListを追加します(heroNode1);
        シングルリンクリスト.list();
    }
 } 
 
 //ヒーローを管理するためにSingleLinkedListを定義する
クラスSingleLinkedList {
    //まずヘッドノードを初期化します。ヘッドノードは移動できず、将来のトラバーサルに使用されます。
    プライベートHeroNodeヘッド = 新しいHeroNode(0, "" , "" ); 
 
    // 単一リンクリストにノードを追加する
    // アイデア: 数字の順序を考慮しない場合
    //1. 現在のリンクリストの最後のノードを見つける
    //2. 最後のノードの次のフィールドを新しいノードにポイントする
パブリックvoid追加(HeroNode ノード) {
        //ヘッドノードは移動できないため、補助的なトラバーサルテンポが必要です 
        HeroNode temp = ヘッド;
        //リンクリストを走査して最後の
        while ( temp . next != null ) {
            // リンクリストの末尾を見つける
            // tempが見つからない場合は戻る
temp = temp . next ;
        }
 temp . next = ノード;
    } 
 
    //リンクリストを表示する [トラバーサル]
パブリックボイドリスト（）{
        // リンクリストが空かどうか確認する
        （ head.next == nullの場合）{
            System.out.println ( "リンクリストは空です" );
        }
        //ヘッドノードは移動できないため、トラバースするための補助変数が必要です
        HeroNode temp = head.next ;
        while ( temp != null ) {
            //終了かどうか判断する
            // 出力ノード情報
            System.out.println ( temp ) ;
            //温度を戻す
temp = temp . next ;
        }
    }
 } 
 
 //HeroNodeを定義します。各HeroNodeオブジェクトはノードです
クラスHeroNode {
公共 整数 いいえ;
パブリック文字列名;
パブリック文字列ニックネーム;
 public HeroNode next ;//次のノードを指す
 
    //コンストラクタ
パブリックHeroNode( int   no 、String name 、String nickName) {
        this.no =いいえ;
        this.name =名前;
        this.nickName = ニックネーム;
    } 
 
パブリックHeroNode getNext() {
戻る 次;
    } 
 
パブリックvoid setNext(HeroNode next ) {
        this.next =次へ;
    } 
 
    @オーバーライド
パブリック文字列toString() {
戻る  「ヒーローノード{" +
 「いいえ=」 +いいえ+
 ", 名前='" +名前+ '\ '' +
 ", ニックネーム='" + ニックネーム + '\ '' +
 '}' ;
    }
 }
 /*
 HeroNode{ no =3、 name = 'Wu Yong' 、 nickName= 'Smart Star' }
 HeroNode{ no =2、 name = 'Lu Junyi' 、 nickName= 'Yu Qilin' }
 HeroNode{ no =4、 name = 'Lin Chong' 、 nickName= 'Leopard Head' }
 HeroNode{ no =1、 name = 'Song Jiang' 、 nickName= 'Timely Rain' }
 */

上記のリンク リストの実装では、ヒーローを追加するときに番号で並べ替えられないことがわかります。ヒーローを挿入するときに番号で並べ替えるように add メソッドを書き直してみましょう。

パッケージ com.structures.linkedlist; 
 
パブリッククラスSingleLinkedListDemo {
公共 静的void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "Song Jiang" , "Timely Rain" );
        HeroNode heroNode2 = new HeroNode(2, "Lu Junyi" , "Yu Qilin" );
        HeroNode heroNode3 = new HeroNode(3, "Wu Yong" , "Zhi Duo Xing" );
        HeroNode heroNode4 = new HeroNode(4, "Lin Chong" , "Leopard Head" );
        シングルリンクリスト singleLinkedList = 新しいシングルリンクリスト();
        単一のLinkedList.addByNo(heroNode3);
        単一のLinkedList.addByNo(heroNode2);
        単一のLinkedList.addByNo(heroNode4);
        単一のLinkedList.addByNo(heroNode1);
        シングルリンクリスト.list();
    }
 } 
 
 //ヒーローを管理するためにSingleLinkedListを定義する
クラスSingleLinkedList {
    //まずヘッドノードを初期化します。ヘッドノードは移動できず、将来のトラバーサルに使用されます。
    プライベートHeroNodeヘッド = 新しいHeroNode(0, "" , "" ); 
 
    // 単一リンクリストにノードを追加する
    // アイデア: 数字の順序を考慮しない場合
    //1. 現在のリンクリストの最後のノードを見つける
    //2. 最後のノードの次のフィールドを新しいノードにポイントする
パブリックvoid追加(HeroNode ノード) {
        //ヘッドノードは移動できないため、補助的なトラバーサルテンポが必要です 
        HeroNode temp = ヘッド;
        //リンクリストを走査して最後の
        while ( temp . next != null ) {
            // リンクリストの末尾を見つける
            // tempが見つからない場合は戻る
temp = temp . next ;
        }
 temp . next = ノード;
    } 
 
    //ヒーローを追加する2番目の方法は、ヒーローを追加するときに、ランキングに従って指定された位置にヒーローを挿入します
    //そのような順位がある場合、追加は失敗し、プロンプトが表示されます
パブリックvoid addByNo(HeroNode heroNode) {
        //ヘッドノードは移動できないため、補助的なトラバーサルテンポが必要です 
        //これは単一のリンクリストなので、探している一時ノードは追加された位置の前のノードです。そうでなければ追加できません。
        HeroNode temp = ヘッド;
        ブール型フラグ = false ; // 追加された番号が存在するかどうかを示します。デフォルトはfalseです 
        （真）の間{
            if ( temp . next == null ) {
                壊す;
            }
            if ( temp . next . no > heroNode. no ) { //位置が見つかったら、 tempの後に挿入します
                壊す;
            }そうでない場合 ( temp . next . no == heroNode . no ) {
                //番号はすでに存在します
                フラグ = true ;
                壊す;
            }
 temp = temp . next ;
        }
        if (フラグ) {
            System.out.printf ( "挿入するヒーロー番号%dはすでに存在するため、追加できません\n" 、 heroNode.no );
        }それ以外{
            //リンクリストの後ろに挿入temp
            ヒーローノードの次のコード
temp . next = heroNode;
        }
    } 
 
    //リンクリストを表示する [トラバーサル]
パブリックボイドリスト（）{
        // リンクリストが空かどうか確認する
        （ head.next == nullの場合）{
            System.out.println ( "リンクリストは空です" );
        }
        //ヘッドノードは移動できないため、トラバースするための補助変数が必要です
        HeroNode temp = head.next ;
        while ( temp != null ) {
            //終了かどうか判断する
            // 出力ノード情報
            System.out.println ( temp ) ;
            //温度を戻す
temp = temp . next ;
        }
    }
 } 
 
 //HeroNodeを定義します。各HeroNodeオブジェクトはノードです
クラスHeroNode {
公共 整数 いいえ;
パブリック文字列名;
パブリック文字列ニックネーム;
 public HeroNode next ;//次のノードを指す
 
    //コンストラクタ
パブリックHeroNode( int   no 、String name 、String nickName) {
        this.no =いいえ;
        this.name =名前;
        this.nickName = ニックネーム;
    } 
 
パブリックHeroNode getNext() {
戻る 次;
    } 
 
パブリックvoid setNext(HeroNode next ) {
        this.next =次へ;
    } 
 
    @オーバーライド
パブリック文字列toString() {
戻る  「ヒーローノード{" +
 「いいえ=」 +いいえ+
 ", 名前='" +名前+ '\ '' +
 ", ニックネーム='" + ニックネーム + '\ '' +
 '}' ;
    }
 }
 /*
 HeroNode{ no =1、 name = 'Song Jiang' 、 nickName= 'Timely Rain' }
 HeroNode{ no =2、 name = 'Lu Junyi' 、nickName= 'Yu Qilin' }
 HeroNode{ no =3、 name = 'Wu Yong' 、 nickName= 'Smart Star' }
 HeroNode{ no =4、 name = 'Lin Chong' 、nickName= 'Leopard Head' }
 */

機能を再度改善し、ノードを変更する機能を追加

//番号に応じてノード情報を変更します。つまり、番号は変更できません。
パブリックvoid更新(HeroNode heroNode) {
        //空かどうかを判定する
        （ head.next == nullの場合）{
            System.out.println ( "リンクリストは空です" ) ;
        }
        //番号に従って変更が必要なノードを検索します
        HeroNode temp = head.next ;
        boolean flag = false ; // ノードが見つかったかどうかを示します
        （真）の間{
            （温度がnullの場合）
                壊す;
            }
            if ( temp . no == heroNode . no ) {
                フラグ = true ;
                壊す;
            }
 temp = temp . next ;
        }
        if (フラグ) {
 temp.name = heroNode.name ;​​
 temp.nickName = heroNode.nickName;
        }それ以外{
            System.out.printf ( "ノード番号%dが見つからないため、変更できません\n" 、heroNode.no );
        }
    }

再度機能を改善し、ノード削除機能を追加

//ノードを削除する
パブリックvoid 削除(HeroNode heroNode) {
        //空かどうかを判定する
        （ head.next == nullの場合）{
            System.out.println ( "リンクリストは空です" ) ;
        }
        HeroNode temp = head.next ;
        boolean flag = false ; //削除するポイントが見つかったかどうかを識別します
        （真）の間{
            （温度がnullの場合）
                壊す;
            }
            if ( temp . next . no == heroNode . no ) {
                フラグ = true ;
                壊す;
            }
 temp = temp . next ;
        }
        if (フラグ) {
 temp.next = temp.next.next ;​​​​​​
        }それ以外{
            System.out.printf ( "ノード番号%dを削除できません、\n" 、heroNode.no );
        }
    }

機能を再度改良し、単一のリンクリスト内の有効なノードの数をカウントする機能を追加します

/**
     * ヘッドノードを除く、単一のリンクリスト内の有効なノードの数を取得します。
     * @param head リンクリストの先頭ノード
     * @return有効なノードの数
     */
公共 静的  int getLength(HeroNode のヘッド) {
        （ head.next == nullの場合）{
 0を返します。
        }
整数 カウント= 0;
        HeroNode temp = head.next ;
        while ( temp . next != null ) {
カウント++;
 temp = temp . next ;
        }
戻る カウント;
    }

関数を再度改良し、単連結リストのK番目最後のノードを見つける関数を追加します。

 /**
     * 単方向リンクリストの K 番目の最後のノードを見つける [Sina のインタビューの質問]
     * アイデア:
     * 1. まずリンクリストを最初から最後まで走査して、リンクリストの合計の長さを取得します。
     * 2.サイズを取得した後、最初のリンクリストから（サイズ-インデックス）まで走査して、
     *
     * @param ヘッド
     * @param indexは最後のノードのインデックスを示します
     * @戻る 
     */
公共 静的HeroNode findLastIndexNode(HeroNode head, int  索引） {
        （ head.next == nullの場合）{
戻る ヌル;
        }
整数 サイズ= getLength(head);
        if (インデックス<= 0 ||インデックス>サイズ) {
戻る ヌル;
        }
        HeroNode temp = head.next ;
 for ( int i = 0; i < (サイズ-インデックス); i++) {
 temp = temp . next ;
        }
戻る 温度;
    }

関数を再度改良し、単一リンクリスト反転関数を追加する

/**
   * 逆リンクリスト [Tencent 面接の質問]
   * アイデア:
   * 1. まず、reverseHead = new HeroHead(); を定義します。
   * 2. 元のリンク リストを最初から最後まで走査し、走査後に各ノードを取り出して、新しいリンク リストの先頭に配置します。
   * 3.元のリンクリストのhead.next = riverHead.next ;
   */
公共 静的voidリバースリスト(HeroNodeヘッド) {
      もし( head.next == null || head.next.next == null ) {
戻る;
      }
      HeroNode curr = head.next ;
      HeroNode next = null ; //現在のノードの次のノードを指す [curr]
      HeroNode を逆にすると、新しい HeroNode (0, "" , "" ) が作成されます。 
 
      while (curr != null ) {
 next = curr.next ;// currノードの次のノードを一時的に保存します
          curr.next = riverHead.next ; // curr の次のノードを新しいリンクリストの先頭にポイントします
          riverHead.next = curr; // currを新しいリンクリストに接続します
          curr = next ; // curr を後ろに移動
      }
      head.next =逆Head.next ;
  }

再度機能を改良し、末尾から先頭まで単一のリンクリストを印刷する機能を追加します

/**
    * スタックを使用して逆順に印刷する [Baidu の面接の質問]
    */
公共 静的void逆印刷(HeroNodeヘッド) {
       （ head.next == nullの場合）{
戻る;
       }
       Stack<HeroNode> heroNodes = 新しい Stack<HeroNode>();
       HeroNode temp = head.next ;
       while ( temp != null ) {
           heroNodes.add ( temp ) ;
 temp = temp . next ;
       }
       ( heroNodes.size () > 0)の場合
           System.out.println (heroNodes.pop()) ;
       }
   }

【編集者のおすすめ】

1. いいですね、上司からシンプルなワークフロー エンジンを開発するように言われました...
2. Windows 10 は世界を揺るがす変化をもたらします!今年最初のアップデートが来ました
3. 2021年に注目すべき6つのサイバーセキュリティトレンド
4. 近年の Windows 10 における最大の改善点! Windows 10 21H2 新機能プレビュー
5. Xiao Aiは本当にPC版をリリースしたのか？コンピュータ版のXiao Aiを体験してみましょう