Insert In Ordered Linked List (python)

I am having trouble creating an insert function for an ordered Linked List. Here is what I have so far: class Node: def __init__(self, initial_data): self.data = initia

Solution 1:

You need to insert your item into the list. That means you need to:

• Break up the chain at the place you are going to insert
• Create a new node
• Join up the chain again with your new node in the middle.

You don't technically need to break up the chain, as setting the next link on the previous item will clear the old link, so all you need to do still is join up the chain again:

while data > other.get_data():
    previous = other
    other = other.get_next()
new = Node(data)
previous.set_next(new)
new.set_next(other)

I also corrected a different error, you didn't callNode.get_next().

Next, you need to think more about edge cases. What happens when you get to the end of your chain but haven't found any node where node.get_data() is greater than your inserted data?

You need to adjust your while loop to make sure that you test for that case; other will be None for the last element of the chain:

while other isnot None and data > other.get_data():
    previous = other
    other = other.get_next()
new = Node(data)
previous.set_next(new)
new.set_next(other)

There are other things you can do to improve your code. There is no need to use setters and getters in Python; there is no cost involved in turning attributes to @propertys in the future, so just use attributes here.

You could also make your Node() accept a next element in the constructor, that'd make inserting an element easier.

You can use str.join() to insert a fixed string between elements of a sequence. Put all your data attributes into a Python list and join that list.

You do not need to set self.head as the next node when creating an initial element (when self.head is None); that's the default already anyway:

classNode:
    def__init__(self, initial_data, next=None):
        self.data = initial_data
        self.next = nextclassLinkedList:
    def__init__(self):
        self.head = Nonedef__str__(self):
        data_list = []    
        current = self.head
        while current isnotNone:
            data_list.append(str(current.data))
            current = current.nextreturn'->'.join(data_list)

    definsert(self, data):
        other = self.head
        previous = Noneif other isNone:
            self.head = Node(data)
        else:
            while other isnotNoneand data > other.data:
                previous = other
                other = other.next
            previous.next = Node(data, other)

Demo:

>>>ll = LinkedList()>>>str(ll)
''
>>>ll.insert(10)>>>str(ll)
'10'
>>>ll.insert(20)>>>str(ll)
'10->20'
>>>ll.insert(15)>>>str(ll)
'10->15->20'

Solution 2:

I think changing this:

else:
            whiledata > other.get_data():
                previous = other
                other = other.get_next
            previous.set_next(Node(data))

to this, should make it work.

else:
            # First condition will short circuit so there won't be exception on calling other.get_data() if other is Nonewhile other isnotNoneand data > other.get_data():
                previous = other
                other = other.get_next()
            node = Node(data)
            node.set_next = previous.get_next()
            previous.set_next(node)

Also, getter and setter methods aren't really necessary in python. The convention is to use @property annotation if you need that kind of behavior and private members are usually prefixed with one _.