双方向リストとdeque

双方向リストの関数作成

先週の説明で、双方向の基礎的なプログラムの意味が分かった所で、練習問題。

先のプログラムでは、1,2,3 を要素とするリストを、ナマで記述していた。実際には、どんなデータがくるか分からないし、指定したポインタ p の後ろに、データを1件挿入する処理 bd_insert( p , 値 ) , また、p の後ろのデータを消す処理 bd_delete( p ) を書いてみよう。

Javaの場合

public class Main {
    // 指定したノードの後ろに1件追加
    static void bd_insert( BDListNode p , int d ) {
        p.next = new BDListNode( null , d , p.next ) ;
        p.next.next.prev = p.next ;
        p.next.prev = p ;
    }
    // 指定したノードの後ろを1件削除
    static void bd_delete( BDListNode p ) {
        p.next = p.next.next ;
        p.next.prev = p ;
    }
    public static void main(String[] args) throws Exception {
        // 双方向リストの追加,削除            
        BDListNode top2
            = new BDListNode( null , 1 ,
                 new BDListNode( null , 2 ,
                    new BDListNode( null , 4 , null ) ) ) ;
        top2.next.prev = top2 ;
        top2.next.next.prev = top2.next ;
        
        // 途中に挿入の実験
        bd_insert( top2.next , 3 ) ;
        for( BDListNode p = top2 ; p != null ; p = p.next )
            System.out.println( p.data ) ; // 1,2,3,4
        for( BDListNode p = top2.next.next.next ; p != null ; p = p.prev )
            System.out.println( p.data ) ; // 4,3,2,1
        
        // 途中を削除の実験
        bd_delete( top2.next ) ;
        for( BDListNode p = top2 ; p != null ; p = p.next )
            System.out.println( p.data ) ; // 1,2,4
        for( BDListNode p = top2.next.next ; p != null ; p = p.prev )
            System.out.println( p.data ) ; // 4,2,1
    }
}

C言語の場合

// 双方向リストの指定場所 p の後ろに、値 d を要素とするデータを挿入せよ。
void bd_insert( struct BD_List* p , int d ) {
   struct BD_List*n = bd_cons( p , d , p->next ) ;
   if ( n != NULL ) {
      p->next->prev = n ;
      p->next = n ;
   }
}

// 双方向リストの指定場所 p の後ろのデータを消す処理は？
void bd_delete( struct BD_List* p ) {
   struct BD_List* d = p->next ;
   d->next->prev = p ;
   p->next = d->next ;
   free( d ) ;
}

// この手のリスト処理のプログラムでは、命令の順序が重要となる。
// コツとしては、修正したい箇所の遠くの部分を操作する処理から
// 書いていくと間違いが少ない。

番兵と双方向循環リスト

前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか？
bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか？

同じく、bd_delete() だが、データの先頭のデータを消したい場合は、どう呼び出せば良いだろうか？
また、データを消す場合、最後の1件のデータが消えて、データが0件になる場合、bd_delete() は正しく動くだろうか？

こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。そこで、一般的には 循環リストの時にも紹介したが、番兵(Sentinel) を置くことが多い。

しかし、先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、循環リストにした方が便利となる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。

deque(両端キュー)

双方向循環リストを使うと、(1)先頭にデータを挿入(addFirst/unshift)、(2)先頭のデータを取り出す(removeFirst/shift)、(3)末尾にデータを追加(addLast/push)、(4)末尾のデータを取り出す(removeLast/pop)、といった処理が簡単に記述できる。この4つの処理を使うと、単純リスト構造で説明した、待ち行列(queue)やスタック(stack) が実現できる。この特徴を持つデータ構造は、先頭・末尾の両端を持つ待ち行列ということで、deque (double ended queue) とも呼ばれる。

先頭への挿入/削除

末尾への挿入削除

import java.util.*;

class BDListNode {
    BDListNode prev ;
    int        data ;
    BDListNode next ;
    
    BDListNode( BDListNode p , int d , BDListNode n ) {
        this.prev = p ;
        this.data = d ;
        this.next = n ;
    }
    BDListNode() {
        this.prev = this ;
        this.data = -1 ; // dummy
        this.next = this ;
    }
}

public class Main {
    static void addFirst( BDListNode p , int d ) {
        p.next = new BDListNode( p , d , p.next ) ;
        p.next.next.prev = p.next ;
    }
    static int removeFirst( BDListNode p ) {
        int ans = p.next.data ;
        p.next = p.next.next ;
        p.next.prev = p ;
        return ans ;
    }
    static void addLast( BDListNode p , int d ) {
        p.prev = new BDListNode( p.prev , d , p ) ;
        p.prev.prev.next = p.prev ;
    }
    static int removeLast( BDListNode p ) {
        int ans = p.prev.data ;
        p.prev = p.prev.prev ;
        p.prev.next = p ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        BDListNode top = new BDListNode() ;
        // 先頭で Stack
        addFirst( top , 11 ) ;
        addFirst( top , 22 ) ;
        System.out.println( removeFirst( top ) ) ;
        System.out.println( removeFirst( top ) ) ;
        // 末尾で Stack
        addLast( top , 33 ) ;
        addLast( top , 44 ) ;
        System.out.println( removeLast( top ) ) ;
        System.out.println( removeLast( top ) ) ;
        // Queue として使う
        addFirst( top , 55 ) ;
        addFirst( top , 66 ) ;
        System.out.println( removeLast( top ) ) ;
        System.out.println( removeLast( top ) ) ;
    }
}

• 双方向リストとDeque

Javaでの LinkedList(Deque) のクラスの使い方

Javaで Deque のような双方向リスト(2重リスト)を使うには、LinkedList<E> を用いる。クラス宣言などで <E> の内側に型Eを指定する機能はジェネリクスと呼ばれる。クラス名に Deque というのもあるけど、LinkedList などの内部の処理を記述するために使われているものなので、ユーザが直接 Deque クラスを使うことはない。

LinkedList でデータ構造を宣言する場合には、LinkedList<E> のように、どのテータ構造を要素にもつ LinkedList なのかを指定する。ただし int,double といったプリミティブ型を型の欄に書くことはできない。こういった場合には Integer,Double といったオブジェクトを記載すること。

また、リストの要素で繰り返しをする場合には、for( 型 item : LinkedList型 ) {…} のように書けば、繰り返しが記述できる。

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        LinkedList<Integer> lst = new LinkedList<Integer>() ;
        lst.addFirst( 11 ) ;  // lst の先頭に11を挿入
        lst.addFirst( 22 ) ;  // lst の先頭に22を挿入
        for( Integer item : lst ) {
            System.out.println( item ) ;
        }
        lst.addLast( 33 ) ;   // lst の末尾に33を追加
        // 全要素の繰り返し
        for( Integer item : lst ) {
            System.out.println( item ) ;
        }
        // 先頭を取り出す
        while( !lst.isEmpty() ) { // isEmpty() : lst の要素が空か判定する
            System.out.println( lst.removeFirst() ) ; // lstの先頭要素を取り出す
        }
    }
}

• ジェネリクスを使ったLinkedListの例

LinkedList クラスは双方向リストだけど、単純リスト専用のクラスは無い。このため、これまでの授業のように自分でクラスを宣言して使う必要がある。

ArrayList クラス

これと同じように自由な配列サイズのデータクラスとして、ArrayListクラスも存在する。以下の例は、ArrayList<Integer> の使用例。

ArrayList はジェネリクスを使った、要素数を増やすことができる配列である。

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        ArrayList<Integer> lst = new ArrayList<Integer>() ;
        lst.add( 11 ) ;
        lst.add( 22 ) ;
        for( Integer item : lst ) {
            System.out.println( item ) ;
        }
        lst.add( 33 ) ;
        for( Integer item : lst ) {
            System.out.println( item ) ;
        }
        for( int x = 0 ; x < lst.size() ; x++ ) {
            System.out.println( lst.get( x ) ) ;
        }
    }
}

• ジェネリクスを使ったArrayListの例

型推論

上記のプログラムで、LinkedList<Integer> lst = new LinkedList<Integer>() ; で宣言しているが、初期化の右辺と左辺で型を揃える必要があるが、複雑な型だとプログラムが煩雑になる。このため、最近の Java には型推論の機能があるため、下の様に型を省略して記述できる。

LinkedList<Integer> lst = new LinkedList<Integer>() ; // 型推論なし
LinkedList<Integer> lst = new LinkedList<>() ;        // 後半のIntegerは明らか
var lst = new LinkedList<Integer>() ; // lst の型は new LinkedList<Integer> で明らか

for( Integer item : lst ) { ... } // 型推論なし
for( var     item : lst ) { ... }     // 型推論でIntegerを省略

LinkedListとArrayListの違い

LinkedList や ArrayList は同じ使い方ができるようにadd(int,E),get(int)クラスメソッド等が定義されている。しかし、LinkedList は双方向リスト、ArrayList は配列を使って実装されているので、同じ名前のメソッドでもそのメソッドの処理時間には、以下のような特徴がある。

処理時間のオーダ	LinkedList	ArrayList	メソッドの機能
addLast(E e) / add(E e)	O(1)	O(1)	リストの末尾に要素を追加
add(int index, E e)	指定した場所探しにO(N) その場所に挿入O(1)	指定した場所探しにO(1) その場所に挿入O(N)	リストの指定したインデックスに要素を追加
addFirst(E e) / add(0, E e)	先頭に挿入O(1)	先頭に挿入O(N)	リストの先頭に要素を追加
E get(int index)	O(N)	O(1)	リストのインデックス番目を参照

理解確認

• ジェネリックス ArrayList, LinkedList を使って逆順のリストを作る、最小値を探すプログラムを作成せよ。
  LinkedListで逆順,最小値を返す練習問題
• 型推論とは何か?