How to create add and remove function in a sorted doubly linked list

137 views Asked by At

Here are the three classes: the node, the doubly linked list, and a sorted list which implement on the doubly linked list. Here is my code:

 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
class SortedList(object):
  def __init__(self, sequence = []):
    if len(sequence)==0:
      self.head = None
      self.tail = None
    else:
      cur_node = None
      prev_node = None
      sequence.sort()
      sequence.reverse()
      for element in sequence:
        prev_node = cur_node
        cur_node = DLLNode(element, cur_node, prev_node)
        self.head = cur_node
        self.tail = DLLNode(sequence[0])

For the sorted list class I need to create an add and remove function. However, I dont really know how to do it. Could anyone let me know?

0

There are 0 answers