メタボロミクス講習会 @大阪
Document Actions
双方向リストのインプリメンテーション
双方向リストの実装法を示します。class ListRepが基本クラスで、各セルをListEntryで実装します。
public class ListEntry
{
Object data;
protected ListEntry prev = null;
protected ListEntry next = null;
ListEntry(Object d) { data = d; }
public void assign(Object d) { data = d; }
public Object data() { return data; }
双方向リストの中では前後をprev, nextという名前で参照します。ListRepクラスはグラフのインプリメンテーションでも使いたいのでpublic classにしておきます。
public class ListRep
{
protected ListEntry head;
protected ListEntry tail;
protected int size;
public ListEntry head() { return head; }
public ListEntry tail() { return tail; }
public int size() { return size; }
protected ListEntry pop_front()
{ ListEntry x = head;
if (x != null)
{ ListEntry y = x.succ;
head = y;
if (y != null) y.prev = null;
else tail = null;
x.next = null;
size--;
}
return x;
}
protected ListEntry pop_back()
{ ListEntry x = tail;
if (x != null)
{ ListEntry y = x.prev;
tail = y;
if (y != null) y.next = null;
else head = null;
x.prev = null;
size--;
}
return x;
}
protected void push(ListEntry x)
{ if (size > 0) head.prev = x;
else tail = x;
x.next = head;
head = x;
size++;
}
protected void append(ListEntry x)
{ if (size > 0) tail.next = x;
else head = x;
x.prev = tail;
tail = x;
size++;
}
protected void remove(ListEntry x)
{ ListEntry succ = x.next;
ListEntry prev = x.prev;
if (succ != null)
{ succ.prev = prev; x.next = null; }
else
tail = prev;
if (prev != null)
{ prev.next = succ; x.prev = null; }
else
head = succ;
size--;
}
}
ListEntryという内部のクラスを隠蔽するためにLinkedListというwrapperを実装してみましょう。基本的にListRepの機能を呼び出すだけですが、ListEntryという中身が外部に見えていないことに注意してください。
public class LinkedList extends ListRep
{
public Object front() { return head.data(); }
public Object back() { return tail.data(); }
public Object popFront()
{ return pop_front().data(); }
public Object popBack()
{ return pop_back().data(); }
public push(Object d)
{ ListEntry e = new ListEntry(); e.assign(d);
super.push(e);
}
public append(Object d)
{ ListEntry e = new ListEntry(); e.assign(d);
super.append(e);
}
}