さまざまなデータ構造（２）連結リスト１

データ構造

こんにちは。前回は片方向リスト用のノードを作っただけで終わりにしてしまいました。今回は、そのノードを使って連結リストを作りたいと思います。

とりあえず、前回の記事（片方向リスト用のノード）を読んでいない場合には、リンク先のページをお読みください。

すでにＪａｖａに連結リストがありますよ

そうなんです。わざわざ自分で連結リストを作らなくても、すでにＪａｖａならばjava.utilというパッケージを読み込んでしまえば、連結リストがあるんです。リンクをはっておきます。

とはいえ、車輪の再開発です。ちゃんと手順をたどっていくことで、データ構造を学ぼうとする人のためにも、考え方が分かるようにしようと思います。

連結リスト（サブセット版）で実装するメソッド

先ほどのオラクルのドキュメントを見ると、膨大なメソッド群になっています。すべてを実装することはできません。連結リストとして使い物になる程度のメソッドを実装することにします。実装するメソッドは

int size()　連結リスト内にある要素の数を返す

void add(int index,E element)　連結リスト内の指定された位置に指定された要素を挿入する

void add(E element)　連結リストの最後に指定された要素を挿入する

get(int index)　連結リストの指定された位置にある要素を返す

set(int index,E element)　連結リストの指定された位置にある要素を、指定された要素に置き換える

remove(int index)　連結リストの指定された位置にある要素を削除する

toString()　連結リストを文字列に変換する

に限定しようと思います。自分で選んだメソッドを実装した連結リストという意味でMyLinkedListクラスと呼ぶことにします。

メソッドごとのアルゴリズム

size()

要素の数を返すメソッドです。単純に一つずつノードインスタンスをたどって、数えていけば値が求められます。

下の図では、headの次の北海道で「１個」、その次の青森県で「２個」、・・・、その次の秋田県で「５個」、その次はｎｕｌｌなので無し。以上「５個！」と返すのがsize()です。

簡単なプログラムを書くと、こんな感じになるでしょうか。

int size = 0;
MyNode<E> tmp = head;

while (tmp != null) {
	tmp = tmp.getNext();
	size++;
}

add(int index,E element)

挿入する場所でノードインスタンスのつなぎ変えが生じます。新しいノードインスタンスを作り、そのリンク先を挿入する前のリンク先にします。挿入する位置のリンクを、新しく作ったノードに向けます。なお、これ以降indexの値は０オリジン（０から数え始める）とします。

先頭に要素を追加する場合と、それ以外の場合とで若干操作が変わります。まずは先頭に追加する場合です。head.add( 0, “北海道" )の場合です。とりあえず、"北海道"を要素とする新しいインスタンスを作ります。

プログラムでは

MyNode<E> n = new MyNode<E>();
n.setElement(element);

です。

次に、①　新しいインスタンスのnextをheadが指していたインスタンスにします。続けて、②　headを新しいインスタンスを指し示すことに変更します。

これをプログラムにすると

n.setNext(head);
head = n;

です。

これで"北海道"を先頭に追加することができました。次に、先頭以外に追加する場合を見ていきましょう。

下の図でhead.add( 3, “宮城県" )を実行した場合は次のようになります。とりあえず、"宮城県"を要素とする新しいインスタンスを作ります。その後、３－１＝２番目のインスタンスが何を指し示しているかをtmpに記憶しておきます。図では青い矢印になります。『ひとつ手前の矢印』を記憶しておくのがポイントです。

青い矢印を見つけるには、

MyNode<E> tmp = getNthNode(index - 1);

としました。ここでgetNthNodeは、N番目のノードを見つけるメソッドです。

private MyNode<E> getNthNode(int index) {
	MyNode<E> result = head;
	for (int count = 0; count < index; count++) {
		result = result.getNext();
	}
	return result;
}

で実装しています。

次に、①　新しいインスタンスのnextを青い矢印が指し示すインスタンスのnextとして、さらに②　青い矢印が指し示すインスタンスのnextを新しいインスタンスに変更します。

ひとつ手前の矢印を覚えておかないと、つなぎ変えができないので注意が必要です。

プログラムでは

n.setNext(tmp.getNext());
tmp.setNext(n);

です。

図は挿入がわかるように、無理やり矢印を曲げて描いていますが、コンピュータでは単なる数値で歪な曲線は登場しないので安心してください。

add(E element)

連結リストの最後に挿入します。いい換えると、add( size() , element )になります。同じメソッド名ですが、引数の違いで異なる挙動をさせることができるのでJavaは便利です。上の図とほとんど同じになるので、説明を省略します。

一応、プログラムです。

add(size(), element);

set(int index,E element)

これは順番に前から個数を数えながら要素をたどっていき、目的の位置に到達したら要素を代入することで上書きしてしまいます。

head.set( 2, “岩手県" )を実行した場合は次のようになります。先頭の要素から０，１，２と順に数えます。２番目の要素（０オリジンなので３個目）の要素を指し示す矢印を覚えておきます。次に、その矢印が指し示す要素のelementを上書きします。ここでは『いわて』が『岩手県』に変更されます。

大変そうですが、プログラムを書くとたった１行です。

getNthNode(index).setElement(element);

get(int index)

これも順番に前から個数を数えながら要素をたどっていき、目的の位置に到達したら要素を返します。

head.get( 1 )を実行した場合は次のようになります。先頭の要素から０，１と順に数えます。1番目の要素（０オリジンなので2個目）の要素のelementを戻り値とします。

これも、プログラムでは、たった１行です。

return getNthNode(index).getElement();

remove(int index)

先頭の要素の場合とそれ以外の要素の場合で考え方が変わります。先頭の要素を削除する場合には、削除前の２番目の要素が新しい先頭の要素になります。

head.remove( 0 )は、headの指し示すインスタンスを、元のheadの次の次につながっているものに変えるだけです。取り除くインスタンスは，Javaの場合はガベージコレクションが備わっているので、消さなくても大丈夫です。言語の仕様によっては、ちゃんとメモリを開放しておきましょう。このような不要であるにも関わらず、解放されないメモリが積み重なっていくと、恐ろしいことが、いつか発生します。

このプログラムです。

head = head.getNext();

それ以外の要素を削除する場合には、リンクをひとつ飛ばした先のものにつなぎ直します。

head.remove( 3 )の場合、３－１＝２番目のインスタンスが何を指し示しているかをtmpに記憶しておき（青い矢印）、これを使ってつなぎ変えの操作をします。

青い矢印が指し示すインスタンスのnextを、変更前と比べてさらに１つ先のnextが指し示しているものに変更します。

これも１つ手前の矢印を使うところがミソです。

プログラムでは、

MyNode<E> tmp = getNthNode(index - 1);
tmp.setNext(tmp.getNext().getNext());

となります。

toString()

一つひとつ要素に対してtoString()してつなぐと、連結リスト全体のtoString()になります。単にループして、文字列をつなぐだけなので、説明は省略します。

クラスを定義するプログラムは次回書きます。今回はこれでおしまい。それではまた。

Posted by 春日井 優