I need help Writing a Python code!!! Implement an ordered list using doubly link

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.

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.