CODEWITHSUNDEEP
pythonlinked-list
garfieldluva
garfieldluva

Reputation: 1

Deleting a Node from a Linked List is not working

My code below for deleting a node in a linked list is not working, as in it is deleting the wrong index of the index I want to delete instead. 

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

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

    def Addnode(self,data):
        new_node=Node(data)
        if self.head==None:
            self.head=new_node
        if self.tail!=None:
            self.tail.next=new_node
        self.tail=new_node

    def removenode(self,index):
        new_n=self.head
        count=0
        while count!=index:
            new_n=new_n.next
            count+=1
        new_n.next=new_n.next.next
    def Printlist(self):
        node=self.head
        while node!=None:
            print(node.data)
            node=node.next

List=LinkedList()
List.Addnode(1)
List.Addnode(2)
List.Addnode(3)
List.Addnode(4)
List.removenode(1)
List.Printlist()

So this should remove the Node that is at index 1, which is 2, but instead it removes 3, and prints 1,2,4 and not even 5 either? I am confused as why this is happening?

Upvotes: 0

Views: 84

Answers (1)

TemperedFate
TemperedFate

Reputation: 56

You are going too far in your removal function. Let's walk through it, removing the first node (as in your code).

new_n=self.head

new_n now points to the head node. This is what we want, so it is correct. 

count=0

Initializes the count to zero. This is also correct, since the current node is node zero.

while count!=index:
    new_n=new_n.next
    count+=1

This is where we get the unexpected behavior. On the first iteration (since 0 != 1), we enter the loop. Now new_n points to the second element in the list (index 1), and count is 1.

Now we try the loop condition again. count is now equal to index so we break out of the loop.

The current new_n is now pointing to the second element in the list (index 1), so new_n.next=new_n.next.next changes the next element to be the element following its current next. This is the way to remove an element from a linked list, however we are off by one element (we traversed the list too far). In order to fix this, try the following code:

def removenode(self,index):
   # catch the edge condition where we're removing the first node
   if index==0 
        self.head = self.head.next 
   else
      new_n=self.head
      count=1
      while count!=index:
           new_n=new_n.next
          count+=1
      new_n.next=new_n.next.next

Disclaimer: I don't have Python on this computer, so I'm unable to test the code, but hopefully breaking it down this way helps.

Upvotes: 2

Related Questions