Pythonでcircular doubly linked list
後輩が頑張っている課題、さすがに複雑になってきたので自分で実装してみて自分が正しいアドバイスをしているかどうか確認してみることにした。
Pythonの__iter__を使って、リストに対するイテレーションをまとめたので、文字列化する__str__やマッチする物を見つけるfindなんかがとても簡単に書けるようになったのだけど、Javaでこれをやるにはどうするんだっけ。Javaにyieldに相当する機能はあったっけ。Iteratorを返すメソッドとか作って、拡張for文を使わないといけないかな。うーん。教えるべきか教えざるべきか、それが問題だ。
追記：addBeforeはheadの前に追加されたのかどうかを自分で判定してself.headを更新するようにしないと、外から利用するときに面倒なので修正。あとその変更に伴い、addTailがaddBeforeを呼び出してはいけなくなった(addTailもaddHeadも要素の追加される位置は同じ、self.headが更新されるかどうかだけが違う)ので、もっとプリミティブなaddBetweenメソッドを作成。deleteメソッドでheadを消した場合の処理が正しくなかったので修正。
# -*- coding: cp932 -*-
class Element:
def __init__(self, v):
self.value = v
def __str__(self):
return str(self.value)
def pop(self):
"自分をリストから取り除く"
prev = self.prev
next = self.next
next.prev = prev
prev.next = next
class DList:
"circular doubly linked list"
def __init__(self):
self.clear()
def clear(self):
"空にする"
self.head = None
def addBefore(self, v, target):
"指定されたエレメントの手前に要素を追加する"
prev = target.prev
next = target
e = self.addBetween(v, prev, next)
if target == self.head:
self.head = e
return e
def addBetween(self, v, prev, next):
"指定されたエレメントの間に要素を追加する"
e = Element(v)
prev.next = e
next.prev = e
e.next = next
e.prev = prev
return e
def addHead(self, v):
"headの位置に要素を追加する"
if self.head:
e = self.addBefore(v, self.head)
self.head = e
else:
self._addFirstElement(v)
def addTail(self, v):
"tailの位置に要素を追加する"
if self.head:
e = self.addBetween(v, self.head.prev, self.head)
else:
self._addFirstElement(v)
def find(self, v):
"値vを持つ最初のエレメントを返す"
for x in xs:
if x.value == v:
return x
def delete(self, e):
"指定されたエレメントを削除する(削除したエレメントを返す)"
if e.prev == e:
self.clear()
elif self.head == e:
self.head = e.next
else:
e.pop()
return e
def _addFirstElement(self, v):
"空のリストに追加する場合の処理"
e = Element(v)
e.prev = e
e.next = e
self.head = e
def __iter__(self):
if self.head:
yield self.head
cur = self.head.next
while cur != self.head:
yield cur
cur = cur.next
def __str__(self):
result = "["
result += ", ".join(str(x) for x in self)
result += "]"
return result
if __name__ == "__main__":
xs = DList()
xs.addHead(1)
print xs.delete(xs.find(1))
print xs
xs.addHead(2)
xs.addHead(3)
xs.addTail(4)
xs.addTail(5)
print xs.delete(xs.find(4))
print xs
