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

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

関連記事

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

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

JavaScriptのMapとは?基本的な使い方やサンプルプログラムをご紹介

<目次> (1) JavaScriptのMapとは?基本的な使い方やサンプルプログラムをご紹介  (1-1) 概要・構文  (1-2) サンプルプログラム   ●JavaScriptのサンプル   ● …

Javaでcsvファイルに書き込みを行う方法(サンプルプログラム付き)

<目次> (1) Javaでcsvファイルに書き込みを行う方法  (1-1) 構文  (1-2) サンプルプログラム (1) Javaでcsvファイルに書き込みを行う方法 Javaでcsvファイルを生 …

JavaScriptでAttributeの値を削除(Remove)する方法

<目次> (1) JavaScriptでAttributeの値を削除(Remove)する方法  (1-1) 構文  (1-2) サンプルプログラム   (1-2-1) サンプルプログラムの概要   ( …

Javaのポリモフィズムのメリットや例をご紹介(サンプルプログラムあり)

<目次> (1) Javaのポリモフィズムのメリットや例をご紹介  (1-1) ポリモフィズムとは?  (1-2) サンプルプログラム  (1-3) ポリモフィズムのメリット  (1-4) 参考:ポリ …

  • English (United States)
  • 日本語
Top