Sorted List for Doubly Linked List

Question

I have following 2 classes node and doublylinked list

class DLLNode(object):
  def __Init__ (self, data, prev_node=None, next_node=None):
    self.data=data
    self.prev_node=prev_node
    self.next_node=next_node

  def __str__(self):
    return str(self.data)

class DoublyLinkedList(object):
  def __init__(self, head=None, tail=None):
    self.head=head
    self.tail=tail
    self.size=0

  def add_to_head(self, data):
    newNode = DLLNode(data)
    if self.head==None:
      self.head=self.tail=newNode
      self.head.prev_node=self.tail.next_node=None
    else:
      self.head.prev_node=newNode
      newNode.next_node=self.head
      self.head=newNode

  def add_to_tail(self, data):
    newNode=DLLNode(data)
    if self.head==None:
      self.head=self.tail=newNode
      self.head.prev_node=self.tail.next_node=None
    else:
      self.tail.next_node=newNode
      newNode.prev_node=self.tail
      self.tail=newNode
      self.tail.next_node=None

  def remove_head(self):
    node=self.head
    if self.head==self.tail:
      self.prev_node=self.next_node=self.head=self.tail=None
      return
    if self.head!=self.tail:
      node=node.next_node
      node.prev_node=None
      self.head=node

  def remove_tail(self):
    node=self.tail
    if self.head==self.tail:
      self.prev_node=self.next_node=self.head=self.tail=None
      return
    if self.head!=self.tail:
      self.tail=node.prev_node
      self.tail.next_node=None


  def index(self,element):
    current = self.head
    while current != None:
      if current.data == element:
      return current.position
    else:
      current = current.next
      return -1

I want to create a third class called SortedList, which is a subclass for DoublyLinkedList class. The class should have add and remove which add and remove object to the list, and keep the list sorted. And a 'middle' method to return the middle element of the list. Not sure how I should create this class, a little confused.

Answer 1

If you want a list to remain sorted, ensure that you insert elements into it in sorted position. Finding this position should be straightforward.

The doubly linked list class, has only a Double Ended Queue (dequeue) interface, so insertion isn't actually possible with the current methods and you will need to write this yourself.

Furthermore, extending the doubly linked list doesn't make that much sense since the add_to_head and add_to_tail methods aren't valid operations for a sorted list which should only allow a single "insert" (possibly called 'add', name is unimportant) which might put something at the head or the tail but could put it anywhere. Because of this you may want to consider a different inheritance hierarchy.

Finally for the keeping track of the middle element, you need to decide what middle means in the context of an even-length list, then when you:

• insert something before the middle of the list, you might need to change the middle to its predecessor
• insert something after the middle of the list, you might need to change the middle to its successor,
• delete something before the middle of the list, you might need to change the middle to it successor
• delete something after the middle of the list, you might need to change the middle to its predecessor
• delete the middle of the list, you will need to set the middle to either its predecessor or successor

Exactly how you need to handle each of these situations will depend on how you define the middle of an even length list and whether the list is changing to an even or odd length. Make sure to consider each case carefully to get them all correct.