Aritalab:Lecture/Programming/Java/LinkedList

Revision as of 19:02, 5 October 2010

二重リンクリスト

File List.java

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