ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » 配列に要素を追加

配列に要素を追加

投稿者: in 情報構造論, 斉藤徹, 講義録 投稿日:

前回、オブジェクトを扱うプログラムの演習の説明を行ったので、前半は次の講義内容につながる説明を行い、後半はレポート課題の時間とする。

データが登録済みかどうかを判定する処理を作るために、登録された値を配列に次々と値を追加保存する場合、どのようにプログラムを記述するだろうか？

配列にデータを追加

次々と与えられた値を保存していくのであれば、Java であれば下記のようなコードが一般的であろう。
でも、ArrayList とはどのようにデータを覚えているのだろうか? なぜ 宣言は ArrayList<Integer> array であって ArrayList<int> array で宣言するとエラーが出るのであろうか?

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // ArrayList は連続アドレス空間に保存してくれる可変長配列
        //   ランダムアクセスをする場合に向いている
        ArrayList<Integer> array = new ArrayList<Integer>() ;
        array.add( 11 ) ;
        array.add( 2 ) ;
        array.add( 333 ) ;
        
        for( Integer i : array ) {
            System.out.println( i ) ;
        }
    }
}

このような ArrayList のようなデータ構造の仕組みを考えるために、最も単純な配列でプログラムを作ってみる。

末尾に追加

import java.util.*;

public class Main {
    static int[] array = new int[ 10 ] ;
    static int   size  = 0 ;

    public static void add( int x ) {
        array[ size ] = x ;
        size++ ;
    }
    public static void main(String[] args) throws Exception {
        add( 11 ) ;
        add( 2 ) ;
        add( 333 ) ;
        
        for( int i = 0 ; i < size ; i++ )
            System.out.println( array[i] ) ;
    }
}

同じ処理をC言語で書いてみる。

#include <stdio.h>

int array[ 10 ] ;
int size = 0 ;

void add( int x ) {          // if ( size < array.length ) ... の判定が必要かも
    array[ size ] = x ;
    size++ ;
}

int main() {
    add( 11 ) ;
    add( 2 ) ;
    add( 333 ) ;

    for( int i = 0 ; i < size ; i++ )
        printf( "%d\n" , array[ i ] ) ;
    return 0 ;
}

しかし、このプログラムでは、最初に宣言した要素数10個を越えてデータを保存できないし、配列溢れさせないためには要素数の上限チェックも必要となるだろう。

要素数を途中で増やす

前述のプログラムでは、配列のサイズが10件なので10個以上のデータは保存できない。しかし、ArrayList では配列のサイズ設定が不要となっている。

実は、ArrayList 型で配列サイズ以上のデータが入ったときは、2倍の大きさの配列を作って中身のコピーを行うことで、途中でデータ件数を増やすことができる。(元の大きさの何倍とするかは実装によって異なる。2倍ではなく1.5倍??)

import java.util.*;

public class Main {
    static int[] array = new int[ 10 ] ;
    static int   size  = 0 ;

    public static void add( int x ) {
        if ( size >= array.length ) {
            int[] array2 = new int[ array.length * 2 ] ;
            for( int i = 0 ; i < array.length ; i++ )
                array2[ i ] = array[ i ] ;
            array = array2 ;
        }
        array[ size ] = x ;
        size++ ;
    }
    public static void main(String[] args) throws Exception {
        add( 11 ) ; add( 22 ) ; add( 33 ) ; add( 44 ) ; add( 55 ) ;
        add( 66 ) ; add( 77 ) ; add( 88 ) ; add( 99 ) ; add( 111 ) ;
        /* 配列サイズが倍になった後 */
        add( 222 ) ;
        
        for( int i = 0 ; i < size ; i++ )
            System.out.println( array[i] ) ;
    }
}

昇順に並べながら途中に要素を追加

前述のプログラムでは、配列の末尾の場所を size で覚えておき、末尾にデータを追加していた。でも、配列に保存されている値の中から目的の値が含まれているか検索したいのであれば、配列に要素を昇順に保存しておいて2分探索法を使うのが一般的であろう。では、前述のプログラムを昇順で保存するにはどうすべきか？

最も簡単な方法で書くのであれば、下記のようなコードになるかもしれない。

public static void add( int x ) {
    int i ;
    for( i = 0 ; i < size ; i++ ) { // ここは2分探索で書けば O( log N ) にできるかも
        if ( array[ i ] > x )
            break ;
    }
    // for( int j = i ; j < size ; j++ )   // 途中に挿入は、コレじゃダメ?
    //     array[ j + 1 ] = array[ j ] ;
    for( int j = size - 1 ; j >= i ; j-- ) // 途中にデータを入れるために要素を１つ後ろに移動
        array[ j + 1 ] = array[ j ] ;
    array[ i ] = x ;
    size++ ;
}

void add( int x ) {
    int i ;
    for( i = 0 ; i < size ; i++ ) {
        if ( array[ i ] > x )
            break ;
    }
    // for( int j = i ; j < size ; j++ )
    //     array[ j + 1 ] = array[ j ] ;
    for( int j = size - 1 ; j >= i ; j-- )
        array[ j + 1 ] = array[ j ] ;
    array[ i ] = x ;
    size++ ;
}

このプログラムでは、for( i … ) の処理でデータを挿入すべき場所を見つけ、for( int j … ) の繰り返しでデータを1つ後ろにずらしてから要素を加えている。

for( i … ) の処理は、このプログラムでは O( N ) となっているが、2分探索法を用いれば O( log N ) に改善ができるかもしれない。しかし、for( int j… ) の処理は、データを1つ後ろにずらす必要があるため O( N ) の処理が必要となる。

配列のまとめ

  • 配列は、末尾にデータを追加であれば、O( 1 ) で追加可能。
  • 配列に昇順で並べてあれば、特定要素を探すには O( log N ) かかる。
  • 途中にデータを挿入するのであれば、O( N ) の時間がかかる。

ArrayList の使い方

配列に要素を追加するような処理を行う場合、末尾にデータを追加とか、配列サイズが溢れたらサイズを修正するなどの処理を自分で記述するのは面倒なので、ジェネリクス機能を使った ArrayList を用いる。ジェネリクス機能を使うときは、データの型を示す < > の中には、プリミティブ型は書くことができず、オブジェクト型しか書けない。このため、整数型のデータの ArrayList では、ArrayList<Integer> を使う必要がある。

ただし、ArrayList 型の中身は、配列なので、N番目の参照 : O( 1 ) , 単純な検索 : O( N ) , N番目に要素を挿入: O( N ) といった特徴は同じ。

// 通常の配列
int[] array = new int[ 10 ] ;
array[ 0 ] = 11 ;
array[ 1 ] = 22 ;
for( int i = 0 ; i < 2 ; i++ )
    System.out.println( array[ i ] ) ;

// ArrayList を使った配列
ArrayList<Integer> array = new ArrayList<Integer>() ;
array.add( 11 ) ;
array.add( 22 ) ;
for( int i = 0 ; i < array.size() ; i++ ) {
    int item = array.get( i ) ;
    System.out.println( item ) ;
}
for( Integer item : array )
    System.out.println( item ) ;