Aritalab:Lecture/Programming/Java/LinkedList

Latest revision as of 10:13, 19 May 2011

[edit] Double-linked List

二重リンクリストは最も単純なデータ構造の一つで、スタックやキューの実装として利用できます。

ここでは、C++のテンプレートに相当するJavaのジェネリック機能を用いたプログラムを紹介します。 ジェネリック型がわかりにくい人は、プログラム中のGENTYPE型をすべてObject型に置き換え、クラス定義やnew構文にある<GENTYPE>を全て消去すればObject型を用いた実装になります。

ジェネリック機能を用いた二重リンクリスト LinkedList.java

// リスト実装に使うコンテナクラス。外部には見せない。
// public class としなければ、ファイル LinkedList.java 中に定義できます。
class ListRep<GENTYPE> {
  GENTYPE obj;
  ListRep(GENTYPE o) { obj = o; }
  ListRep prev;
  ListRep next;
  public GENTYPE inf() { return obj; }
}

public class LinkedList<GENTYPE> {
  ListRep head =null;
  ListRep tail =null;
  int size =0;

  LinkedList() {}

  void push(GENTYPE o) // リストの先頭に追加
  { ListRep r = new ListRep<GENTYPE>(o);
    if (size > 0) head.prev = r; else tail = r;
    r.next = head;
    head = r;
    size++;
  }

  void append(GENTYPE o) // リストの末尾に追加
  { ListRep r = new ListRep<GENTYPE>(o);
    if (size > 0) tail.next = r; else head = r;
    r.prev = tail;
    tail = r;
    size++;
  }

  GENTYPE pop() // リストの先頭から削除
  { ListRep x = head;
    if (x != null)
      { ListRep y = x.next;
        head = y;
        if (y != null) y.prev = null; else tail = null;
        size--;
        return (GENTYPE)x.inf();
      }
    else { 
      System.err.println("Error: empty list (function pop)");
      return null;
    }
  }

  GENTYPE peek() // リストの先頭を参照
  { if (head != null)
      return (GENTYPE)head.inf();
    else {
      System.err.println("Error: empty list (function peek)");
      return null;
    }
  }

  int size() { return size; }
  boolean empty() { return (size==0); }

  //サンプルプログラム
  static public void main(String[] args)
  { LinkedList<Integer> L = new LinkedList<Integer>();
    for(int i=0; i < 100; i++)
      L.push(i);
    int sum=0;
    while (!L.empty())
      sum += L.pop();
    System.out.println(sum);
  }
}

実行結果

0から100までの数字を逆順に取り出して（スタック）、和をとっています。

$ javac LinkedList.java
注:LinkedList.java の操作は、未チェックまたは安全ではありません。
注:詳細については、-Xlint:unchecked オプションを指定して再コンパイルしてください。

$ java LinkedList
4950

プログラムをよく見ると、pop()メソッドの戻り値の型はメソッドの中身だけからはわかりません。 戻り値をキャストするのに(GENTYPE)x.inf()と書いているため、コンパイル時に「安全ではありません」という警告が出てきます。（利用には問題ありません。）