AVA-集合フレームワーク(3)


LinkedList


配列には次のような欠点があります.
  • サイズは変更できません.
  • の非連続データの追加または削除には時間がかかります.
  • それを補うためにLinkedListが登場した.リンクリストは、不連続に存在するデータを資料接続の形で構成します.

    「リンク」リストの各要素(node)は、次に関連付けられた要素への参照とデータから構成されます.
    class Node{
    Node next;//下記の要素の住所を保存する
    Object obj;//ストレージデータ
    }
    リンクリストからデータを削除する場合は、削除する要素の前の要素を変更して、削除する要素を参照する次の要素を変更するだけです.
    アレイのようにデータを移動するためにコピーするプロセスがないため、処理速度が速い.
    新しいデータを追加する場合は、新しい要素を作成し、追加する前の要素の参照を新しい要素への参照に変更し、新しい要素が次の要素を参照するように変更します.そのため、処理速度が非常に速い.
    リンクリストの移動方向は一方向なので、次の要素にアクセスしやすいが、前の要素にアクセスするのは難しい.これを補うのはダブルリンクリストです.
    二重リンクリストは、単純にリンクリストに参照変数を追加するだけで、次の要素だけでなく前の要素も参照できます.それ以外はリンクリストと同じです.
    class Node{
    	Node next; 		//다음 요소의 주소를 저장
        Node previous;  //이전 요소의 주소를 저장
        Object obj;		//데이터를 저장.
        
    }

    二重リンクリストのアクセス性を向上させるのは、「二重ループリンクリスト」です.
    これは、ダブルリンクリストの最初の要素と最後の要素を接続するだけです.
    最後の要素の次の要素が最初の要素になり、最初の要素の前の要素が最後の要素になります.

    n/a.結論
    1.順次追加・削除する場合、LinkedListよりArrayListの方が速い.
    2.中間データを追加/削除する場合、LinkedListはArrayListより速い.
    配列内の各要素はメモリに連続的に存在するため、これらの要素のアドレスを計算するだけで格納されたデータを取得できます.
    LinkedListは、不連続位置の各要素が互いに接続されており、最初からn番目のデータまで順次フォローして必要な値を得る.
    従ってLinkedListの欠点は、格納するデータが多ければ多いほど、データの読み取り時間が長くなることである.
    処理するデータ数が変わらない場合は、ArrayList
    データ量を頻繁に使うならLinkedListの方が良いと言えます.