Inserting node at specified index in Linked Lists

Question

I'm writing the code for Linked Lists and I'm confused when I want to insert a new node at the specified position. I'm wondering why we decrease the position by 1? Here is the code:

def insert(self, data, index):
        """
        Inserts a new Node containing data at index position
        Insertion takes O(1) time but finding the node at the 
        insertion point takes O(n) time. 
        """
        if index == 0:
            self.add(data)
        
        if index > 0:
            new = Node(data)
            
            position = index
            current = self.head
            current.next_node
            
            while position > 1:
                current = new.next_node
                position -= 1
                
            prev_node = current
            next_node = current.next_node
            
            prev_node.next_node = new
            new.next_node = next_node

luk2302 · Accepted Answer · 2022-04-11 13:55:50Z

1

The reason you do it is that you try to move the current forward index elements.
How you do that does not matter, whether you decrease the position by one, do a different loop or do something entirely different - as long as you do current = new.next_node index times.

And that is exactly what

while position > 1:
    current = new.next_node
    position -= 1

does. It runs that statement index times since position = index to begin with. An alternative would be

for _ in range(index):
    current = new.next_node

Note that it most likely should be current = current.next_node, not current = new.next_node, since new never gets updated.

answered Apr 11, 2022 at 13:55

luk2302

57.5k24 gold badges108 silver badges151 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Inserting node at specified index in Linked Lists

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related