【Java集合のList】ArayListとLinkdListの違い

6832 ワード

前言
ArayListとLinkdListはListインターフェースを実現しました.大まかな違いは以下の通りです.
  • ArayListは、動的配列に基づくデータ構造を実現し、リンクベースのデータ構造である.
  • は、ランダムアクセスgetおよびsetに対して、LinkedListは、Linked Listがポインタを移動するので、Linked Listより優れていると思う.
  • は、ArayListがデータを移動するので、動作addとremoveを追加して削除する場合、LindeListが比較的有利である.
  • これから詳しくテストします.
    テスト
    /**
     * @  :List  
     * @  :CYH
     * @  :V1.0
     * @    ::2016-12-20
     */
    public class ListTest {
        /**@    :
         * @param args void
         */
        public static void main(String[] args) {
            List list = new ArrayList();
            List link = new LinkedList();
    
            //   ArrayList
            long start = System.currentTimeMillis();
            Random random = new Random();
            for(int i=0; i<10000000; i++){
                list.add(random.nextInt(10000000));
            }
            long end = System.currentTimeMillis();
            long time = end - start;
            System.out.format("   ArrayList  :%d  
    "
    , time); // LinkedList start = System.currentTimeMillis(); for(int i=0; i<10000000; i++){ link.add(random.nextInt(10000000)); } end = System.currentTimeMillis(); time = end - start; System.out.format(" LinkedList :%d
    "
    , time); // ArrayList start = System.currentTimeMillis(); for(int i=0; i<10; i++){ list.get(random.nextInt(1000000)); } end = System.currentTimeMillis(); time = end - start; System.out.format("ArrayList :%d
    "
    , time); // LinkedList start = System.currentTimeMillis(); for(int i=0; i<10; i++){ link.get(random.nextInt(1000000)); } end = System.currentTimeMillis(); time = end - start; System.out.format("LinkedList :%d
    "
    , time); // ArrayList start = System.currentTimeMillis(); for(int i=0; i<100; i++){ list.add(1000, list.get(random.nextInt(1000000))); } end = System.currentTimeMillis(); time = end - start; System.out.format("ArrayList :%d
    "
    , time); // ArrayList start = System.currentTimeMillis(); for(int i=0; i<100; i++){ link.add(1000, list.get(random.nextInt(1000000))); } end = System.currentTimeMillis(); time = end - start; System.out.format("LinkedList :%d
    "
    , time); // ArrayList start = System.currentTimeMillis(); for(int i=0; i<100; i++){ list.remove(random.nextInt(1000000)); } end = System.currentTimeMillis(); time = end - start; System.out.format("ArrayList :%d
    "
    , time); // ArrayList start = System.currentTimeMillis(); for(int i=0; i<100; i++){ link.remove(random.nextInt(1000000)); } end = System.currentTimeMillis(); time = end - start; System.out.format("LinkedList :%d
    "
    , time); } }
    試験入力の実行結果:
    初期化ArayList費用:3656秒初期化LinkdList費用:4869秒ArayListランダム取込時間:0秒LikedListランダム取込時間:73秒ArayListランダム挿入時間:884秒Listランダム挿入時間:0秒ArayListランダム削除時間:855秒Listランダム削除時間:431秒
    ArayListの作成オーバーヘッドはLinked Listより小さい.ランダムアクセスのArayListはLinked Listより効率が高いです.ランダムにArayListを挿入して削除するのはLinked Listより効率が低いです.
    ArayListの内部実装は、ベースのオブジェクト配列に基づいているので、リスト内のいずれかの要素にget方法を用いてアクセスする場合、その速度はLinked Listよりも速い.Linked Listでのget方法は、リストの端から順にチェックし、他端までチェックします.Linked Listにとって、リストにある特定要素にアクセスするのはより速い方法がない.
    締め括りをつける
    ArayListとLinkdListはそれぞれの性能上の長所と短所があり、それぞれに適用されるところがあります.総じて言えば、1.ArayListとLinkdListに対して、リストの末尾に1つの要素オーバーヘッドを追加するのは固定されています.ArayListは、主に内部配列に一つの項目を追加し、追加された要素を指し、偶には配列の再割り当てを引き起こす可能性がある.Linked Listというオーバーヘッドは統一され、内部のEntryオブジェクトを割り当てます.2.ArayListの中間に要素を挿入または削除すると、このリストの残りの要素が移動されることを意味する.Linked Listの中間に要素を挿入または削除するオーバーヘッドは固定されている.3.LinkdListは効率的なランダム要素アクセスをサポートしていません.4.ArayListの空間浪費は、主にリストの最後に一定の容量空間を予約することを体現しているが、Linked Listの空間費はその各要素に反映されており、相当な空間を消費する必要がある.
    動作が前または中間ではなく、一列のデータの後にデータを追加し、その中の要素にランダムにアクセスする必要がある場合、ArayListを使用するとより良い性能を提供する.一列のデータの前または中間にデータを追加または削除し、その中の要素に順番にアクセスする場合は、LinkdListを使うべきです.