【LinkedList】Javaで待ち行列を簡単に扱う!

  • このエントリーをはてなブックマークに追加
  • Pocket

LinkedListは、ListクラスとDequeクラスのインターフェースを実装した双方向結合リストだ。

待ち行列を使った順序の管理やArrayListに比較して処理スピード速いメソッドの使用頻度が高い場合に向いている。

このページではJavaのLinkedListについてまとめてみた。参考にしていただければと思う。

LinkedListによる配列の扱い方

すべての操作は、双方向結合リストに期待されるはずの処理を実行する。リストのindexに関係する操作は、指定されたindexに近いリストの最初か終わりから横断するようになっている。

双方向結合リスト

Listクラスのインターフェースが実装されているので、整数のインデックス(Listの位置)で要素にアクセスできる。追加する要素は、同じ要素であってもかまわない。ArrayListと比較すると、メソッドの機能は同じでも、アクセス速度に違いがあるので注意が必要だ。

Dequeクラスのインターフェースが実装されている。DequeとはDouble Ended Queue(二つの終端がある待ち行列)を省略した名称なのだ。それは、線形コレクションで両端に要素を追加することや削除することがサポートしている。ほとんどのDequeクラスは要素の数に制限を設けない実装をしているが、このインターフェースは固定サイズ制限と同様の容量制限があるDequeをサポートしている。

JavaでのLinkedListを使うための書き方の詳細を確認していこう。

LinkedListクラスを使うための準備をする

まず、配列に要素にアクセスするために、コンストラクタを使ってその入れ物となるLinkedListクラスのオブジェクトを生成しなければならない。そのコンストラクタの書き方の詳細を見てみよう。

LinkedList()

内容

空のリストを生成する。

要素を追加して取得する

リストに要素を追加しなければ、何も始まらない。次に、追加された要素を取り出す。これが基本的なメソッドだ。それらのメソッドの詳細を見てみよう。

追加

追加するために、基本となるふたつのメソッドを紹介しよう。ひとつは、リストの最後に要素を追加するためのメソッドとリストの途中に要素を追加するためのメソッドだ。

add(E e)

戻り値の型

public boolean

内容

特定の要素をリストの最後に追加する。このメソッドは、addLast(E)と同じである。

 

引数:e – リストに追加されるべき要素

戻り値:true (Collection.add(E)で指定されているように)

add(int index, E element)

戻り値の型

public boolean

内容

リストの指定された位置に指定された要素を挿入する。挿入された位置にあった要素(もしあれば)、また、後に続く要素は右にシフトする。(それらのindexに1を加える。)

 

引数:index - 指定された要素が挿入されるべきindex。

element -リストに挿入されるべき要素

 

例外:IndexOutOfBoundsException  –  もしindexが範囲外ならば

(index < 0 || index > size())

要素の取得

要素を取得するためのメソッドはひとつしかない。indexを指定して、要素を取得する。もしindexが範囲外なら、例外を発生させて教えてくれる。

get(int index)

戻り値の型

public E

内容

指定された位置にある要素を戻す。

 

引数:index - 戻すべき要素のインデックス

戻り値:リストの指定された位置の要素

例外:IndexOutOfBoundsException – もしindexが範囲外ならば

(index < 0 || index > size())

サンプルプログラム

それでは実際にサンプルプログラムで確認してみよう。

実行結果

サンプルプログラムの説明

それでは簡単にプログラムの解説をしてゆこう。

このプログラムは、くだものの名前を最初にふたつ追加した後、追加した要素の「りんご」と「みかん」の間に「もも」を挿入するというものだ。次に、要素を表示して確認している。このとき、存在しない要素を取得して、例外が発生することも確認している。

  • l [1] LinkedListクラスのオブジェクト、listを生成する。
  • l [2] listに文字列:「りんご」を追加する。
  • l [3] listに文字列:「みかん」を追加する。
  • l [4] listのindex:1に文字列:「もも」を追加する。
  • l [5] listのindex:0から取得した要素を表示する。
  • l [6] listのindex:1から取得した要素を表示する。
  • l [7] listのindex:2から取得した要素を表示する。
  • l [8] 例外処理の開始tryを宣言する。
  • l [9] listのindex:3から取得した要素を表示する。
  • l [10] 例外処理のcatchを宣言する。
  • l [11] 例外が発生したことを表示する。

要素を検索して置換削除する

要素を検索して、見つけた要素を変更することも、削除することもできる。検索方法もひとつだけではない。その詳細を見てみよう。

検索

要素を検索するためのメソッドはふたつある。リストの先頭から探すメソッドと最後から探すメソッドだ。要求に合ったものを使うようにしよう。

indexOf(Object o)

戻り値の型

public int

内容

リストの中で、指定された要素が最初に見つかった位置を戻す。もし、リストの中に見つからなかったら、-1を戻す。

もっと形式的に言えば、(o==null ? get(i)==null : o.equals(get(i)))であるような要素の中で最も小さい値のインデックスiを戻す。また、もしそのようなインデックスがなければ-1を戻す。

 

引数:o – 探すべき要素

戻り値:上の記述と同じだ。

lastIndexOf(Object o)

戻り値の型

public int

内容

リストの中で、指定された要素が最後に見つかった位置を戻す。もし、リストの中に見つからなかったら、-1を戻す。

もっと形式的に言えば、(o==null ? get(i)==null : o.equals(get(i)))であるような要素の中で最も大きい値のインデックスiを戻す。また、もしそのようなインデックスがなければ-1を戻す。

 

引数:o – 探すべき要素

戻り値:上の記述と同じだ。

置換

すでに存在する要素を、indexを指定して置き換える。もしindexが範囲外なら、例外を発生させて教えてくれる。

set(int index, E element)

戻り値の型

public E

内容

指定された要素で、リストの指定された位置にある要素を置き換える。

 

引数:index - 置き換えるべき要素のインデックス

element - 指定された位置に格納される要素

戻り値:指定された位置の置き換え前の要素

例外:IndexOutOfBoundsException – もしindexが範囲外ならば

(index < 0 || index > size())

削除

削除するためのメソッドはいくつかあるが、その基本となるメソッドだ。戻り値に削除された要素が返されるので、確実に削除されたかどうかがわかる。

remove(int index)

戻り値の型

public E

内容

指定された位置にある要素をリストから削除する。後に続く要素を左にシフトする(それらのインデックスから一つを取り去る)。

 

引数:e - 削除すべき要素のインデックス

戻り値:リストから削除された要素

例外:IndexOutOfBoundsException – もしindexが範囲外ならば

(index < 0 || index > size())

要素を検索して置換削除するサンプルプログラム

それでは実際にサンプルプログラムで確認してみよう。

実行結果

サンプルプログラムの説明

それでは簡単にプログラムの解説をしてゆこう。

このプログラムは、くだものの名前を最初に3つ追加した後、追加した要素の「りんご」を「マンゴー」に置換する。「もも」を削除する。次に、置換した要素を表示して置換を確認している。削除した要素は取得して、例外が発生することも確認している。

  • l [1] LinkedListクラスのオブジェクト、listを生成する。
  • l [2] listに文字列:「りんご」を追加する。
  • l [3] listに文字列:「もも」を追加する。
  • l [4] listに文字列:「みかん」を追加する。
  • l [5] listのindex:0から取得した要素を表示する。
  • l [6] listのindex:1から取得した要素を表示する。
  • l [7] listのindex:2から取得した要素を表示する。
  • l [8] listのindex:0を文字列:「マンゴー」で置換する。
  • l [9] 置換前の要素を表示する。
  • l [10] listのindex:2を削除する。
  • l [11] 削除した要素を表示する。
  • l [12] listのindex:0から取得した要素を表示する。
  • l [13] listのindex:1から取得した要素を表示する。
  • l [14] 例外処理の開始tryを宣言する。
  • l [15] listのindex:2から取得した要素を表示する。
  • l [16] 例外処理のcatchを宣言する。
  • l [17] 例外が発生したことを表示する。

要素すべてに対して繰り返し処理(forEach)

要素をリストからひとつひとつ取り出して、何かの処理をすることはよくある。その基本からラムダ式まで詳細を見てみよう。

size()

戻り値の型

public int

内容

リスト内の要素の数を返す。

 

戻り値:リスト内の要素の数を返す。

forEach(Consumer<? super E> action)

戻り値の型

public void

内容

すべての要素が処理されるか、actionが例外を発生させるまで、各々の要素のためのactionが実行される。実装されたクラスによって他に指定されない限り、繰り返しの順序でactionが実行される。(繰り返しの並びが特定されるならば)actionにより投げられた例外は呼び出し元に中継される。

 

引数:action – 各々の要素のために実行されるべきaction。

forを使ったサンプルプログラム

それでは実際にサンプルプログラムで確認してみよう。

拡張forを使ったサンプルプログラム

このプログラムが拡張forを使ったサンプルプログラムだ。要素を表示するところだけがforと違う。

forEachを使ったサンプルプログラム

このプログラムがforEachを使ったサンプルプログラムだ。要素を表示するところだけがforと違う。

実行結果

どのサンプルプログラムも実行結果は同じになる。

サンプルプログラムの説明

それでは簡単にプログラムの解説をしてゆこう。

これら3つのプログラムは、どれも同じだ。くだものの名前を3つ追加した後、forを使用してlistの要素をすべて表示している。

  • l [1] LinkedListクラスのオブジェクト、listを生成する。
  • l [2] listに文字列:「りんご」を追加する。
  • l [3] listに文字列:「もも」を追加する。
  • l [4] listに文字列:「みかん」を追加する。
  • l [5] [6] forを使用して、listのすべての要素をすべて表示する。

要素をソートする

要素をソートすることは、よくある。LinkedListは、このソートを自由に行うことのできる仕組みを持っている。Comparatorを使って、ソートで使用する比較メソッドを自由に定義できる。詳細を見てみよう。

メソッド

sort(Comparator<? super E> c)

戻り値の型

public void

内容

指定されたComparatorによって誘導された順序に応じてこのリストをソートする。

リストの中の要素は、指定されたcomparatorによって相互に比較可能でなければならない。

もし、指定されたcomparatorがnullならば、リストの中のすべての要素はComparable Interfaceを実装しており、要素の自然な順序付けを使用していなければなりません。(つまり、c.compare(e1, e2)は、リストの中のどんな要素e1とe2に対してもClassCastExceptionを投げてはならない)

このリストは、修正可能でなければならないが、サイズを変更可能である必要はない。

 

引数:c – リストの要素を比較するために使用されるCamparator。null値は、要素の自然な順序付けが使用されるべきだということを示す。

サンプルプログラム

このプログラムがsortを使ったサンプルプログラムだ。要素を昇順にソートして表示している。Comparatorをラムダ式で書いているので、そのメソッド:compareを書き換えれば、ソート順を変えることができる。

実行結果

[9] 要素[0]:アメリカ

[10] 要素[1]:イタリア

[11] 要素[2]:ウクライナ

サンプルプログラムの説明

それでは簡単にプログラムの解説をしてゆこう。

このプログラムは、国の名前を3つ追加した後、sortを使用してlistの要素を昇順に並べ替えている。

  • l [1] LinkedListクラスのオブジェクト、listを生成する。
  • l [2] comparatorを定義する。
  • l [3] メソッド:compareを実装する。
  • l [4] 文字列が昇順になるように文字列比較を行う。
  • l [5] listに文字列:「イタリア」を追加する。
  • l [6] listに文字列:「ウクライナ」を追加する。
  • l [7] listに文字列:「アメリカ」を追加する。
  • l [8] listをソートする。
  • l [9] listのindex:0から取得した要素を表示する。
  • l [10] listのindex:1から取得した要素を表示する。
  • l [11] listのindex:2から取得した要素を表示する。

順序を管理する

順序を管理するには、LinkedArrayに実装されたDequeのインターフェースが使える。一般的に順序管理のために、FIFO(First In First Out:先入れ先出し)やLIFO(Last In First Out)などの手法がある。このような手法を実現するリストの両端への要素の追加や削除を行うメソッドがサポートされているからだ。

追加

offerFirst(E e)

戻り値の型

public boolean

内容

リストの先頭に指定された要素を追加する。

 

引数:追加する要素

戻り値:true(Deque.offerFirst(E)によって指定されているように)

以後:1.6

offerLast(E e)

戻り値の型

public boolean

内容

リストの先頭に指定された要素を追加する。

 

引数:追加する要素

戻り値:true(Deque.offerFirst(E)によって指定されているように)

以後:1.6

削除

pollFirst()

戻り値の型

public E

内容

リストの最初の要素を取り出して、削除する。または、もしリストが空ならば、nullを戻す。

 

戻り値:上記と同じだ。

以後:1.6

pollLast()

戻り値の型

public E

内容

リストの最後の要素を取り出して、削除する。または、もしリストが空ならば、nullを戻す。

 

戻り値:上記と同じだ。

以後:1.6

サンプルプログラム

このプログラムがDequeのインターフェースを使ったサンプルプログラムだ。空のエレベーターに乗った人のうちだれが先に出てくるかをシミュレーションしている。入口と出口が同じタイプのエレベーターをOne Door Typeとした。入口の反対側に出口あるタイプをTwo Door Typeとした。One Doorの場合がLIFO(先入れ後出し)の待ち行列に、Two Doorsの場合が、FIFO(先入れ先出し)の待ち行列になる。

FIFO

実行結果

サンプルプログラムの説明

それでは簡単にプログラムの解説をしてゆこう。

このプログラムは、One Door Typeのエレベーター場合は、リスト(待ち行列)の先頭に要素を追加して、リストの先頭から取り出している。Two Doors Typeの場合は、リストの先頭に要素を追加して、リストの最後から取り出している。

  • l [1] LinkedListクラスのオブジェクトqueueOfOneDoorTypeElevatorを生成する。
  • l [2] queueOfOneDoorTypeElevatorの先頭に「Aさん」を追加する。
  • l [3] queueOfOneDoorTypeElevatorの先頭に「Bさん」を追加する。
  • l [4] queueOfOneDoorTypeElevatorの先頭に「Cさん」を追加する。
  • l [5] queueOfOneDoorTypeElevatorの先頭から要素を取り出して表示する。
  • l [6] queueOfOneDoorTypeElevatorの先頭から要素を取り出して表示する。
  • l [7] queueOfOneDoorTypeElevatorの先頭から要素を取り出して表示する。
  • l [8] queueOfOneDoorTypeElevatorの先頭から要素を取り出して表示する。
  • l [9] LinkedListクラスのオブジェクトqueueOfTwoDoorsTypeElevatorを生成する。
  • l [2] queueOfTwoDoorsTypeElevatorの先頭に「Aさん」を追加する。
  • l [3] queueOfTwoDoorsTypeElevatorの先頭に「Bさん」を追加する。
  • l [4] queueOfTwoDoorsTypeElevatorの先頭に「Cさん」を追加する。
  • l [5] queueOfTwoDoorsTypeElevatorの最後から要素を取り出して表示する。
  • l [6] queueOfTwoDoorsTypeElevatorの最後から要素を取り出して表示する。
  • l [7] queueOfTwoDoorsTypeElevatorの最後から要素を取り出して表示する。
  • l [8] queueOfTwoDoorsTypeElevatorの最後から要素を取り出して表示する。

配列を変換する

最初からコードを書くときは、このメソッドを使うことはまずないだろう。配列よりLinkedListの方が、いろいろなメソッドがあるからだ。しかし、既存のコードには配列を使ったところがある。簡単に実装できるからだ。しかし、だんだん機能が盛り込まれると、やっぱりLinkedListが必要になる。そんな時、このメソッドが役に立つ。既存の配列とLinkedListをつないでくれるからだ。

型変換

toArray()

戻り値の型

public Object[]

内容

正しい順序(最初から最後の要素に向かって)でリストの中のすべての要素を含む配列を戻す。

戻される配列は、このリストによるどんな参照も保持されないという意味で安全です。(言い換えれば、このメソッドは新たな配列を確保します。)呼び出し側は、戻された配列を自由に変更可能です。

このメソッドは、配列ベースとCollectionベースAPI間のブリッジになります。

 

戻り値:正しい順序でリストの中のすべての要素を含む配列を戻す。

参照:Arrays.asList(Object[])

toArray(T[] a)

戻り値の型

public <T> T[]

内容

リストの中に含まれているすべての要素を正しい順序(最初から最後の要素に向かう)の並びの配列で戻す;戻される実行時の型は、指定された配列の型である。もしリストが指定された配列に合致すれば、その中に戻される。一方、新しい配列は、指定された実行時の配列とリストの大きさで確保される。

もしリストが空きスペースと共に指定された配列に収まるのであれば(例えば、配列がリスト内の要素よりもっと多くの要素を持っている)、集合の最後にすぐ続く配列の中の要素にnullをセットする。(これは、もし呼び出し元が、リストがどんなnull要素を含んでいないことを知っているときに限って、リストの長さを決定するのに有用である)

 

型引数:T - 集合を含むべき実行時の配列の型

引数:a – 配列が十分な大きさをならば、リストの要素が格納される。そうでなければ、この目的のために同じ実行時の型の配列が確保される。

戻り値;リストの要素を含む配列

例外:

ArrayStoreException – 指定された配列の実行時の型が、リスト内のどの要素の実行時のsuper型ではない。

NullPointerException – もし、指定された配列がnullならば

Listの追加

addAll(Collection<? extends E> c)

戻り値の型

public boolean

内容

リストの最後に指定されたcollectionにある全ての要素を追加する。そして、その順序は指定されたcollectionのIteratorによって戻される。

もし指定されたcollectionが操作の進行中に修正されたならば、操作の振る舞いが未定義となる。(これは、指定されたcollectionがこのリストで、このリストが空でない場合、この呼び出しの振る舞いが未定義になることを意味する。)

 

引数:c – このリストに追加されるべき要素を含むcollection。

戻り値:true 呼び出しの結果としてリストが変化したならば。

 

例外:NullPointerException – 指定されたcollectionがnullならば。

参照:AbstractCollection.add(Object)

サンプルプログラム

このプログラムがtoArrayを使ったサンプルプログラムだ。配列を一度LinkedListのオブジェクトに格納して、またその要素を配列に変換している。既存のプログラムが配列を使っていて、LinkedListにある機能をそこで使いたくなったら、このメソッドがあることを思い出してほしい。

実行結果

サンプルプログラムの説明

それでは簡単にプログラムの解説をしてゆこう。

このプログラムは、初期値として3つのくだものの名前を配列に設定する。その配列をLinkedListに変換し、さらに「マンゴー」を追加する。最後にもう一度配列に変換して、要素すべて表示している。

  • l [1] 文字列の配列「りんご」「もも」「みかん」を持つstringsを宣言する
  • l [2] Listクラスのオブジェクトlistに配列stringsを、asList()を使って変換する。
  • l [3] ArrayListクラスのオブジェクトarrayListを生成する。
  • l [4] arrayListにlistを追加する。
  • l [5] index:1に「マンゴー」を追加する。
  • l [6] listのすべての要素をObject型の配列:objectsに変換する。
  • l [7] [8] 配列:objectsのすべての要素を表示する。
  • l [9] listのすべての要素をString型の配列:stringsに変換する。
  • l [10] [11] 配列:stringsのすべての要素を表示する

まとめ

LinkedListについてまとめてきたがいかがだっただろうか?

先でもお伝えしたが、待ち行列を使った順序の管理やArrayListに比較して処理スピード速いメソッドの使用頻度が高い場合に向いている。

ぜひ機会があれば活用していただきたい。

  • このエントリーをはてなブックマークに追加
  • Pocket

このページの続きや関連ページは下記から一覧で確認できる。

短期間でエンジニアになる方法

・「まったくの初心者だけどエンジニアになりたい!」

・「プログラマーとして転職をしたい!」

という方はリナックスアカデミーの資料を見てみてください。短期間で未経験からエンジニアになることができるスクールとして15年間選ばれ続けてきた理由やノウハウが載った資料です。

エンジニアの入り口に立つために必要な勉強技術の最新動向本当に使えるIT資格学習に役立つ国からの奨励金などの情報が詰まっています。

無料で2,3日中にお手元にお届けします。


資料を見てみる

SNSでもご購読できます。

コメントを残す

*