ArrayList & LinkedList

1949 ワード
データ構造 テキストリンク

ArrayListとは?

  • は、
    • の繰り返しを許可する.
    保持
  • シーケンス
  • インデックス管理要素を使用すると、配列と非常に似ています.
  • 寸法は動的に増加します.
    • ArrayList<T> list=new ArrayList<>();
  • 初期容量(Default Capacity=10)より大きいサイズの場合、要素を追加および削除する場合、アレイコピーが頻繁に発生する可能性があります.したがって、パフォーマンスは
    • 低下する.
    一時アレイ
  • を作成してデータ
    • をコピーする.
  • データのインデックスがあり、検索データは
    • 速い.

    API


  • add(E element):最後に要素を追加
    時間複雑度:O(1)

  • remove(int index):インデックス内の要素を削除
    時間複雑度:O(n)

  • get(int index):インデックスの要素値を取得する
    時間複雑度:O(1)

  • コンテンツ(E要素):この要素が含まれているかどうか
    時間複雑度:O(n)

    • LinkedListとは?


  • の2つの方向の接続リストから構成されています.
  • スキームの欠点を補うために、リンクリストというデータ構造
    • が設計された.
  • データを格納する各ノードは、前のノードと次のノードの状態のみを知る.
  • の追加と削除が高速
  • のデータを取得するにはノードを最初から巡回する必要があるため、速度は
    • 遅い.

    配列の欠点

  • サイズは変更できません.
    -新しいアレイを作成してコピーする必要があります
  • の稼働速度を向上するには、十分な容量を予め決定する必要があるが、メモリ浪費
    • .
  • の非連続データの追加または削除には時間がかかります.

    • API


  • add(E element):最後に要素を追加
    時間複雑度:O(1)

  • remove:要素を削除する
    時間複雑度:O(1)

  • get:インデックスに対応する要素をインポートする
    時間複雑度:O(n)

  • contains:この要素が含まれているかどうか
    時間複雑度:O(n)
    • [Spring] JPA?
    Abstract_Factory