Data Structures in Python: Singly Linked Lists -- Node Swap

In this video, we investigate how to swap two different nodes in a singly linked list.

Slides:

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:

[pythonenthusiast]

i dont know if you realize but yours is the most underrated and best explanation of whatever you teach .. please post more often . WE NEED YOU !

[samarthbhandari]

How does this channel have just 6k subscribers?! Excellent content in all the videos, I hope you keep adding on to them very helpful in clearing concepts. Thank you!

[lazykitten]

Thank you so much for creating these data structure videos. I finally understand how to create python class and how to code linked list. Another idea for swapping two nodes is to create two empty linkedlist in the function and point those linkedlists to the nodes that to be swapped. And then just swap the data. This way we do not need to keep track of where the .next part goes and we only need to iterate through the original linkedlist once. The code looks like this: def ll_swap(self, data1, data2):
if data1==data2:
print('the two values are the same. Nothing to swap')
return
if self.ll_length() is None or self.ll_length()<2:
print('not enough nodes to swap')
return
ll1=LinkedList()
ll2=LinkedList()
curr_node=self.head
while curr_node:
if curr_node.data==data1:
ll1.head=curr_node
if curr_node.data==data2:
ll2.head=curr_node
curr_node=curr_node.next
if ll1.head and ll2.head: #swap the data of the two nodes that are marked by ll1.head and ll2.head
ll1.head.data, ll2.head.data=ll2.head.data, ll1.head.data
return
print('the data to be swaped is not in the linked list')
return

[Sam-nens]

Thanks for the explanation. I would suggest (1) clarifying that the nodes to be swapped are cur_1 and cur_2, and (2) change the scheme to reflect that cur_1 and cur_2 need not be contiguous, (3) clarifying that since we're tracking two keys, we need to define two loops to traverse the list for the corresponding node, and also track their previous nodes. Other than that, your series is excellent.

[sivakarsiva]

You have a such a way of explaining things, the best on Youtube I would say, thank you for the great work you keep sharing!!!!

[VikashKumar-yghm]

Great job. Explanation of all the topics u taught is so simple and detailed that anybody having a little programming background could understand.

[joycejeyaratnam]

Hi there, sorry to ask a lot of questions. I'm pretty confused at the end of the video.

You set prev_1.next to curr_2 (A->C) and then prev_2.next to curr_1 (B->B). Shouldn't that be: prev_1.next = curr_2(A->C), then prev_2.next = curr_2.next(B->D) and finally, curr_2.next = curr_1 (C->B). So that it works out to A->C->B->D?

I know that your code works, but I'm failing to understand why! Please help me: I know that linked lists have a data field and a next field. So the next should be the memory location.
In your code, you set prev_1.next = curr_2. But If prev_1 = B and curr_2 = (also!) B, aren't you simply making B point to itself?

[davidkanjuru]

Best data structures video ever. Clear and concise

[krishnannavadia]

Best tutorials ever I have found in internet.... Excellent Work!

[sherryx]

Your tutorials are awesome. It found it easy to follow event without CS background. thanks for sharing !

[arjunreddy]

Although it took a bit of time to wrap the head around, it was intriguing and fun going through it Thanks...

[chuckchen]

This swapping of pointers is brilliant, although really hard to get to at the first thought. prev pointers can be swapped in a similar style too.

[IntrestingRandomFacts]

from your example of list A->B->C->D. prev2 value will be B and cur1 value will also be B when we call swap("B", "C"). Its like B will point to B.
Also cur1.next, cur2.next = cur2.next, cur1.next in this cur2.next=cur1.next will be pointing to C only
B->C, C->D = C->D, B->C

[janakkapuriya]

I found linkedlist implimantation in python in youtube with all operation in your channel only.
keep it up. :)

[EricTsai-pt]

Thanks for uploading these tutorials, it really helps me a lot!

[prathamgupta]

Really blessed to have you. Amazing teaching skills.

[abhinavyel]

Would it work for swapping A and D since we are doing prev2.next = curr1 so if there is a node in between curr1 and prev2 this wouldn't work?

[rayj]

I just have a quick question if you don’t “prev_2.next = curr_1” but if I track the nodes it looks like prev 2 is curr 1. The program works correctly but I feel like I’m missing something. Any help would be appreciated!

[niteshrawat]

Hi lucid, amazing video. Just curious to ask if we just swap the data inside the nodes, that way we do need all this hassle. Please advise what will wrong in it?

[lunghunglin]

Dear teacher,
In the last code, why can't I write: curr_2.next = curr_1.next curr_1.next = curr_2.next?
What's the difference?
Thanks a lot!
( Once again, thank you for the tutorial!)