Sorted Doubly Linked List

Question

I want to create a class sort itself with add and remove function, here is my code:

class SortedList(object):
    def __init__(self):
        self.head=None 
        self.tail=None

    def add (self, add_obj):
        newNode=DLLNode(add_obj)
        current=self.head
        if current==None:
            self.head=self.tail=newNode
        else:
            while add_obj>current.data:
                current=current.next_node
            newNode.next_node=current
            newNode.prev_node=current.prev_node
            current.prev_node.next_node=newNode
            current.prev_node=newNode

    def remove (self, element):
        current=self.head
        while element != current.data:
            current=current.next_node
        current.next_node.prev_node=current.prev_node
        current.prev_node.next_node=current.next_node
        current=None

I tried to run it but it failed. Could anyone let me know why?

Answer 1

Looking at the logic for your add function , I can see some problems -

1. Once you have added an element, that is once your self.head and self.tail are no longer - None - , you are doing a while loop to find if the add_obj is greater than current.data . But the while loop is wrongly written. Lets assume , we have only put 1 element in the linked list, and we are trying to add a data that is greater than current , current will become current.next_node , which is currently None , then you again try to do same check, this time you try to access data property of None object which results in Error. Similar issue exists with your remove code.

2. Secondly, in your add function, you are only taking care of greater than head, what if later on you add an object which is less than all other elements, you have to add it to the self.head , but that case is not handled.

3. You are not handling addition an element that is greater than all other elements in the list currently, in this case, I think you intended to make self.tail the element at the highest value, but you are not doing that either.

Answer 2

def add (self, add_obj):
        newNode=DLLNode(add_obj)
        current=self.head
        if current==None:
            self.head=self.tail=newNode
        else:
            if add_obj<current.data:
                self.head.prev_node=newNode
                newNode.next_node=self.head
                self.head=newNode
                self.head.prev_node=None
            else:
                while add_obj>current.data:
                    current=current.next_node
                if current != None:
                    newNode.next_node=current
                    newNode.prev_node=current.prev_node
                    current.prev_node.next_node=newNode
                    current.prev_node=newNode
                else:
                    self.tail.next_node=newNode
                    newNode.prev_node=self.tail
                    self.tail=newNode
                    self.tail.next_node=None