ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » 双方向リストとdeque

双方向リストとdeque

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

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 ) ) ;
    }
}

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

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 ) ) ;
        }
    }
}

型推論

上記のプログラムで、LinkedList<Integer> lst = new LinkedList<Integer&gt() ; で宣言しているが、初期化の右辺と左辺で型を揃える必要があるが、複雑な型だとプログラムが煩雑になる。このため、最近の 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 メソッドの機能
addFirst(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) リストのインデックス番目を参照

理解確認


	


    

        
タグ: , ,