Javaデータ構造とアルゴリズム-チェーンテーブル(面接)

声明:コードワードは容易ではありません.転載は出典を明記してください.文章の下で討論して交流することを歓迎します.
前言:Javaデータ構造とアルゴリズムのテーマは不定期に更新され、読者の監督を歓迎します.本文は前編の文章Javaデータ構造とアルゴリズム--チェーンテーブルの拡張編で、チェーンテーブルの特徴を紹介して、シーン、チェーンテーブルの性能分析と1本の経典のチェーンテーブルの面接問題--チェーンの反転問題を使用します
1.チェーンテーブルの特徴
1)物理空間が不連続で、オーバーヘッドが大きい
チェーンテーブルは、その特殊な記憶構造のため、物理的な記憶空間が不連続であるため、次のノードのアドレスをマークする追加の情報(ポインタ)が必要であり、オペレーティングシステムの動的メモリ管理を利用することができ、データ自体を記憶する以外にポインタを保存する追加のオーバーヘッドが必要であるという利点がある.
2)運転時に動的に追加できる
配列とは異なり、チェーンテーブルは要素を動的に追加したり削除したりすることができ、配列の欠陥を補うことができます.
3)検索が遅い、削除が早い
検索には遍歴が必要であることは明らかですが、最悪の場合、最後の1つを検索すると、特にチェーンテーブルが長い場合は効果がありません.チェーンテーブルの削除はポインタを操作するだけで、配列よりも効率的です
2.チェーンテーブルの適用シーン
削除が頻繁な場合(コンピュータ技術の発展に伴い、空間はもはや主要な矛盾ではなく、時間効率こそ)同時に存在する場合、削除して検索する場合、一般的にチェーンテーブルはハッシュリスト、スタック、キューと組み合わせて使用されます.
3.チェーンテーブル性能分析
チェーンテーブルの挿入は、 ・ ・ 、ヘッドとテールの時間複雑度テールO(1)に分けられ、中間挿入は遍歴する必要があるため、時間複雑度テールO(L)、Lはチェーンテーブル長である.
同様に削除も ・ ・ に分けられるが、ヘッド削除の時間的複雑度はO(1)であり、中間削除と末尾削除はチェーンテーブルを遍歴する必要があるため、時間的複雑度はO(L)、Lはチェーンテーブル長である.
チェーンテーブルの検索は,遍歴が必要であるため,時間的複雑度はO(L),Lはチェーンテーブル長である.
4.一つの面接問題——チェーンテーブルの反転を実現する方法
これは面接でよく出る問題で、一般的に面接ではできるだけ余分な空間を使わずに実現することが求められています.チェーンテーブルを巡り、ヘッドを順番に挿入する方法など、方法はたくさんあります.チェーンテーブルの各ポインタを反転させる方法もあります.
4.1ポインタ反転によるチェーンテーブル反転コードの実現

    /**
     *     
     */
    public void lindRevese(){
        Node temp = first;
        last = temp;
        Node next = first.getNext();
        for (int i = 0; i < size-1; i++) {
            Node nextNext = next.getNext(); //         
            next.setNext(temp);
            temp = next;
            next = nextNext;
        }
        last.setNext(null);
        first = temp;
    }

4.2テスト

public class LinkReverse {
    public static void main(String[] args) {
        Link link = new Link();
        link.add(0,1); //1
        link.add(1,2); //1->2
        link.add(2,3); //1->2->3
        link.add(3,4); //1->2->3->4
        link.add(4,5); //1->2->3->4->5
        link.printLink();//1->2->3->4->5
        link.lindRevese();
        link.printLink();//5->4->3->2->1
    }    
}

コードセクションでは、前述のJavaデータ構造とアルゴリズムであるチェーンテーブルのコードセグメントを使用しています.
コードワードは容易ではありませんて、もしあなたに対して役に立つならば、称賛のコレクションを歓迎して賞をあげます^^;