Data Structures in Python: Circular Linked Lists -- Remove Node

In this video, we investigate how to remove nodes in a circular linked list and code up the function to do so in Python.

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[euwofbw]

Hi Vincent ! thanks for the great tutorial!

3 issues
1, cur=cur.next is inefficient, if key is at tail, the while loop will end up running *twice* before it can exit out. I suggest use break
2, throw error when it's an empty list which can be easily modified by adding a if statement
3, cant remove when there is only one node, someone else in the comment section already pointed it out and gave great solution


thanks again for your work!

[lunghunglin]

def remove(self, key):
if self.head.data == key:
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = self.head.next
self.head = self.head.next
else:
cur = self.head
prev = None
while cur.data != key:
prev = cur
cur = cur.next
prev.next = cur.next
I used a similar method but did a little bit change in the while loop in the else statement. I think it works!
As always, thank you for the tutorial and keep on the great work!!

[mrinmayigavali]

Awesome tutorial as always!


I added one more condition at the end as I was not able to remove the key if the circular linked list contained only one node.
Hope this is right.


if self.head==self.head.next and self.head.data==key:
self.head=None

[prabhanjantrivedi]

Salute to you. You are really awesome.
Just one thing i wanted to point in above code.
If CL is A>B>C>C>D, after removing C, it will result A>B>C>D, but if CL is A>B>C>D>C, after removing C, it will give A>B>D

[ouroboros]

This playlist is amazing, thank you for your amazing work!!

[ian_senior]

i am really learning a lot from all of your data structure playlist videos. i implemented my own version of the remove method. seems to work fine for all the edge cases.

def remove(self, data):
head = node = prev = self.head
while node.next != head:
if node.data == data and node != head: break
prev, node = node, node.next
if self.head.data == data:
self.head = head.next
node.next = self.head
if node.data == data: prev.next = node.next

[iplmaniac]

Great video.Why is there a need for " cur = cur.next" in the last line of the function?The program seems to run without it

[tomio]

Great video and the visual representation in the previous one really helped. I still do have one question; how do we delete the last node in a list? I get that this would be the case if the next-pointer of a node would point to itself, but how do we let the __repr__ or print function know? Is it enough if we set the data of that last node to None?

[shubhamjaiswal]

Hello, @LucidProgramming I have a question regarding the deletion of the node like you wrote
while curr.next != self.head:
prev = curr
curr = curr.next #why did you move the next pointer here
if curr.data is data:
prev.next = curr.next
curr = curr.next
#why not here, like we used to do in earlier videos

please explain I am bit confused.
Thank you

[UPDATE]
* We can write the above program like this also. This also works flawlessly.*
else:
curr = self.head
prev = None
while curr.next != self.head:
nxt = curr.next
if curr.data is data:
prev.next = nxt
prev = curr
curr = nxt

Thank you

[ian_senior]

the github link in the video description points to the split list repo. here is the remove repo if anyone is looking for it.

[Dev-dkez]

For else condition, the more efficient way is to check the key in while loop. This would ensure less iteration unless you want to delete the last node. Let me know if you think otherwise.

[arjunreddy]

Could we just break out of the loop once we have found the key and altered the next position of the previous nose as below...
As it is not required to go through the list again since we aimed at removing a single node..
code:
def remove(self, key):
if self.head.data == key:
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = self.head.next
self.head = self.head.next
else:
prev = None
cur = self.head
while cur.next != self.head:
prev = cur
cur = cur.next

if cur.data == key:
prev.next = cur.next
#cur = cur.next
break

[sutingyang]

Hey, I am the one who asked why self.head = self.head.next is a must. I have made comment under another video, sorry for that!
Could you please explain line 91 for me ?

[ybruce]

Hey so appreciate your detailed tutorial !
I wanna ask if it would be an easy way to write:
else:
cur = self.head
prev = None
While cur.data != key:
prev = cur
cur = cur.next
prev.next = cur.next

[jamesjanes]

does this work if head is the only node and its pointing to itself?