M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

お気楽 Java プログラミング入門

第 8 回 連結リスト

[ PrevPage | J a v a | NextPage ]

●はじめに

前回はインターフェースと例外処理について説明しました。今回はオブジェクト指向機能を使った簡単な例題として、連結リスト (linked list) という基本的なデータ構造を作成します。

連結リストを扱うプログラミング言語といえば Lisp が有名です。このほかに、関数型言語 (ML や Haskell など) や論理型言語の Prolog も、組み込みのデータ構造として連結リストを装備しています。また、Java のパッケージにも連結リストと同等の機能を持つクラス LinkedList が用意されているので、わざわざ連結リストを自作する必要はまったくありません。今回は Java の勉強ということで、あえて連結リストをプログラムしてみましょう。

●連結リストの構造

今回取り上げる連結リストはデータを一方向 [*1] につないだデータ構造です。図 1 に連結リストの構造を示します。 

(1)変数
  ┌─┐    ┌─┬─┐  ┌─┬─┐  ┌─┬─┐  
  │・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(null)
  └─┘    └─┴─┘  └─┴─┘  └─┴─┘  

(2)ヘッダセル
  ┌─┬─┐    ┌─┬─┐  ┌─┬─┐  ┌─┬─┐  
  │  │・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(null)
  └─┴─┘    └─┴─┘  └─┴─┘  └─┴─┘  

        図 1 : 連結リストの構造

連結リストはセル (cell) というデータをつなげて作ります。セルにはデータを格納する場所と、次のセルを指し示す場所から構成されます。図 1 でいうと、箱がひとつのセルを表していて、左側にデータを格納し、右側に次のセルへの参照を格納します。リストの終わりを示すため、最後のセルの右側には特別な値 (null) を格納します。

null は「なにも無い」ことを表す特別なデータ (null 型) です。null はクラスなどの参照データ型に無条件でキャストすることができます。たとえば、オブジェクトを格納する変数や配列は、デフォルトで null が初期値になります。

そして、図 1 (1) のように先頭セルへの参照を変数に格納しておけば、この変数を使って連結リストにアクセスすることができます。また、図 1 (2) のようにヘッダセルを用意する方法もあります。

連結リストの長所は、データの挿入や削除が簡単にできることです。配列でデータの削除や挿入を行う場合、要素を移動しなければいけませんが、連結リストはセルを付け替えるだけで実現できます。逆に、配列はどの要素にも一定の時間でアクセスすることができますが、連結リストはセルを順番にたどっていくため、後ろのデータになるほどアクセスに時間がかかります。これが連結リストの短所です。

[*1] 一方向につないだ連結リストを「片方向リスト (singly-linked list) 」といいます。これに対し、前後のセルをつないだ「双方向リスト (doubly-linked list) 」という連結リストもあります。Java の LinkedList クラスは双方向リストです。

●クラスの定義

それではプログラムを作りましょう。最初に、連結リストを表すクラス Linked_List とセルを表すクラス Cell を定義します。Java には LinkedList クラスがあるので、名前は Linked_List としました。リスト 1 を見てください。 

リスト 1 : 連結リストの定義

// セル
class Cell {
  // フィールド変数
  private Object value;
  private Cell link;
  // コンストラクタ
  Cell(Object obj, Cell cp){
    value = obj;
    link = cp;
  }
  // アクセスメソッド
  Object get_value(){ return value; }
  Cell get_link(){ return link; }
  void set_value(Object obj){ value = obj; }
  void set_link(Cell cp){ link = cp; }
}

// 連結リスト
class Linked_List {
  // フィールド変数
  private Cell head;
  private int  size;
  // コンストラクタ
  Linked_List(){
    head = new Cell(null, null);   // ヘッダーセル
    size = 0;
  }
  
  // メソッドの定義
  ...
}

Cell のフィールド変数 value にデータを格納し、link に次のセルへの参照を格納します。value のデータ型は Object とします。Java のクラスは必ず Object を継承するので、どんなクラスのオブジェクトでもアップキャストすることで連結リストに格納することができます。あとは、コンストラクタとアクセスメソッドを定義します。これらのメソッドを使ってセルを操作します。

次に、セルを使って連結リストクラス Linked_List を作成します。Linked_List にはセルを保持するフィールド変数 head とデータの個数をカウントする変数 size を用意します。コンストラクタで、head にヘッダセルをセットし、size を 0 に初期化します。ヘッダセルの value はダミーで、このプログラムでは null をセットします。また、後ろのセルは無いので link にも null をセットします。

●連結リストの操作メソッド

次は、連結リストを操作するメソッドを定義します。基本的なメソッドを表 1 に示します。

表 1 : Linked_List の操作メソッド
メソッド 機能
Object get(int n) n 番目の要素を求める
void add(int n, Object x) n 番目の位置にデータ x を追加する
boolean add(Object x) 最後尾にデータ x を追加する
Object remove(int n) n 番目の要素を削除する
Object set(int n, Object x) n 番目の要素をデータ x に置き換える
返り値は置き換えられた古い要素を返す
void clear() 連結リストを空にする
int size() 要素の個数を返す
boolean isEmpty() 空リストであれば true を返す

要素の位置は配列と同様に 0 から数えることにします。位置 n がリストの長さよりも大きい場合、どのメソッドでも例外を送出することにします。 

リスト 2 : 例外クラス

class ListIndexOutOfBoundsException extends IndexOutOfBoundsException {
  public ListIndexOutOfBoundsException(){ }
  public ListIndexOutOfBoundsException(String msg){ super(msg); }
}

例外の名前は ListIndexOutOfBoundsException とし、IndexOutOfBoundsException を継承することにします。

●作業用メソッド nth()

最初に、作業用のメソッドとして n 番目のセルを求める処理を作ります。メソッド名は nth() としました。リスト 3 を見てください。 

リスト 3 : n 番目のセルを求める

  private Cell nth(int n){
    int i = -1;
    Cell cp = head;
    while(cp != null){
      if(n == i) return cp;
      i++;
      cp = cp.get_link();
    }
    throw new ListIndexOutOfBoundsException("Linked_List");
  }

nth() は private メソッドに設定します。最初に、ヘッダセルを cp にセットします。ヘッダセルから数えるので、変数 i は -1 に初期化します。次に、while ループでセルをたどり、i が n と等しくなったとき、そのセルを return で返します。

セルのたどり方は実に簡単です。図 2 を見てください。 

 cp1         cp2         cp3
┌─┬─┐  ┌─┬─┐  ┌─┬─┐
│10│・┼→│20│・┼→│30│・┼→
└─┴─┘  └─┴─┘  └─┴─┘
↑          ↑
(1)         (2)

(1) cp = cp.get_link() => cp2
(2) cp = cp.get_link() => cp3

        図 2 : セルのたどり方

セル cp1 の link にはセル cp2 への参照が格納されています。変数 cp が cp1 を指している場合 (図 2 (1))、cp の値を cp.get_link() の返り値で更新すれば、cp の値はセル cp2 になります (図 2 (2))。さらに cp の値を cp.get_link() の返り値で更新すれば、cp の値は cp3 になります (図 2 (3))。

nth() の場合、while ループでセルをたどっていきますが、途中でセルがなくなった場合、cp の値は null になります。ここで while ループを終了して、例外 ListIndexOutOfBoundsException を送出します。

●データの取得

それでは、n 番目の要素を求めるメソッド get() から作りましょう。リスト 4 を見てください。 

リスト 4 : n 番目の要素を求める

  public Object get(int n){
    Cell cp = nth(n);
    return cp.get_value();
  }

nth() を呼び出して n 番目のセル cp を求めます。そして、格納されているデータを cp.get_value() で求めます。

●データの挿入

次は、データの挿入を行うメソッド add() を作りましょう。データの挿入はセルの link を書き換えることで実現できます。図 3 を見てください。セル cp1 とセル cp2 の間に、セル cp4 を挿入します。 

 top         (1)                (2)
┌─┐      ┌─┬─┐         ┌─┬─┐  ┌─┬─┐
│  ┼──→│10│・┼─ X ─→│20│・┼→│30│／│
└─┘      └─┴┼┘         └─┴─┘  └─┴─┘
                  │   (3)      ↑
                  │  ┌─┬─┐│
                  └→│40│・┼┘
                      └─┴─┘

セル(1)とセル(2)の間にセル(3)を挿入する場合

                図 3 : データの挿入

セル cp1 の後ろにセル cp4 を挿入する場合、セル cp1 の link にはセル cp2 への参照がセットされているので、この値をセル cp4 の link にセットします。これで、セル cp4 とセル cp2 がリンクされます。次に、セル cp1 の link にセル cp4 への参照をセットします。これで、セル cp1 とセル cp2 の間に、セル cp4 を挿入することができます。

プログラムをリスト 5 に示します。 

リスト 5 : データの挿入

  public void add(int n, Object obj){
    Cell cp = nth(n - 1);
    Cell cp1 = new Cell(obj, cp.get_link());
    cp.set_link(cp1);
    size++;
  }

  // 最後に挿入
  public boolean add(Object obj){
    this.add(size, obj);
    return true;
  }

連結リストにデータを挿入する場合、挿入する位置のひとつ手前のセルが必要になります。nth() で n - 1 番目のセルを求めます。セル cp が見つかれば、cp の後ろに obj を挿入します。n が 0 の場合、nth() はヘッダセルを返すので、リストの先頭にデータが挿入されることになります。

new Cell(obj, cp.get_link()) で obj を格納する新しいセル cp1 を生成します。第 2 引数に cp.get_link() を指定することで、新しいセルの後ろに、cp の後ろのセルを接続することができます。そして、cp.set_link(cp1) で cp の link を新しいセル cp1 に書き換えます。これで cp の後ろに cp1 を挿入することができます。最後に size を +1 してから、挿入したデータ obj を返します。

最後にデータを追加するメソッド add(Object obj) は、多重定義したメソッドを呼び出せば簡単です。this.add(size, obj) とすれば、同じクラスのメソッド add() を呼び出して、最後尾にデータ obj を追加することができます。

●データの削除

次は、データを削除するメソッド remove() を作りましょう。 

 (1)           (2)         (3)
┌─┬─┐    ┌─┬─┐  ┌─┬─┐  
│10│・┼×→│20│・┼→│30│・┼→
└─┴┼┘    └─┴─┘  └─┴─┘  
      │                  ↑
      └─────────┘

        図 4 : データの削除:セル(2) を削除する場合

データを削除する場合も、セルを付け替えるだけで済ますことができます。図 4 を見てください。セル cp1 の後ろにあるセル cp2 を削除する場合、セル cp1 の link をセル cp3 への参照に書き換えればいいのです。セル cp3 はセル cp2 の link から求めることができます。

プログラムをリスト 6 に示します。 

リスト 6 : データの削除

  public Object remove(int n){
    Cell cp = nth(n - 1);
    Cell del_cp = cp.get_link();
    if(del_cp == null){
      throw new ListIndexOutOfBoundsException("Linked_List");
    }
    cp.set_link(del_cp.get_link());
    size--;
    return del_cp.get_value();
  }

データを削除する場合も、削除する位置のひとつ手前のセルが必要になります。nth() で n - 1 番目のセルを求めます。セル cp が見つかれば、cp の後ろのセルを削除します。

次に、削除するセル del_cp を cp.get_link() で求めます。del_cp が null ならば、削除するセルが無いので例外を送出します。cp.set_link() で cp の link を del_cp の後ろのセル del_cp.get_link() に書き換えます。最後に size を -1 してから、削除した要素を del_cp.get_value() で求めて返します。

ところで、連結リストからはずされたセルは head からアクセスすることができなくなります。Java の場合、どの変数からも参照されなくなったオブジェクトはゴミとなり、「ゴミ集め (GC) 」[*2] によって回収されて再利用されます。

GC がないプログラミング言語では、不要になったオブジェクトは自動的に回収されません。それを行うようにプログラムする必要があるのです。Java のように GC があるプログラミング言語では、ゴミになったオブジェクトは自動的に回収されるので、プログラマの負担はそれだけ軽くなります。

[*2] 不要になったオブジェクトを自動的に回収する機能を「ガベージコレクション (Garbage Collection) 」と呼びます。

●その他の操作メソッド

残りのメソッドは簡単です。次のリストを見てください。 

リスト 7 : その他の操作メソッド

  // 置き換え
  public Object set(int n, Object obj){
    Cell cp = nth(n);
    Object old = cp.get_value();
    cp.set_value(obj);
    return old;
  }

  // 空にする
  public void clear(){
    head.set_link(null);
    size = 0;
  }

  // 個数を求める
  public int size(){ return size; }

  // 空リストか
  public boolean isEmpty(){ return size == 0; }

要素を置き換えるメソッド set() は、nth() で n 番目のセル cp を求め、cp.set_value(obj) で要素の値 old を obj に書き換えます。clear() も簡単で、head.set_link() でヘッダーセルの link を null に書き換えて size を 0 にするだけです。要素の個数を求める size() は、フィールド変数 size を返すだけです。isEmpty() は size が 0 かチェックするだけです。

●データの変換

このほかに、連結リストを配列に変換するメソッド toArray() と文字列に変換するメソッド toString() を定義すると便利です。リスト 8 を見てください。 

リスト 8 : データの変換

  // 配列に変換する
  public Object[] toArray(){
    Object[] a = new Object [size];
    Cell cp = head.get_link();
    for(int i = 0; i < size; i++){
      a[i] = cp.get_value();
      cp = cp.get_link();
    }
    return a;
  }

  // 文字列に変換
  public String toString(){
    String buff = "(";
    Cell cp = head.get_link();
    while(cp != null){
      buff += cp.get_value().toString();
      cp = cp.get_link();
      if(cp != null) buff += " ";
    }
    buff += ")";
    return buff;
  }

toArray() は簡単です。Object 型の配列 a を用意し、連結リストをたどって要素を配列に格納していくだけです。toString() も簡単で、要素を toString() で文字列に変換し、それを変数 buff に追加していくだけです。演算子 + で文字列を連結すると新しい文字列が生成されるので、連結リストが長くなると非効率になりますが、簡単にプログラムすることができます。

●ボクシングとアンボクシング

ところで、連結リストはオブジェクトを格納するので、数や boolean などの基本データ型 (プリミティブ型ともいう) をそのまま格納することはできません。Java には基本データ型に対応するクラス (プリミティブラッパークラス) があり、それに変換することでデータを連結リストに格納することができます。基本データ型とそれに対応するラッパークラスを表 2 に示します。

表 2 : ラッパークラス
基本データ型ラッパークラス
booleanBoolean
charCharacter
byteByte
shortShort
intInteger
longLong
floatFloat
doubleDouble

基本データ型をラッパークラスに変換することを「ボクシング (boxing) 」といい、逆にラッパークラスを基本データ型に変換することを「アンボクシング (unboxing) 」といいます。たとえば、int と Integer の変換は次のように行います。 

リスト 9 : ボクシングとアンボクシング

public class sample80 {
  public static void main(String[] args){
    Integer n1 = new Integer(10);
    Integer n2 = Integer.valueOf(100);
    Integer n3 = 1000;                  // (1)
    int m1 = n1.intValue();
    int m2 = n2;                        // (2)
    System.out.println(n1);
    System.out.println(n2);
    System.out.println(n3);
    System.out.println(m1);
    System.out.println(m2);
  }
}

C>java sample80
10
100
1000
10
100

ボクシングはコンストラクタを使ってインスタンスを生成する、もしくはクラスメソッド valueOf() を使います。アンボクシングはメソッド intValue() を使います。これは int に変換するときに使用するメソッドで、他のデータ型に返還するメソッドもあります。

Java は JDK 5 から自動的にボクシングとアンボクシングを行うようになりました。この機能を「オートボクシング」といいます。リスト 9 の (1) は 1000 が自動的にラッパークラス Integer に変換されます。(2) は Integer クラスのインスタンス n2 が自動的に int に変換されます。

ところで、ラッパークラスは参照型データなので、演算子 == で比較すると、値が等しくても false になる場合があります。次の例を見てください。 

リスト 10 : ラッパークラスの比較

public class sample81 {
  public static void main(String[] args){
    Integer n1 = new Integer(100);
    Integer n2 = new Integer(100);
    System.out.println(n1 == n2);
    System.out.println(n1 == 100);
    System.out.println(100 == n2);
    System.out.println(n1.equals(n2));
  }
}

C>java sample81
false
true
true
true

new で Integer のインスタンスを生成し、変数 n1 と n2 にセットします。どちらも同じ値ですが、別々のインスタンスなので n1 == n2 は false になります。100 と比較すると、自動的にアンボクシングされるので n1 == 100 と 100 == n2 は true になります。また、メソッド equals() を使って n1 と n2 を比較すると true になります。オートボクシングは便利な機能ですが、演算子 == を使うときには十分に注意してください。

●実行例

それでは簡単な実行例を示しましょう。 

リスト 11 : 簡単なテスト

public class list0 {
  public static void main(String[] args){
    Linked_List ls = new Linked_List();
    System.out.println(ls);
    System.out.println(ls.size());
    System.out.println(ls.isEmpty());
    for(int i = 0; i < 10; i++){
      System.out.println("add: " + i);
      ls.add(i);
      System.out.println(ls);
      System.out.println(ls.size());
      System.out.println(ls.isEmpty());
    }
    for(Object n: ls.toArray()) System.out.print(n + " ");
    System.out.println();
    for(int i = 0; i < 10; i++){
      System.out.print(ls.get(i) + " ");
    }
    System.out.println();
    for(int i = 0; i < 5; i++){
      System.out.println("remove: " + i);
      System.out.println(ls.remove(i));
      System.out.println(ls);
      System.out.println(ls.size());
      System.out.println(ls.isEmpty());
    }
    System.out.println("clear:");
    ls.clear();
    System.out.println(ls);
    System.out.println(ls.size());
    System.out.println(ls.isEmpty());
  }
}

C>java list0
()
0
true
add: 0
(0)
1
false
add: 1
(0 1)
2
false
add: 2
(0 1 2)
3
false
add: 3
(0 1 2 3)
4
false
add: 4
(0 1 2 3 4)
5
false
add: 5
(0 1 2 3 4 5)
6
false
add: 6
(0 1 2 3 4 5 6)
7
false
add: 7
(0 1 2 3 4 5 6 7)
8
false
add: 8
(0 1 2 3 4 5 6 7 8)
9
false
add: 9
(0 1 2 3 4 5 6 7 8 9)
10
false
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
remove: 0
0
(1 2 3 4 5 6 7 8 9)
9
false
remove: 1
2
(1 3 4 5 6 7 8 9)
8
false
remove: 2
4
(1 3 5 6 7 8 9)
7
false
remove: 3
6
(1 3 5 7 8 9)
6
false
remove: 4
8
(1 3 5 7 9)
5
false
clear:
()
0
true

正常に動作していますね。

●プログラムリスト

//
// list0.java : 連結リスト
//
//             Copyright (C) 2009 Makoto Hiroi
//

// 例外クラス
class ListIndexOutOfBoundsException extends IndexOutOfBoundsException {
  public ListIndexOutOfBoundsException(){ }
  public ListIndexOutOfBoundsException(String msg){ super(msg); }
}

// セル
class Cell {
  // フィールド変数
  private Object value;
  private Cell link;
  // コンストラクタ
  Cell(Object obj, Cell cp){
    value = obj;
    link = cp;
  }
  // アクセスメソッド
  Object get_value(){ return value; }
  Cell get_link(){ return link; }
  void set_value(Object obj){ value = obj; }
  void set_link(Cell cp){ link = cp; }
}

// 連結リスト
class Linked_List {
  // フィールド変数
  private Cell head;
  private int  size;
  // コンストラクタ
  Linked_List(){
    head = new Cell(null, null);   // ヘッダーセル
    size = 0;
  }
  
  // n 番目のセルを求める
  private Cell nth(int n){
    int i = -1;
    Cell cp = head;
    while(cp != null){
      if(n == i) return cp;
      i++;
      cp = cp.get_link();
    }
    throw new ListIndexOutOfBoundsException("Linked_List");
  }

  // 参照
  public Object get(int n){
    Cell cp = nth(n);
    return cp.get_value();
  }

  // 挿入
  public void add(int n, Object obj){
    Cell cp = nth(n - 1);
    Cell cp1 = new Cell(obj, cp.get_link());
    cp.set_link(cp1);
    size++;
  }

  // 最後に挿入
  public boolean add(Object obj){
    this.add(size, obj);
    return true;
  }

  // 削除
  public Object remove(int n){
    Cell cp = nth(n - 1);
    Cell del_cp = cp.get_link();
    if(del_cp == null){
      throw new ListIndexOutOfBoundsException("Linked_List");
    }
    cp.set_link(del_cp.get_link());
    size--;
    return del_cp.get_value();
  }

  // 置き換え
  public Object set(int n, Object obj){
    Cell cp = nth(n);
    Object old = cp.get_value();
    cp.set_value(obj);
    return old;
  }

  // 空にする
  public void clear(){
    head.set_link(null);
    size = 0;
  }

  // 個数を求める
  public int size(){ return size; }

  // 空リストか
  public boolean isEmpty(){ return size == 0; }

  // 配列に変換する
  public Object[] toArray(){
    Object[] a = new Object [size];
    Cell cp = head.get_link();
    for(int i = 0; i < size; i++){
      a[i] = cp.get_value();
      cp = cp.get_link();
    }
    return a;
  }
  
  // 文字列に変換
  public String toString(){
    String buff = "(";
    Cell cp = head.get_link();
    while(cp != null){
      buff += cp.get_value().toString();
      cp = cp.get_link();
      if(cp != null) buff += " ";
    }
    buff += ")";
    return buff;
  }
}

// 簡単なテスト
public class list0 {
  public static void main(String[] args){
    Linked_List ls = new Linked_List();
    System.out.println(ls);
    System.out.println(ls.size());
    System.out.println(ls.isEmpty());
    for(int i = 0; i < 10; i++){
      System.out.println("add: " + i);
      ls.add(i);
      System.out.println(ls);
      System.out.println(ls.size());
      System.out.println(ls.isEmpty());
    }
    for(Object n: ls.toArray()) System.out.print(n + " ");
    System.out.println();
    for(int i = 0; i < 10; i++){
      System.out.print(ls.get(i) + " ");
    }
    System.out.println();
    for(int i = 0; i < 5; i++){
      System.out.println("remove: " + i);
      System.out.println(ls.remove(i));
      System.out.println(ls);
      System.out.println(ls.size());
      System.out.println(ls.isEmpty());
    }
    System.out.println("clear:");
    ls.clear();
    System.out.println(ls);
    System.out.println(ls.size());
    System.out.println(ls.isEmpty());
  }
}
Copyright (C) 2009 Makoto Hiroi
All rights reserved.
[ PrevPage | J a v a | NextPage ]