Aritalab:Lecture/Programming/Java/LinkedList - Revision history

Adm at 01:13, 19 May 2011

2011-05-19T01:13:58Z

Adm at 05:20, 21 October 2010

2010-10-21T05:20:51Z

Adm: /* Double-linked List */

2010-10-13T05:21:10Z

‎Double-linked List

Adm at 05:19, 13 October 2010

2010-10-13T05:19:35Z

Adm at 08:26, 7 October 2010

2010-10-07T08:26:17Z

Adm at 16:21, 5 October 2010

2010-10-05T16:21:42Z

Adm at 16:06, 5 October 2010

2010-10-05T16:06:36Z

Adm at 10:04, 5 October 2010

2010-10-05T10:04:41Z

Adm at 10:02, 5 October 2010

2010-10-05T10:02:42Z

Adm: New page: 二重リンクリスト ;File List.java

 class ListRep { // publicなclassではない（List.java中に書ける。）   Object obj;   ListRep(Object o) { obj = o; } // コンス...

2010-10-05T10:02:10Z

New page: 二重リンクリスト ;File List.java <pre> class ListRep { // publicなclassではない（List.java中に書ける。） Object obj; ListRep(Object o) { obj = o; } // コンス...

New page

二重リンクリスト

;File List.java
<pre>
class ListRep { // publicなclassではない（List.java中に書ける。）
Object obj;
ListRep(Object o) { obj = o; } // コンストラクタ
ListRep prev;
ListRep next;
public Object inf() { return obj; }
}

public class List {
ListRep head =null;
ListRep tail =null;
int size =0;

List() {} //コンストラクタ

void push(Object o)
{ ListRep r = new ListRep(o);
if (size > 0) head.prev = r; else tail = r;
r.next = head;
head = r;
size++;
}

Object pop()
{ ListRep x = head;
if (x != null)
{ ListRep y = x.next;
head = y;
if (y != null) y.prev = null; else tail = null;
size--;
return x.inf();
}
else
{ System.err.println("Accessing empty list.");
System.exit(1);
}
}

void append(Object o)
{ ListRep r = new ListRep(o);
if (size > 0) tail.next = r; else head = r;
r.prev = tail;
tail = r;
size++;
}

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

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

@@ Line 32: / Line 32: @@
    LinkedList() {}
-   void push(GENTYPE o)
+   void push(GENTYPE o) // リストの先頭に追加
    { ListRep r = new ListRep<GENTYPE>(o);
      if (size > 0) head.prev = r; else tail = r;
@@ Line 40: / Line 40: @@
+   }
-   void append(GENTYPE o)
+   void append(GENTYPE o) // リストの末尾に追加
    { ListRep r = new ListRep<GENTYPE>(o);
      if (size > 0) tail.next = r; else head = r;
@@ Line 47: / Line 47: @@
      size&#43;&#43;;
+   }
+</pre>
-   GENTYPE pop()
+<pre>
    { ListRep x = head;
      if (x != null)
@@ Line 63: / Line 64: @@
+   }
-   GENTYPE peek()
+   GENTYPE peek() // リストの先頭を参照
    { if (head != null)
        return (GENTYPE)head.inf();

@@ Line 15: / Line 15: @@
 ;ジェネリック機能を用いた二重リンクリスト LinkedList.java
 <pre>
-class ListRep<GENTYPE> { // リストに使うコンテナクラス。外部には見せない。
+// リスト実装に使うコンテナクラス。外部には見せない。
    GENTYPE obj;
    ListRep(GENTYPE o) { obj = o; }

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

@@ Line 15: / Line 15: @@
 ;ジェネリック機能を用いた二重リンクリスト LinkedList.java
 <pre>
-class ListRep<GENTYPE> { // 値のコンテナクラス。外部には見せない。
+class ListRep<GENTYPE> { // リストに使うコンテナクラス。外部には見せない。
    GENTYPE obj;
    ListRep(GENTYPE o) { obj = o; }

@@ Line 15: / Line 15: @@
 ;ジェネリック機能を用いた二重リンクリスト LinkedList.java
 <pre>
-class ListRep<GENTYPE> {
+class ListRep<GENTYPE> { // 値のコンテナクラス。外部には見せない。
    GENTYPE obj;
    ListRep(GENTYPE o) { obj = o; }

@@ Line 85: / Line 85: @@
+}
 </pre>
-実行結果
+;実行結果
 <pre>
 $ javac LinkedList.java
@@ Line 95: / Line 96: @@
 </pre>
 プログラムをよく見ると、<tt>pop()</tt>メソッドの戻り値の型はメソッドの中身だけからはわかりません。
-そのため、<tt>(GENTYPE)x.inf()</tt>と参照した値をキャストするため「安全ではありません」という警告が出ています。
+戻り値をキャストするのに<tt>(GENTYPE)x.inf()</tt>と書いているため、コンパイル時に「安全ではありません」という警告が出てきます。（利用には問題ありません。）

@@ Line 1: / Line 1: @@
-二重リンクリスト
+==Double-linked List==
-;File LinkedList.java
+;ジェネリック機能を用いた二重リンクリスト LinkedList.java
 <pre>
-class ListRep { // publicなclassではないのでList.java中に書ける。
+class ListRep<GENTYPE> {
-   Object obj;
+   GENTYPE obj;
-   ListRep(Object o) { obj = o; } // コンストラクタ
+   ListRep(GENTYPE o) { obj = o; }
    ListRep prev;
    ListRep next;
-   public Object inf() { return obj; }
+   public GENTYPE inf() { return obj; }
+}
-public class LinkedList {
+public class LinkedList<GENTYPE> {
    ListRep head =null;
    ListRep tail =null;
    int size =0;
-   LinkedList() {}           //コンストラクタ
+   LinkedList() {}
-   void push(Object o)
+   void push(GENTYPE o)
-   { ListRep r = new ListRep(o);
+   { ListRep r = new ListRep<GENTYPE>(o);
      if (size > 0) head.prev = r; else tail = r;
      r.next = head;
@@ Line 26: / Line 38: @@
+   }
-   Object pop()
+   void append(GENTYPE o)
    { ListRep x = head;
      if (x != null)
@@ Line 33: / Line 53: @@
          if (y != null) y.prev = null; else tail = null;
          size--;
-         return x.inf();
+         return (GENTYPE)x.inf();
+       }
-     else
+     else {
-       { System.err.println("Error: empty list"); }
+       System.err.println("Error: empty list (function pop)");
+   }
-   void append(Object o)
+   GENTYPE peek()
-   { ListRep r = new ListRep(o);
+   { if (head != null)
-    if (size > 0) tail.next = r; else head = r;
+      return (GENTYPE)head.inf();
-    r.prev = tail;
+    else {
-    tail = r;
+      System.err.println("Error: empty list (function peek)");
-     size&#43;&#43;;
+      return null;
+   }
@@ Line 52: / Line 75: @@
    //サンプルプログラム
    static public void main(String[] args)
-   { LinkedList L = new LinkedList();
+   { LinkedList<Integer> L = new LinkedList<Integer>();
-     for(int i=0; i < 10; i++)
+     for(int i=0; i < 100; i++)
        L.push(i);
      while (!L.empty())
-       System.out.println(L.pop());
+       sum += L.pop();
+   }
+}
 </pre>