プログラミング/11

出典: CourseWiki

目次

連結リスト

配列は作るときにサイズを指定する必要があるため,作る時点で必要な大きさが予測できない場合は不便です.

  • サイズが小さすぎれば,後で必要なデータを入れられない
  • サイズが大きすぎれば,メモリの無駄

また,配列の途中に要素を挿入する場合,後ろの要素をすべてコピーする必要があります. この処理は配列の大きさに比例する時間がかかるため,大きい配列だと問題になります. (実はメモリのアクセスは時間がかかる処理なのです). 配列の途中から要素を削除する場合も同様の問題があります.

配列の途中に100を挿入したときの図
画像:ArrayInsert.png

以下は配列の途中に挿入するプログラムです.

import java.util.Arrays;
 
public class ArrayInsertSample {
    public static void main(String[] args) {
        int[] data = new int[20];
        // 配列の初期化 
        for (int i = 0; i < data.length; i++) {
            data[i] = i;
        }
        
        System.out.println(Arrays.toString(data));
        
        // insPos(=3)の位置に100を挿入する.
        // このためにdata[insPos]〜data[18]をdata[insPos+1]〜data[19]にコピーする
        // データを上書きしないように後ろからコピーしていることに注意
        int insPos = 3;
        for (int i = data.length - 1; i > insPos; i--) {
            data[i] = data[i - 1];  
        }
        data[insPos] = 100;
        
        System.out.println(Arrays.toString(data));
    }
}

実行結果:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
[0, 1, 2, 100, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

作成時点でサイズの予測ができない場合や,配列の途中で要素を追加・削除する場合, 配列ではなく連結リスト(linked list)が良く使われます.

連結リストはおそらく配列の次によく使われるデータ構造(data structure)です.

データ構造とは,複数のデータをコンピュータで扱うときのデータの格納方法のことをいいます. 効率の良いプログラムをつくるためには,処理に適したデータ構造を選ぶ必要があります. よく使われるデータ構造としては,配列,連結リスト,ハッシュ表,木(ツリー)などが挙げられます.

連結リストにはいくつか種類がありますが,まずは単純な片方向連結リスト(singly-linked list)を説明します.

片方向連結リスト

配列では,各要素は連続したメモリ領域に確保されますが,連結リストは,各要素が別々の領域(一般にセル(cell)と呼ばれます)に確保されます(次の図を参照).

  • それぞれのセルには,格納するデータと,次のセルへの参照(一般にnextで表される)が格納されています.
  • 末尾のセルでは,next の値に null を入れて最後ということを表します.
  • 先頭のセルを参照する変数(図のhead)を用意します.

このような構造を構築すれば,先頭のセルから next を次々に辿っていくことで要素を順番にアクセスすることができます.

なお,連結リストではnextのポインタが要素数必要になるので,メモリ効率は配列よりも悪くなります.

配列は連続した領域に確保される
画像:Array.png

連結リストは各要素が別々の領域に確保される
画像:SList.png

双方向連結リスト

片方向連結リストは制約が厳しいため(前のセルに辿れないため効率が悪い),一般的には双方向連結リスト(doubly-linked list)が使われます.

双方向連結リストは,各セルに前のセルへのポインタ(一般にprevで表される)を付け加えたものです.

図では,prevのリンクは青い線で表しています.

画像:DList.png

一般にはリストの先頭だけではなく,末尾にも高速にアクセスできるように,末尾の要素を指す参照も用意します.

実装を楽にするため,次の図のようにダミーのセルを用意し,ダミーセルの next に先頭のセルへの参照を,ダミーセルの prev に末尾セルへの参照を格納しておきます. また,最初の要素の prev と末尾の要素の next はダミーセルを指すようにしておきます.

画像:DList2.png

リストが空の状態ではダミーセルだけが存在し,ダミーセルの next と prev はダミーセル自身を指しています.

画像:DListInitial1.png

次は最初の要素を追加したところです.

画像:DListInitial2.png

要素の挿入

双方向連結リストでセルAの次にセルXを挿入する処理は以下のようになります.

  1. セルXのnextにセルAのnextの値(=セルAの次のセルへの参照)を代入
  2. セルXのprevにセルAへの参照を代入
  3. セルAのnextの指すセル(=セルAの次のセル)のprevに,セルXへの参照を代入
  4. セルAのnextにセルXへの参照を代入

書き換える個所は要素の数に関わらず4個所だけなので,この処理は定数時間で実行できます.

次は2と3の間に100のセルを挿入したときの図です.書き換わったところを太い矢印で示しました. 番号は上の説明に対応しています.

画像:DListInsert.png

要素の削除

セルXを削除する処理は以下のようになります.これも定数時間で実行できます.

  1. セルXのnextの指すセル(Xの次のセル)のprevに,Xのprevの値を代入
  2. セルXのprevの指すセル(Xの前のセル)のnextに,Xのnextの値を代入

次は上の図の初期状態から2のセルを削除する場合の図です.

画像:DListDelete.png

ところで,リストから削除したセルはどうなるのでしょうか.メモリの中に残ったままにはならないのでしょうか.

心配はいりません.Javaには,ヒープ領域中でどこからも参照されないオブジェクトを検出してメモリ領域を回収する仕組み(ガベージコレクション(Garbage Collection),ゴミ回収の意)があります.このため,参照されていないオブジェクトは自動的に削除されます.(ガベージコレクションのない言語では,オブジェクトの削除を行うのはプログラマの責任になります).

n番目の要素の取得

配列のn番目の要素は data[n] のように書けばアクセスすることができました. この処理は定数時間で行うことができます.

配列はメモリ上の連続した範囲に格納されているため,配列のn番目の要素の場所は (配列の先頭アドレス + 各要素のサイズ * n)ですぐに計算できます. このため,各要素には定数時間でアクセスできるのです.

しかし,連結リストではn番目の要素を取得するには,先頭から順番にn個のセルを辿る必要があります. つまり,nに比例した時間がかかります.

双方向連結リストの実装

Javaでは,Java Collection Frameworkと呼ばれる標準ライブラリがあって,双方向連結リストは java.util.LinkedList クラスとして提供されていますが,ここでは勉強のためにあえて自分で実装することにします.

Java Collection Frameworkは,連結リスト,集合,ハッシュ表などを提供するクラス群です.

Cellクラス

まずはセルを表す Cell クラスを考えます.リストに格納するデータが int 型だった場合,

class Cell {
  // 格納するデータ
  private int data;
  // 次の要素への参照
  private Cell next;
  // 前の要素への参照 
  private Cell prev;
  ...
}

のようにして実現できます.Cellクラスの中でCell型を使っていますが,問題ありません (nextとprevは,Cell型のインスタンスに対する参照を格納します).

問題は,この定義だと格納するデータ型ごとに異なる Cell クラスを定義しないといけない点です(double用Cellクラス,String用Cellクラス...). int の部分を,「何でも良い型」で宣言したいところですね.

Javaでは,この「何でも良い型」として Object (java.lang.Object クラス) を使うことができます. Javaの全ての参照型変数は,Object型の変数に代入することができます. (詳しい説明はクラスの継承を学ぶまで待ってください)

String s1 = "Foo";
Object o1 = s1;           // OK. Stringは参照型
String s2 = o1;           // エラー.次の行のようにキャスト演算子が必要
String s2 = (String)o1;   // OK. キャスト演算子をつければString型に代入可能
int len2 = s2.length();   // OK

int[] array1 = {1, 2, 3};
Object o2 = array1;       // OK.配列は参照型
String s3 = (String)o2;   // 実行時エラー.o2が指すもの(int[])はStringと互換性がない
int[] array2 = (int[])o2; // OK.(int[])はintの配列へのキャスト     

覚えておくべき点:

  • Javaの全ての参照型変数は,Object型の変数に代入できる
  • Object型からもとの型に戻すにはキャスト演算子が必要
  • 別の型にキャストしようとすると,実行時エラーになる

Cell クラスに話を戻すと,private int data; の部分は Object 型を使って private Object data; のようにすれば,いろいろな型を扱うことができるようになります.

以下が Cell クラスのプログラムです.

コンストラクタで,Object型の引数を受け取っていますが,これがこのセルに格納するデータになります.

Cell c = new Cell("Foo"); // Stringを格納

setNextやgetNextのように,インスタンス変数の値を設定・取得するメソッドが並んでいますが,このようなメソッドをsetterメソッド/getterメソッドと呼びます.

// Cellはリストの1要素を表す
public class Cell {
    // リストに格納されるデータへの参照
    private Object data;
    // 次の要素への参照
    private Cell next;
    // 前の要素への参照 
    private Cell prev;
 
    // コンストラクタ
    // next, prevは自動的に null に初期化される
    public Cell(Object o) {
        data = o;
    }
    // nextをセットする 
    public void setNext(Cell next) {
        this.next = next;
    }
    // nextを得る
    public Cell getNext() {
        return next;
    }
    // prevをセットする 
    public void setPrev(Cell prev) {
        this.prev = prev;
    }
    // prevを得る
    public Cell getPrev() {
        return prev;
    }
    // データを得る
    public Object getData() {
        return data;
    }
}

DLinkedListクラス

次に,双方向連結リスト本体のクラスを示します.

基本的な処理は上で書いた通りです.

// 双方向連結リスト (Doubly-Linked List)
public class DLinkedList {
    // ダミーセルへの参照
    private Cell dummy;
    
    // コンストラクタ
    public DLinkedList() {
        // ダミーセルを生成し,nextとprevをダミーセル自身に設定する
        dummy = new Cell(null);
        dummy.setNext(dummy);
        dummy.setPrev(dummy);
    }
    
    // リストの先頭に要素を追加
    public void addFirst(Object data) {
        // セルを生成
        Cell c = new Cell(data);
        c.setNext(dummy.getNext());
        c.setPrev(dummy);
        dummy.getNext().setPrev(c);
        dummy.setNext(c);
    }
    
    // リストの最初の要素を削除して返す
    public Object removeFirst() {
        Cell c = dummy.getNext();
        if (c == dummy) {
            return null;
        }
        c.getNext().setPrev(c.getPrev());
        c.getPrev().setNext(c.getNext());
        return c.getData();
    }
    
    // 最初の要素を返す.空ならば null を返す
    public Object getFirst() {
        Cell c = dummy.getNext();
        if (c == dummy) {
            return null;
        }
        return c.getData();
    }
    
    // index番目の要素を得る.末尾を越えたらnullを返す.
    public Object get(int index) {
        Cell c = dummy.getNext();
        for (int i = 0; i < index; i++) {
            if (c == dummy) {
                return null;
            }
            c = c.getNext();
        }
        return c.getData();
    }
    
    // リストを文字列形式に変換する
    public String toString() {
        // StringBuilderは可変文字列を表すクラス
        StringBuilder sb = new StringBuilder("[");
        for (Cell c = dummy.getNext(); c != dummy; c = c.getNext()) {
            // StringBuilderのappendメソッドで文字列を追加
            sb.append(c.getData());
            if (c.getNext() != dummy) {
                sb.append(", ");
            }
        }
        sb.append("]");
        // 最後に toStringメソッドでStringに変換
        return sb.toString();
    }
}
  • getメソッドでは,for文で先頭からセルを1つづつ辿っています.
  • toString()メソッドでは,リストの全ての要素を","で区切った文字列を返しています.
    • for文の使い方に注目してください.これで先頭のセルから最後のセルまで辿っています.
    • また,StringBuilderクラス(java.lang.StringBuilder,APIドキュメント)を使っているところにも注目してください.
StringBuilderクラスは,Stringと同じように文字列を扱うためのクラスです. Stringクラスは,一度インスタンスを生成したら後から中身を変更することはできません (変更するメソッドが用意されていない). これに対し,StringBuilderクラスは,後から中身を変更できる文字列を扱います. 文字列を追記していくような場合は,String よりも効率的に実現できます.

中には

String s = "foo";
s = s + "bar";

のように書いたら文字列sの中身が書き換わっているのではと思う人もいるかもしれませんが,これは s に "bar" を繋げた新しい String インスタンスを作って,そのインスタンスへの参照を s に代入しなおしているだけです. ヒープメモリ上にある "foo" 自体が書き換わったわけではありません.

Stringのように後から中身を変更できないオブジェクトを不変オブジェクト(immutable object)といいます.不変オブジェクトの良いところは扱うのが楽という点です(中身が書き変わることはないので,参照をコピーすれば中身をコピーしたのと同じになるなど).

StringBuilderクラスはJ2SE5.0で導入されたもので,それ以前のJavaではStringBufferクラスを使います.

サンプルプログラム

DLinkedListクラスを使ったサンプルプログラムを示します.

// DLinkedListを使ったサンプル
public class DListSample {
    public static void main(String[] args) {
        DLinkedList l = new DLinkedList();
        l.addFirst("Tokyo");
        System.out.println(l);
        l.addFirst("Osaka");
        System.out.println(l);
        l.addFirst("Kyoto");
        System.out.println(l);
        l.addFirst("Nara");
        System.out.println(l);
 
        // DLinkedListのgetメソッドはObjectを返すので,Stringにキャストしている
        String s = (String)l.get(2);
        System.out.println("2nd item: " + s);
        // 同様にキャスト
        String removed = (String)l.removeFirst();
        System.out.println("removeFirst() result: " + removed);
        System.out.println(l);
        removed = (String)l.removeFirst();
        System.out.println("removeFirst() result: " + removed);
        System.out.println(l);
    }
}

実行結果:

[Tokyo]
[Osaka, Tokyo]
[Kyoto, Osaka, Tokyo]
[Nara, Kyoto, Osaka, Tokyo]
2nd item: Osaka
removeFirst() result: Nara
[Kyoto, Osaka, Tokyo]
removeFirst() result: Kyoto
[Osaka, Tokyo]

課題11-1(双方向連結リスト)

DLinkedListクラスに以下の機能を付け加えて下さい.

  • 要素数を得るメソッド public int size()
  • 先頭からn番目に,指定した要素を挿入するメソッド public void add(int n, Object o)
    • nは0から数える.ダミーセルは数えない.
  • 先頭からn番目の要素を削除するメソッド public Object remove(int n)
  • 末尾に要素を挿入するメソッド public void addLast(Object o)
  • 末尾の要素を削除して返すメソッド public Object removeLast()

うまく動作することを示すテストプログラムと,実行結果も示すこと.

ヒント

  • 要素数を得るためにいちいち連結リストを辿るのは無駄なので,インスタンス変数で要素数を覚えておくと良い.
  • addやremoveでは,とりあえずn番目のCellにたどり着く必要がある.
  • addLastやremoveLastでは,最後のCellへの参照がダミーセルに格納されていることを利用する.

ラッパークラス

intやdoubleのような基本型変数は参照型ではないので,(基本的には)Object型の変数に代入できません.

このあたりはオブジェクト指向言語らしくないところですが,実行効率を考えてこのような設計になっています

これだと不便なので,Javaではそれぞれの基本型に対応するラッパークラス(wrapper class)が用意されています.ラッパークラスは,基本型の値をオブジェクトとして使用するためのクラスです.

基本型 対応するラッパークラス APIドキュメント
int Integer java.lang.Integer
long Long java.lang.Long
float Float java.lang.Float
double Double java.lang.Double
boolean Boolean java.lang.Boolean

以下のように使用します. Integerクラスのインスタンスへの参照は Object 型に代入できるので,Cellクラスで扱うことができるようになります.

int x = 10;
Integer iobj = new Integer(x);  // intからIntegerのインスタンスを作成
int y = iobj.intValue();        // Integerからintへ変換
Object o = iobj;                // Integer型はObject型に代入できる

double z = 1.23;                // doubleでも同様
Double bar = new Double(z);
double w = bar.doubleValue();

ただし,J2SE 5.0 以降のJavaでは,基本型とラッパークラスとの間の変換を自動的に行う機能(Autoboxing/unboxing)があるため,以下のように書けてしまいます. これはあくまでコンパイラが気を利かせてやっているだけなので(syntax sugar),内部では上で書いたようなコードが実行されています.

int i = 10;
Integer iobj = i;  // intからIntegerへ自動変換
int y = iobj;      // Integerからintへ自動変換
double z = 1.23;
Double bar = z;    // doubleからDoubleへ自動変換
double w = bar;    // Doubleからdoubleへ自動変換
if (i < iobj) {...} // intとIntegerの比較

Cell cell = new Cell(10.2); // doubleからDoubleへの変換

最後の行は,Cellのコンストラクタの引数がObjectであるため,10.2が自動的にDoubleに変換されています.

Copyright (C) 2002-2015 Kota Abe, Osaka City University

ナビゲーション