Question

I need help Writing a Python code!!!

Implement an ordered list using doubly linked list

Implement the following operations for an ordered list of integers ordered in ascending order using a doubly
linked list. The “head” of the list be where the “smallest items are and let “tail” be where the largest items are.
You may use whatever mechanism you like to keep track of the head and tail of the list. E.g. references or
sentinel nodes.
• OrderedList () creates a new ordered list that is empty. It needs no parameters and returns an empty list.
• add (item) adds a new item to the list making sure that the order is preserved. It needs the item and
returns nothing. Assume the item is not already in the list.
• remove (item) removes the item from the list. It needs the item and modifies the list. Return the position
of removed item if it is in the list, otherwise return -1 (as not found).
• search_forward (item) searches for the item in the list. It needs the item and returns the boolean value
True if the item is in the list and False if the item is not in the list.
• search_backward (item) searches for the item in the list starting from the tail of the list. It needs the
item and returns the boolean value True if the item is in the list and False if the item is not in the list.
• is_empty () tests to see whether the list is empty. It needs no parameters and returns a boolean value.
True if the list is empty and False if any items are in the list.
• size () returns the number of items in the list. It needs no parameters and returns an integer.
• index (item) returns the position of item in the list. It needs the item and returns the index. If it is not in
the item it returns -1(as not found).
• pop () removes and returns the last item in the list. It needs nothing and returns an item.
• pop (pos) removes and returns the item at position pos. It needs the position and returns the item. If it is
not in the item it returns -1(as not found). pop(pos) should compare pos to the size of the list and
search from the head if pos <= size/2 and from the rear if pos > size/2.

Answer 1

class Node(object):
	def __init__(self, initdata):
	self._data = initdata
	self._next = None
	self._prev = None
	@property
	def data(self):
	return self._data
	@property
	def next(self):
	return self._next
	@property
	def prev(self):
	return self._prev
	def set_data(self, newdata):
	self._data = newdata
	return self.data
	def set_next(self, newnext):
	self._next = newnext
	return self.next
	def set_prev(self, newprev):
	self._prev = newprev
	return self.prev
	class DoublyLinkedList(object):
	def __init__(self):
	self.head = None
	def isEmpty(self):
	return self.head is None
	def add(self, item):
	new = Node(item)
	if self.head is None:
	self.head = new
	elif self.head.data > new.data:
	new.set_next(self.head)
	self.head.set_prev(new)
	self.head = new
	else:
	prev = self.head
	cur = self.head.next
	while cur is not None:
	if cur.data > new.data:
	prev.set_next(new)
	new.set_prev(prev)
	new.set_next(cur)
	cur.set_prev(new)
	return new
	prev = cur
	cur = cur.next
	prev.set_next(new)
	new.set_prev(prev)
	return new
	@property
	def size(self):
	count = 0
	cur = self.head
	while cur is not None:
	count += 1
	cur = cur.next
	return count
	def search(self, item):
	cur = self.head
	while cur is not None:
	if cur.data == item:
	return True
	elif cur.data > item:
	return False
	cur = cur.next
	return False
	def remove(self, item):
	if self.head.data == item:
	self.head = self.head.next
	else:
	prev = self.head
	cur = prev.next
	while cur is not None:
	if cur.data == item:
	if cur.next is None:
	prev.set_next(None)
	else:
	prev.set_next(cur.next)
	cur.next.set_prev(prev)
	return True
	prev = cur
	cur = cur.next
	return False
	def index(self, item):
	if self.search(item) == False:
	raise ValueError("Item not in list")
	index = 0
	cur = self.head
	while cur is not None:
	if cur.data == item:
	return index
	index += 1
	cur = cur.next
	return index
	def pop(self, index=None):
	if self.isEmpty():
	raise ValueError("The list is already empty")
	prev = self.head
	cur = prev.next
	if index is None:
	while cur is not None:
	if cur.next is None:
	prev.set_next(None)
	return cur
	prev = cur
	cur = cur.next
	self.head = None
	return prev
	if index == 0:
	self.head = cur
	return prev
	cur_index = 0
	while cur is not None:
	if cur_index == index - 1:
	try:
	prev.set_next(cur.next)
	cur.next.set_prev(prev)
	except:
	prev.set_next(None)
	return cur
	prev = cur
	cur = cur.next
	cur_index += 1
	new_list = DoublyLinkedList()
	print "isEmpty:", new_list.isEmpty()
	new_list.add(10)
	print "isEmpty:", new_list.isEmpty()
	new_list.add(20)
	new_list.add(30)
	new_list.add(40)
	new_list.add(25)
	print "search(15):", new_list.search(15)
	print "search(10):", new_list.search(10)
	print "size:", new_list.size
	print "remove(30):", new_list.remove(30)
	print "size:", new_list.size
	print "index(25):", new_list.index(25)
	print "pop(2):", new_list.pop(2).data
	print "size:", new_list.size
	print "pop(1):", new_list.pop(1).data
	print "size:", new_list.size
	print "pop(1):", new_list.pop(1).data
	print "pop():", new_list.pop().data