|
|
コレクション(LinkedList) |
H.Kamifuji . |
次はLinkedListです。基本的にはArrayListと似ているのですが、要素の順番について個別に管理しているため要素を削除したり指定の場所に挿入したりといったことを高速に行うことができます。 またキューとしての性質も合わせて持っています。 当ページでは、Linux CentOS7 の Gnome で動作テストしています。 現在(2021/08)では、JDK-16.0.2 にアップされています。一部、上位互換について、見直しを行っていきます。 現在(2021/11)では、JDK-17.0.1 にアップされています。一部、上位互換について、見直しを行っていきます。 現在(2023/04)では、JDK-20.0.1 にアップされています。一部、上位互換について、見直しを行っていきます。 現在(2024/10)では、JDK-23 にアップされています。一部、上位互換について、見直しを行っていきます。 |
|
次にLinkedListクラスを見ていきます。ArrayListと似ていますが、中に含まれる要素がどのように並んでいるかを別に管理しているため、要素を追加したり削除したりする場合にArrayListと比較して高速に動作します。逆に要素を検索しようとする場合は先頭から順にリンクをたどって検索するためArrayListと比較して遅くなります。 その為、要素を追加したり削除したりすることが多い場合に適したクラスです。 LinkedListを使うには、まずLinkedListクラスのオブジェクトを作成します。LinkedListクラスのコンストラクタの1つは下記のようになっています。 LinkedList public LinkedList()空のリストを作成します。 次にnew演算子を使ってLinkedListのオブジェクトを作成します。 LinkedList<型> 変数名 = new LinkedList<型>();ArrayListクラスと同じく格納する要素の型を合わせて指定します。 例えば整数を格納するLinkedListやStringを格納するLinkedListを作成する場合は下記のようになります。 LinkedList<Integer> array = new LinkedList<Integer>(); LinkedList<String> array = new LinkedList<String>();次項のページで要素の格納と取り出しについて確認します。 |
では実際に要素を格納してから取り出してみます。 まず要素の格納方法ですが、LinkedListクラスで用意されている"add"メソッドを使います。 add public boolean add(E o)リストの最後に、指定された要素を追加します。 パラメータ: o - リストに追加される要素 戻り値: true (Collection.add の一般規約に従う) "add"メソッドを使った場合は、最後に追加されます。これはArrayListクラスの場合と同じです。 次に追加する場所を指定して要素を追加する方法です。同じ"add"メソッドで引数の異なるメソッドが用意されています。 add public void add(int index, E element)リストの指定された位置に、指定された要素を挿入します。現在その位置にある要素と後続の要素は右に移動します (インデックス値に 1 を加算)。 パラメータ: index - 指定された要素が挿入されるインデックス element - 挿入される要素 例外: IndexOutOfBoundsException - 指定されたインデックスが範囲外の場合 (index < 0 || index > size()) 指定したインデックス番号の位置に要素を追加します。該当のインデックス番号に元々あった要素と、それ以降の要素のインデックスは「+1>」ずつされます。 またリストの先頭及び最後に要素を追加するためのメソッドが別に用意されています。 addFirstメソッド: addFirst public void addFirst(E o)リストの先頭に、指定された要素を挿入します。 パラメータ: o - リストの先頭に挿入される要素 addLastメソッド: addLast public void addLast(E o)リストの最後に、指定された要素を追加します。add メソッドと同じ機能ですが、一貫性のために提供されています。 パラメータ: o - リストの最後に挿入される要素 次に格納された要素を取り出します。LinkedListクラスで用意されている"get"メソッドを使います。 get public E get(int index)リスト内の指定された位置にある要素を返します。 パラメータ: index - 返される要素のインデックス 戻り値: リスト内の指定された位置にある要素 例外: IndexOutOfBoundsException - 指定されたインデックスが範囲外の場合 (index < 0 || index > size()) 指定したインデックス番号の位置にある要素を取得します。 実際の使い方は下記のような感じとなります。 LinkedListでは実際に試してみます。 サンプルプログラム下記のサンプルを実行してみよう。import java.util.LinkedList; class collectionTest6{ public static void main(String args[]){ LinkedList上記をコンパイルした後で実行すると次のように表示されます。 [xxxxxxxx@dddddddddd LinkedList]$ java collectionTest6 日本 ポルトガル ブラジル イングランド [xxxxxxxx@dddddddddd LinkedList]$上記のサンプルでは、現在リストの格納されている要素数を取得するためにLinkedListクラスで用意されている"size"メソッドを使いました。 size public int size()リスト内にある要素の数を返します。 戻り値: リスト内の要素数 |
次に既に格納されている要素の置き換えです。LinkedListクラスで用意されている"set"メソッドを使います。 set public E set(int index, E element)リストの指定された位置にある要素を、指定された要素で置き換えます。 パラメータ: index - 置換される要素のインデックス element - 指定された位置に格納される要素 戻り値: 指定された位置に以前あった要素 例外: IndexOutOfBoundsException - 指定されたインデックスが範囲外の場合 (index < 0 || index >= size()) 指定したインデックス番号に格納されている要素を新しい要素に置き換えます。 次に要素を削除する方法です。LinkedListクラスで用意されている"remove"メソッドを使います。 remove public E remove(int index)リストの指定された位置にある要素を削除します。後続の要素は左に移動します (インデックス値から 1 を減算)。リストから削除された要素が返されます。 パラメータ: index - 削除される要素のインデックス 戻り値: 指定された位置に以前あった要素 例外: IndexOutOfBoundsException - 指定されたインデックスが範囲外の場合 (index < 0 || index >= size()) 削除したい要素のインデックス番号を指定して要素を削除します。削除された要素の後に格納されていた要素は、自動的にインデックス番号は1ずつ減ります。(ArrayListと異なり要素の再配置は行われないため、比較的高速に行われます)。 また全ての要素を削除したい場合には"clear"メソッドを使います。 clear public void clear()リストからすべての要素を削除します。 使い方としては下記のような感じとなります。 array.add("日本"); array.add("ブラジル"); array.add("イングランド"); array.set(1, "イタリア"); array.remove(0);では実際に試してみます。 サンプルプログラム下記のサンプルを実行してみよう。import java.util.LinkedList; class collectionTest7{ public static void main(String args[]){ LinkedList上記をコンパイルした後で実行すると次のように表示されます。 [xxxxxxxx@dddddddddd LinkedList]$ java collectionTest7 日本 ブラジル イングランド 2番目の国をイタリアへ置き換えます 日本 イタリア イングランド 先頭の国を削除します イタリア イングランド [xxxxxxxx@dddddddddd LinkedList]$ |
ここではLinkedListに登録されている要素の中から、指定した要素があるかどうかを検索してみます。基本的にArrayListの時と同じです。LinkedListクラスで用意されている"indexOf"メソッドを使います。 indexOf public int indexOf(Object o)リスト内で指定された要素が最初に検出された位置のインデックスを返します。List にこの要素がない場合は -1 を返します。つまり、(o==null ? get(i)==null : o.equals(get(i))) となる、最小のインデックス値 i を返します。そのようなインデックスがない場合は -1 を返します。 パラメータ: o - 検索する要素 戻り値: リスト内で指定された要素が最初に検出された位置のインデックス。リストにこの要素がない場合は -1 検索したい要素を引数に指定すると、LinkedListクラスのオブジェクト内に格納されている要素の先頭から検索を行い、最初に見つかった要素のインデックス番号を返してくれます。 また"indexOf"メソッドは先頭から検索しますけれど、最後から検索するための"lastIndexOf"メソッドも用意されています。 lastIndexOf public int lastIndexOf(Object o)リスト内で指定された要素が最後に検出された位置のインデックスを返します。リストにこの要素がない場合は -1 を返します。つまり、(o==null ? get(i)==null : o.equals(get(i))) となる、最大のインデックス値 i を返します。そのようなインデックスがない場合は -1 を返します。 パラメータ: o - 検索する要素 戻り値: リスト内で指定された要素が最後に検出された位置のインデックス。リストにこの要素がない場合は -1 削除したい要素のインデックス番号を指定して要素を削除します。削除された要素の後に格納されていた要素は、自動的にインデックス番号は1ずつ減ります。(ArrayListと異なり要素の再配置は行われないため、比較的高速に行われます)。 使い方としては下記のような感じとなります。 LinkedListでは実際に試してみます。 サンプルプログラム下記のサンプルを実行してみよう。import java.util.LinkedList; class collectionTest8{ public static void main(String args[]){ LinkedList上記をコンパイルした後で実行すると次のように表示されます。 [xxxxxxxx@dddddddddd LinkedList]$ java collectionTest8 日本 ブラジル 日本 イングランド 日本について検索します 最初のインデックス番号は 0 最後のインデックス番号は 2 [xxxxxxxx@dddddddddd LinkedList]$ |
LinkedListでは今まで見てきたような可変長配列としての利用の他に、キューとしても利用できるようになっています。キューと言うのは先入れ先出し法(FIFO)と呼ばれる方式の一つで先に追加されたデータが最初に処理されるというものです。 例えば苦情受付センターみたいなところの業務で考えて見ます。苦情の電話はどんどんかかってくるので処理するべきリストに追加していき、そして苦情が来た順番に処理していくわけです。この場合、新しくかかってきた苦情はリストの最後に追加し、処理する時はリストの一番先頭にある苦情を処理します。このような方式を先入れ先出し法と言います。 今まで見てきたメソッドでも要素を追加する時はリストの最後に追加し、処理する時はインデックス番号が0番目の要素を取り出して処理すれば同じことが出来るのですが、先入れ先出し法を使う場合は一般的なメソッド名があり同じ機能であっても違うメソッド名が用意されているわけです。 では順に見ていきます。新しい要素をリストの最後に追加するにはLinkedListクラスで用意されている"offer"メソッドを使います。 offer public boolean offer(E o)指定された要素をこのリストの末尾 (最後の要素) に追加します。 パラメータ: o - 追加する要素 戻り値: true (Queue.offer の一般規約に従う) 次に取り出す方法です。リストの先頭から要素を取り出すにはLinkedListクラスで用意されている"peek"メソッドを使います。 peek public E peek()このリストの先頭 (最初の要素) を取得しますが、削除はしません。 戻り値: キューの先頭。キューが空の場合は null また"element"メソッドも同じ機能となります。ただ要素が無いのに取り出そうとした場合、こちらは例外を投げます。 element public E element()このリストの先頭 (最初の要素) を取得しますが、削除はしません。 戻り値: キューの先頭 例外: NoSuchElementException - キューが空の場合 また同じような機能ですが、先頭の要素を取り出しつつ、同時に先頭の要素を削除するメソッドも用意されています。"poll"メソッドと"remove"メソッドですが、"poll"の場合は要素が無い場合はNULLを返しますが"remove"メソッドの場合は例外を投げます。 pollメソッド: poll public E poll()このリストの先頭 (最初の要素) を取得し、削除します。 戻り値: キューの先頭。キューが空の場合は null removeメソッド: remove public E remove()このリストの先頭 (最初の要素) を取得し、削除します。 戻り値: キューの先頭 例外: NoSuchElementException - キューが空の場合 使い方としては下記のような感じとなります。 LinkedList最初に書いたとおり、"add"メソッドや"get"メソッドでも同じことが出来ますが、キューとしてLinkedListを使う場合はメソッド名もキュー用のものを使った方が分かりやすいと思います。 では実際に試してみます。 サンプルプログラム下記のサンプルを実行してみよう。import java.util.LinkedList; class collectionTest9{ public static void main(String args[]){ LinkedList上記をコンパイルした後で実行すると次のように表示されます。 [xxxxxxxx@dddddddddd LinkedList]$ java collectionTest9 色が違う サイズが合わない 壊れていた 商品が違う [xxxxxxxx@dddddddddd LinkedList]$ |
|