CODEWITHSUNDEEP
pythonlinked-list
Jared Jennings
Jared Jennings

Reputation: 27

Inserting an integer in singly-linked list in sorted order

I need to define the insert_in_ascending_order() method, and I have no idea what I'm doing. What I need the code to do is take input:
Ex:

8 3 6 2 5 9 4 1 7

and output:

1 2 3 4 5 6 7 8 9 

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

    def append(self, new_node):
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def prepend(self, new_node):
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def insert_after(self, current_node, new_node):
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        elif current_node is self.tail:
            self.tail.next = new_node
            self.tail = new_node
        else:
            new_node.next = current_node.next
            current_node.next = new_node
            
    # TODO: Write insert_in_ascending_order() method
    def insert_in_ascending_order(self, new_node):
        if self.head is None:
            new_node.next = self.head
            self.head = new_node
        elif self.head.data >= new_node.data:
            new_node.next = self.head
            self.head = new_node
        else :
            current = self.head

        current = self.head
        while current is not None:
            print (current.data)
            current = current.next
        new_node = current
        current = new_node

Upvotes: 1

Views: 1854

Answers (2)

Axe319
Axe319

Reputation: 4365

You can just let your existing methods do most of the work for you.

If you consider that your head will be the smallest value, and your tail the largest. You can traverse from head to tail till you reach your insertion point.

If at first you take care of a few edge cases.

    def insert_in_ascending_order(self, new_node):
        # the linked list is empty. just append and return
        if self.head is None:
            self.append(new_node)
            return
    
        # the linked list head value is larger than the current value.
        # meaning our new_node value is the smallest in the list
        # just prepend and return
        if new_node.data < self.head.data:
            self.prepend(new_node)
            return
        
        # now you know can assume everything is sorted
        # and start at the head, your smallest value
        # and move forward from that
        current = self.head
        while True:
            # we've reached our tail.
            # let our append method do the work
            # and break from the loop
            if current.next is None:
                self.append(new_node)
                break
            # we've reached our insert point
            # insert and break
            if new_node.data < current.next.data:
                # make the insert points next, our new_nodes next
                new_node.next = current.next
                # and exchange it with our new_node
                current.next = new_node
                break
            # continue on
            current = current.next

Here is the full code with a nice repr.

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, new_node):
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
    
    def prepend(self, new_node):
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def insert_in_ascending_order(self, new_node):
        if self.head is None:
            self.append(new_node)
            return
    
        if new_node.data < self.head.data:
            self.prepend(new_node)
            return
        
        current = self.head
        while True:
            if current.next is None:
                self.append(new_node)
                break
            if new_node.data < current.next.data:
                insert_point_next = current.next
                new_node.next = insert_point_next
                current.next = new_node
                break
            current = current.next
    
    def __repr__(self):
        _repr = '['
        current = self.head
        while current is not None:
            _repr = f'{_repr}{repr(current.data)}, '
            current = current.next
        if _repr.endswith(', '):
            _repr = _repr[:-2]
        return f'{_repr}]'

lst = LinkedList()
for i in [8, 3, 6, 2, 5, 9, 4, 1, 7]:
    lst.insert_in_ascending_order(Node(i))
print(lst) # [1, 2, 3, 4, 5, 6, 7, 8, 9]

Upvotes: 2

Alain T.
Alain T.

Reputation: 42143

You need to track the nodes that will be the predecessor of the one you're inserting while you seek the one that will be its successor.

# start with first node in list
prevNode = None
nextNode = self.head

# find adjacent nodes
while nextNode and nextNode.data < newNode.data:
     prevNode,nextNode = nextNode,nextNode.next

# link to new node
if prevNode: prevNode.next = newNode # insert after
else:        self.head = newNode     # new head

# chain to successor
newNode.next = nextNode
if not nextNode: self.tail = newNode # new tail

Upvotes: 1

Related Questions