ステップ--javaベース(4)--JavaにおけるArayListとLinked Listの違い

6667 ワード

データ構造

この記事の転載は以下の通りですhttp://pengcqu.iteye.com/blog/502676 オリジナルを尊重する
ArayListとLinkdListの大まかな違いは、一般的に知られています.1.ArayListは、動的配列に基づくデータ構造を実現し、LinkdListは、チェーンベースのデータ構造に基づいています.2.ランダムアクセスgetとsetに対して、ArayListはLinked Listより優れていると思います.なぜならLinked Listはポインタを移動するからです.3.追加と削除操作addとremoveに対して、Linded ListはArayListがデータを移動するために優位を占めています.
ArayListとLinkdListは、一連のオブジェクト参照(references)を格納するための2つのクラスである.例えば、一連のStringまたはIntegerをArayListで記憶することができます.ArayListとLinkdListの性能にはどのような違いがありますか?ArayListはいつLinkdListを使うべきですか?
一.時間の複雑さ
まず重要な点は、ArayListの内部実装は基礎的なオブジェクト配列に基づいているので、リスト内の任意の要素にget方法を使用してアクセスするときは、LinkdListよりも速い速度であることである.
Linked Listでのget方法は、リストの端から順にチェックし、他端までチェックします.Linked Listにとって、リストにある特定要素にアクセスするのはより速い方法がない.
大きなリストがあると仮定して、その中の要素はもう順番に並べられています.このリストはArayListタイプのものかもしれません.Linked Listタイプのものかもしれません.今はこのリストを二分検索します.比較リストはArayListとLinkdList時の検索速度です.次の手順を見てください.

package com.mangocity.test;   
import java.util.LinkedList;   
import java.util.List;   
import java.util.Random;   
import java.util.ArrayList;   
import java.util.Arrays;   
import java.util.Collections;   
public class TestList ...{   
     public static final int N=50000;   

     public static List values;   

     static...{   
         Integer vals[]=new Integer[N];   

         Random r=new Random();   

         for(int i=0,currval=0;i<N;i++)...{   
             vals=new Integer(currval);   
             currval+=r.nextInt(100)+1;   
         }   

         values=Arrays.asList(vals);   
     }   

     static long timeList(List lst)...{   
         long start=System.currentTimeMillis();   
         for(int i=0;i<N;i++)...{   
             int index=Collections.binarySearch(lst, values.get(i));   
             if(index!=i)   
                 System.out.println("***  ***");   
         }   
         return System.currentTimeMillis()-start;   
     }   
     public static void main(String args[])...{   
         System.out.println("ArrayList    ："+timeList(new ArrayList(values)));   
         System.out.println("LinkedList    ："+timeList(new LinkedList(values)));   
     }   
}

私が得た出力は、ArayListの消費時間:15 Linked Listの消費時間:2596
この結果は固定されていないが、基本的にはArayListの時間はLinked Listの時間より明らかに小さい.このような状況ではLinked Listは使われない.二分割検索法で使用されるランダムアクセスポリシーは、Linked Listが速いランダムアクセスをサポートしていません.一つのLinked Listにランダムアクセスをするために消費される時間は、このlistの大きさに比例します.これに応じて、ArayListにおけるランダムアクセスによって消費される時間は固定される.
これは、ArayListがいつもLinked Listよりも性能が良いということを示していますか?これは必ずしもそうではないが、場合によってはLinked ListのパフォーマンスはArayListよりも優れており、いくつかのアルゴリズムはLinkdListで実現されるときより効率が高い.例えば、Collection.reverseを利用してリストを反転させる場合は、その性能が良いです.
このような例を見ると、リストに参加して、大量の挿入と削除を行います.この場合、LinkdListはいい選択です.以下の極端な例を見てください.リストの始まりに要素を挿入します.

package com.mangocity.test;   

import java.util.*;   
public class ListDemo {   
     static final int N=50000;   
     static long timeList(List list){   
     long start=System.currentTimeMillis();   
     Object o = new Object();   
     for(int i=0;i<N;i++)   
         list.add(0, o);   
     return System.currentTimeMillis()-start;   
     }   
     public static void main(String[] args) {   
         System.out.println("ArrayList  ："+timeList(new ArrayList()));   
         System.out.println("LinkedList  ："+timeList(new LinkedList()));   
     }   
}

この時の出力結果は、ArayList消耗時:2463 LinkdList消耗時:15
これは、前の例の結果とは対照的に、ArayListの最初に要素が加えられたときに、既に存在しているすべての要素が後にシフトし、これはデータ移動と複製におけるオーバーヘッドを意味する.逆に、1つの要素をLinked Listの最初に加えるのは、単純な非この要素に記録を割り当て、その後、2つの接続を調整するだけである.Linked Listの開始時には、1つの要素のオーバーヘッドを増加させるのが固定されていますが、ArayListの開始時には、1つの要素のオーバーヘッドを増加させるのがArayListの大きさに比例します.
二.空間の複雑さ
Linked Listにはプライベートな内部クラスがあります.定義は以下の通りです.

private static class Entry {   
         Object element;   
         Entry next;   
         Entry previous;   
     }

各Entryオブジェクトreferenceリストには、Linked Listの前の要素と次の要素があります.1,000個の要素を持つLinked Listオブジェクトは、1,000個のリンクされたEntryオブジェクトがあり、各オブジェクトはリストの1つの要素に対応しています.このようにすると、Linked List構造の中にはこの1000個のEntityオブジェクトに関する情報を格納するために大きなスペースオーバヘッドがある.
ArayListは、要素を格納するために内蔵された配列を使用しています.この配列の開始容量は10です.配列が成長する必要があるとき、新しい容量は次の式によって得られます.新しい容量=(旧容量*3)/2＋1、つまり、容量は50%ぐらい増加します.これは、大量の元素を含むArayListオブジェクトがあると、最終的には大きな空間が浪費されるということを意味しています.この浪費は、ArayListの働き方そのものによるものです.新しい要素を保存するために十分な空間がない場合、配列は新しい要素を追加するために再割り当てされる必要があります.配列を再分配すると,性能が急激に低下する.ArayListがどれぐらいの要素を持つかを知っているなら、構造法によって容量を指定できます.また、trimToSize方法により、ArayList割り当てが完了したら、無駄な空間を取り除くこともできます.
三.まとめ
ArayListとLinkdListはそれぞれ性能上の長所と短所があり、それぞれに適用されるところがあります.総じて次のように説明できます.

1.ArayListおよびLinkdListについては、リストの末尾に要素を追加するためのオーバーヘッドが固定されている.ArayListにとっては、主に内部配列に一つの項目を追加し、追加された要素を指し、偶には配列の再割り当てを引き起こす可能性がある.Linked Listにとっては、このオーバーヘッドは統一されており、内部のEntryオブジェクトが割り当てられている.

.ArayListの中間に要素を挿入または削除すると、このリストの残りの要素が移動されることを意味する.Linked Listの中間に要素を挿入または削除するオーバーヘッドは固定されている.

.LinkdListは効率的なランダム要素アクセスをサポートしていません.

.ArayListの空間的浪費は、主にリストの最後に一定の容量空間を予約することによって表されるが、LinkdListの空間的支出は、それぞれの要素に反映されるので、相当な空間を消費する必要がある

.
動作が前または中間ではなく、一列のデータの後にデータを追加し、ランダムにその中の要素にアクセスする必要がある場合、ArayListを使用するとより良い性能を提供するということができる.一列のデータの前または中間にデータを追加または削除し、その中の要素に順番にアクセスする場合は、LinkdListを使うべきです.

nodejs oraclejetをインストールします.