Rainbow Engine

IT技術を分かりやすく簡潔にまとめることによる学習の効率化、また日常の気付きを記録に残すことを目指します。

Java

JavaのArrrayListとLinkedListの違いについて

投稿日:2021年1月31日 更新日:

<目次>

(1) JavaのArrrayListとLinkedListの違いについて
 (1-1) 比較表(ArrayList vs LinkedList)
 (1-2) まとめ
 (1-3) 参考

(1) JavaのArrrayListとLinkedListの違いについて

両方ともListインターフェイスを実装している点や、データの追加時に順番が保持される点などは同じですが、いくつか異なる点があるので、その違いについてご紹介いたします。

(1-1) 比較表(ArrayList vs LinkedList)

(表)

観点 ArrayList LinkedList
メモリ領域の連続性 連続した領域が必要(×)

(確保した領域以上のデータを追加しようとすると、別の新しい領域を確保する処理が行われる)

連続していなくてもOK(◎)

(データの領域さえあれば、連続する必要なし)

メモリの必要量 少ない(◎)

(アドレスの情報が無い分、LinkedListと比較するとメモリ消費が少ない)

多い(×)

(値の情報のみならず、次の要素のアドレスを保持する必要がある)

要素の追加・削除 遅い(×)

(追加・削除位置より後の要素を1つずつずらす処理が発生)

速い(◎)

(リンクを1カ所付け替えるのみなので、ArrayListと比して速い)

要素の参照 速い(◎)

(要素のアドレスを計算して直接アクセスできるため速い)

遅い(×)

(最初の要素から目的の要素まで1つずつリンクを辿るため遅い)

用途 List List、Deque

(ListのみならずDequeとしても使える)

【※補足①】
確保領域を上回るデータを格納する場合、内部的には次の処理が行われています。
(1) より大きなサイズの「新配列」をnewで確保する
(2) 「旧配列」のデータを新配列にコピーする
(3) コピーが終わったら「旧配列」をnullにする
 
【※補足②】
途中のポイントでINSERTやDELETEをしてしまうと、INSERTの場合は以降の要素を「1つずつ後」にずらし、DELETEの場合は以降の要素を「1つずつ前」にずらす処理が発生するためです。そのため、削除位置が先頭に近いほど処理時間が掛かります。
 
【※補足③】
要素の追加・削除が発生する時の動きをイメージしやすいよう、図を交えて流れを追ってみます。
まず下図のようなLinkedListがあるとします。

(図1)

これにデータの追加を行うと、次のように変化します。図の赤い矢印が示すように、LinkedListの場合はリンクの付け替えが1回で済みます(ArrayListのように後続の要素を1つずつズラす必要なし)

(図2)

 

目次にもどる

(1-2) まとめ

ArrayListは「データの参照」が得意で、LinkedListは「データの追加・更新」が得意です。

■ArrayListメリット・デメリット
⭕️:メモリの消費量がLinkedListより少ない
⭕️:要素へのアクセスが速い
❌:メモリ領域が連続している必要がある
❌:要素の追加・削除が遅い
 
■LinkedListのメリット・デメリット
⭕️:メモリ領域が連続していなくてもOK
⭕️:要素の追加・削除が速い
❌:要素のアクセスが遅い
❌:メモリの消費量がArrayListより多い
 

目次にもどる

(1-3) 参考

Javaに出てくる「List」は順序を持った要素の集合の事で、Listの挙動はListインターフェイスにて定義されています。そのため、ArrayListやLinkedListは同じメソッドが利用可能になっています。

目次にもどる

Adsense審査用広告コード


Adsense審査用広告コード


-Java

執筆者:


comment

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

関連記事

APサーバ(Java)⇒DBサーバ(OracleDB 11g)へJDBC接続する方法まとめ

(0)目次 (1) 前提条件 (2) JDBCドライバーのインストール  (2-1) JDBCドライバーをダウンロード  (2-2) APサーバにアップロード・解凍 (3) プログラムの実装  (3- …

JavaScriptでタグを追加する方法(jQueryのtagEditorプラグインを導入)

  <目次> (1) JavaScriptでタグを追加する方法(jQueryのtagEditorプラグインを導入)  (1-1) 概要  (1-2) tagEditorの導入方法  (1-3 …

サーバサイドJava(JSP&サーブレット)における画面遷移の手法とそのサンプルコードの紹介

(0)目次&概説 (1) 画面遷移の代表手法  (1-1) フォワード  (1-2) リダイレクト (2) 画面遷移手法のご紹介  (2-1) 方法1:formタグ+Submitボタン(JSP/Ser …

WindowsのcmdからJavaファイルを作成・コンパイル・実行する方法

“Windows”の「コマンドプロンプト」からJavaファイルを作成・コンパイル・実行する方法について記述します。今回の操作は全てコマンドラインインターフェイスから実施いたしま …

木構造の探索における計算量の違いや木構造の種類について(B木/二分木/2-3探索木)

<目次> (1) 木構造の探索における計算量の違いや木構造の種類について(B木/二分木/2-3探索木)  (1-1) 木構造について  (1-2) 「B木」構造  (1-3) 「二分木」構造  (1- …

  • English (United States)
  • 日本語
Top