class RNode:
	def __init__(self, val, next = None, prev = None):
		self.value = val
		if next and prev:
			self._prev, self._next = prev, next
			prev._next = next._prev = self
		else:
			self._prev = self._next = self
	def next(self):
		return self._next
	def __iter__(self):
		return self

class RList:
	def __init__(self, list = None):
		self._first = None
		if list:
			for x in list:
				self.insert(x)
	def insert(self, val, node = None):
		node = node or self._first
		if node:
			newnode = RNode(val, node, node._prev)
		else:
			self._first = RNode(val)
	def erase(self, node):
		if node == self._first:
			if self._first == self._first._next:
				self._first._next = self._first._prev = None
				self._first = None
				del node
				return self._first
			else:
				self._first = self._first._next
		prev = node._prev
		next = node._next
		prev._next = next
		next._prev = prev
		node._prev = node._next = None
		del node
		return next
	def find(self, val):
		node = self._first
		last = node._prev
		while node.value != val and node != last:
			node = node.next()
		if node.value == val:
			return node
		elif last.value == val:
			return last
		return None
	def clear(self):
		if not self._first:
			return
		if self._first._next == self._first:
			self._first._next = self._first._prev = None
			del self._first
			return
		node = self._first._next
		while node != self._first:
			tmp, node = node, node._next
			tmp._next = None
			tmp._prev = None
			del tmp
		node._prev = node._next = None
	def __iter__(self):
		return self._first

if __name__ == '__main__':
	rlist = RList(range(9))
	node = iter(rlist)
	n = 0
	while n < 81:
		assert n % 9 == node.value
		node = node.next()
		n += 1
	node = rlist.find(7)
	assert node.value == 7
	assert rlist.erase(node).value == 8
	node = rlist.find(7)
	assert node == None
	node = rlist.find(8)
	assert node.value == 8
	assert rlist.erase(node).value == 0
	n = 0
	node = iter(rlist)
	while n < 81:
		assert n % 7 == node.value
		node = node.next()
		n += 1