Data Structures in Python: Singly Linked Lists -- Node Swap
ฝัง
- เผยแพร่เมื่อ 31 ม.ค. 2025
- In this video, we investigate how to swap two different nodes in a singly linked list.
Slides:
drive.google.c...
The software written in this video is available at:
github.com/vpr...
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:
bit.ly/lp_vim
If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:
bit.ly/lp_subsc...
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 !
Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!
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!
Thank you Samarth, that's quite flattering. I really appreciate the comment, and I do indeed hope to continue making more content on the channel. Thanks for your words of encouragement, and for watching! If you think anyone else can benefit from this content, please, by all means, share it with others :). Thanks again!
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()
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.
Awesome, thank you for the kind suggestions! I appreciate them!
Great job. Explanation of all the topics u taught is so simple and detailed that anybody having a little programming background could understand.
Thank you, that's really great to hear!
@@LucidProgramming keep it up! Wish u all the very best 👍
@@VikashKumar-yg1hm Cheers, thank you, Vikash!
You have a such a way of explaining things, the best on TH-cam I would say, thank you for the great work you keep sharing!!!!
Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing!
I really appreciate the support, and if you want to support the channel, I do have a PayPal link
paypal.me/VincentRusso1
for donations that go directly to the creation of content on this channel.
I hope that the content I provide there will enhance the videos on my TH-cam page.
bit.ly/lp_email
Best tutorials ever I have found in internet.... Excellent Work!
Really appreciate that, thank you very much!
Best data structures video ever. Clear and concise
Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!
Your tutorials are awesome. It found it easy to follow event without CS background. thanks for sharing !
Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!
I found linkedlist implimantation in python in youtube with all operation in your channel only.
keep it up. :)
Thanks for uploading these tutorials, it really helps me a lot!
Hi, 蔡柏裕. Thank you, I'm really happy to hear that these videos have been helpful to you! Cheers, and thanks for watching!
Really blessed to have you. Amazing teaching skills.
Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing!
I really appreciate the support, and if you want to support the channel, I do have a PayPal link
paypal.me/VincentRusso1
for donations that go directly to the creation of content on this channel.
I hope that the content I provide there will enhance the videos on my TH-cam page.
bit.ly/lp_email
@Daniel Kua B does not point to B. I am not sure what you are talking about.
@Daniel Kua Reversing the arrow at 10:44 would not have it point from C to B. It already points from C to B...
@Daniel Kua Daniel. I would appreciate if you stopped commenting your questions under Pratham's comment. He did not make a comment about anything to do with your question and is probably getting bombarded by emails. Please make a separate thread.
@Daniel Kua Daniel. Stop posting under this comment, I already told you this. I am not your servant.
Although it took a bit of time to wrap the head around, it was intriguing and fun going through it Thanks...
Cheers, thanks for watching!
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.
The more problems here you practice, I think the more obvious this type of thing becomes. Keep practicing!
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
Awesome!! Love your explanation.
Thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing!
I really appreciate the support, and if you want to support the channel, I do have a PayPal link (www.paypal.me/VincentRusso1) for donations that go directly to the creation of content on this channel.
I hope that the content I provide there will enhance the videos on my TH-cam page.
bit.ly/lp_email
Thank you so much sir im enjoying yout seiries i hope i can end them all i really love your content
Glad to hear it, and I hope you continue to enjoy them! Cheers, and thanks for watching!
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?
I would encourage you to bring out the data held at the nodes for the example you're talking about to see what is happening.
Excellent video. Thank you :)
Thank you, I greatly appreciate that! :)
love your video
Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!
In one of the slides, the node C is pointing to 2 nodes at the same time, this is not possible as a node can point to only one node. C is pointing to both B and D. please check this and made appropriate changes. Thank you
What time-stamp is this slide on?
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?
Hi Nitesh. Thanks for your kind comment. Regarding your question, certainly in the event where we are just storing integers, it seems like simply swapping the data would be reasonable. However, in the introduction video, recall that I mentioned that any type of data could be stored at these nodes, not just integers.
This data could be complicated data structures, and explicitly copying all of that data everytime we want to swap a node would be cumbersome. If we simply worry about where the node is located in memory and swap with the other node we wish to swap with, we can avoid this issue. Hope that makes sense. Cheers!
LucidProgramming Thanks for guiding ! :)
Thank you very much for the content. I learned a lot from it. I am just wondering for the Node Swap, can u only change the data for each node and not the pointer. Cuz to me it seems like do the same thing.
You can change the data or the pointer. Depends on what your needs are.
@@LucidProgramming Thanks a lot.
@@----5497 Cheers! If you enjoyed and benefited from my content, please consider liking the video and subscribing to the channel for more content like this. If you would like to support the content creation on this channel please consider unblocking ads when watching my videos as this is how I support my time to make content. I hope to be putting out more similar videos soon!
when we are already checking whether curr1 or curr2 exists or not in the loops then why do we check them again (if not curr1 or not curr2)
I would encourage you to print out the steps to the screen to see why.
@@LucidProgramming okay,thanks! lemme try to do that
@@AM-ml7dp Cool, best of luck!
You can define a counter variable and only iterate through once, instead of doing it for each key. something like '' while current and counter < 2: if current.data == key_1 counter += 1 same condition for second key, you make it O(n) worst case instead of O(n2)
Hi Abel. I'm not sure I fully follow what you're doing with your code. While I understand what you're doing with the counter, I'm not 100% sure on what your code is doing. True, you could improve from O(n+n) to O(n), but both evaluate to the same overall complexity with respect to Big-Oh analysis. Thanks for the comment!
Thank you so much! you are awesome
Thank you very much, Akshay, I greatly appreciate that! Cheers, and thank you again for watching!
here is one solution in which handles both cases root node as well as other nodes , no need to write explicitely
def swap(self,k1,k2):
t1 = self.root
t2 = self.root
t3 = 0
while t1.data != k1:
t1 = t1.next
while t2.data != k2:
t2 = t2.next
t3 = t1.data
t1.data = t2.data
t2.data = t3
Hope u will like this
Cool, thanks for sharing!
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?
Have you tried this before asking?
I am not sure about the curr_1.next, curr_2.next = curr_2.next, curr_1.next. In the example, the curr_1.next is actually point to curr_2 itself, and this code will make curr_2.next point to curr_2 itself, doesn't it? Thanks in advance.
Not sure I understand the question
In the last step for llist.swap_nodes('B', 'C'),
temp = curr_1.next ( B points to C )
curr_1.next = curr_2.next ( after this equation: B points to D, instead of C )
curr_2.next = temp ( C points to (B points to C) ). This is just C points to C.
I thought it would be
curr_1.next , curr2.next = curr2.next , curr_1 (B points to D and C points to B)
But its not working in the program. Where is the mistake in the logic above? Thanks
Hi Anoubhav. I'm having a hard time understanding what you're asking. The first portion of code is equivalent to the second. That is, the Python code using the following shorthand:
A, B = B, A
is equivalent to:
tmp = A
A = B
B = tmp
It seems like you think the statements produce different results, but I don't think that is the case. I might be misunderstanding what you're asking as well.
curr_1.next , curr2.next = curr2.next , curr_1 ????
I think That would be curr_1.next , curr2.next = curr2.next , curr_1.next
@@LucidProgramming The 1st portion is equivalent to "curr_1.next, curr_2.next = curr_2.next, curr_1.next" and not same as the 2nd portion which is "curr_1.next, curr_2.next = curr_2.next, curr_1" (it's not swapping, but overriding curr_2.next with curr_1). Actually I am also confused and have the same question as Anoubhav. Thanks!
i had the exact same thought. curr_1.next == "C" so why would you then tell "C" to point to itself by curr_2.next = curr_1.next when you want "C" to point to "B" and "B" is curr_1, so i can see the logic of curr_2.next = curr_1 in order to have "C" point to "B" and not point to itself. however, what happened was that earlier in the code the "B" next attribute was reassigned to point to itself with the code prev_2.next = curr_1 since prev_2 == "B" node and curr_1 == "B" node, therefore "B" now points to itself until the swap and that is why the swap works since it is then pointing "B" to "C" and "C" to "B". here is the code with the current values in [ ] for clarity. curr_1.next, curr_2.next = curr_2.next ["D"], curr_1.next["B"] (since it was reassigned with prev_2.next = curr_1 earlier in the code).
Excellent teaching from where can I access the slides
Updated the description with a link to the slides,.
And thank you! If you like my content, I've been working on some projects during the past couple of months. If you would like to stay up-to-date, please consider subscribing to my mail list. Also, if you haven't already, please consider subscribing!
I really appreciate the support, and if you want to support the channel, I do have a PayPal link
paypal.me/VincentRusso1
for donations that go directly to the creation of content on this channel.
I hope that the content I provide there will enhance the videos on my TH-cam page.
bit.ly/lp_email
@@LucidProgrammingcan you share the slides to prepare
@@roopkummar3858 Yeah, I did. Link in description.
I was trying this on my own not, trying my own approach -
Can you please tell me how this code is just losing the key nodes that I am passing?
def node_swap(self, n1, n2):
curr_node = self.head
while curr_node:
if curr_node.data == n1:
n1_node = curr_node
if curr_node.data == n2:
n2_node = curr_node
curr_node = curr_node.next
n1_node.next, n2_node.next = n2_node.next, n1_node.next
ll.node_swap("A", "C")
Somehow after printing the Linked List, A and C are lost. Any help is appreciated!
I'd recommend printing out at different steps to see why this might be happening.
@@LucidProgramming Thank you for your suggestion! I was not taking into consideration the previous nodes, duh!
Here is the updated code which works if none of the keys are head nodes -
-
while curr_node:
if curr_node.data == n1:
n1_prev_node = prev_node
n1_node = curr_node
elif curr_node.data == n2:
n2_prev_node = prev_node
n2_node = curr_node
prev_node = curr_node
curr_node = curr_node.next
n1_prev_node.next = n2_node
n2_prev_node.next = n1_node
n1_node.next, n2_node.next = n2_node.next, n1_node.next
@@Mithileshx Cool, glad you figured it out!
Why can't we just swap the node values? It would reduce the hassles of updating 'next' pointer and could achieve swap in o(n) time complexity.
I just have a quick question if you don’t mind......so “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!
Not sure I understand the confusion.
"so “prev_2.next = curr_1” but if I track the nodes it looks like prev 2 is curr 1."
Your initial statement confirms the latter.
LucidProgramming so let’s say we switch B and C like the example you used. Prev1 will be A, prev 2 and curr 1 will be B and curr2 will be C. So my setting prev2.next = curr1 are we not setting B.next equal to itself? Sorry if my question is stupid. I’m just slightly confused
Ahhhh I get it!
@@rayj1232 Great :)
@@rayj1232 can you please help me I'm also confused...why we are pointing B to itself. Please help...!
I have managed to create below program for swap node and this works too . But i think i am missing something ( pointers ) here . Please suggest me if we are good with below program or we do need to update pointers as well.
def swap_node(self,node1,node2):
firstnode = self.head
prev1 = None
while firstnode.data != node1:
prev1 = firstnode
firstnode = firstnode.next
secnode = self.head
prev2 = None
while secnode.data != node2:
prev2 = secnode
secnode = secnode.next
if not firstnode or not secnode:
return
firstnode.data, secnode.data = secnode.data, firstnode.data
But you're not swapping the nodes. You're swapping the values of the data contained at those nodes.
@@LucidProgramming Yes lucid . That's correct. Let me follow the steps written by you. Thank you for replying . You are the best teacher as always ❤️
@@muraliperi7669 Cheers!
Awesome video..Please add videos for sorting
Hey Rohan. Thanks for the kind comment :). I do have one video on sorting. It's a playlist I intend to add more videos to. Thanks for the suggestion, and I'm looking forward to making more videos on the topic of sorting!
th-cam.com/video/vNm2nvDyyls/w-d-xo.html
Can you include hash table contents too in your videos
Hash table contents?
@@LucidProgramming" Data structures hash table concept"
@@aravindhang1264 Still not following what you're asking here.
Can we just swap the data in the nodes?
No. Because then you would just be swapping the data and not the nodes.
@@LucidProgramming Yes thank you
@@darshmehta3476 Sure, no problem.
Which data structure is good linked list or hash map
Depends on what you're trying to do.
i got confused in line 11: while curr_2 and curr_2.data!=key_2: please explain why you write curr_2.data!=key_2
Are you sure it's line 11? Can you timestamp the video so I know where you are referring to?
this is labeled as the first video in the playlist - but then why is he say its a continuation. if its not the first video, then what is
@LucidProgramming
I am okay with this code but this is the ideal case, ideal case means that there should not be repetition of the data.
So my question is that if the data is repeated then ?
My same question goes with the deletion also.
How the linked list will pick data.
Example let there be a linked list (1,2,3,4,5,6,5,2,8,7,5)
If I want to delete the 7th data of the linked list then how will it be done?How will it know that I am referring to the data(5, the 7th character) which has occured 3 times in the linked list.
Please clear my doubt
Thank you
Hi Shubham. Indeed this only works with unique data elements. If you wanted to account for duplicates, you could do something like add an extra field for each node that has a unique identifier. Then you could simply search for those identifiers in the list. Hope that makes sense, and thanks for your question!
@@LucidProgramming Yeah! That's what I thought.
The time we append the data to the linked list at that time we can put some identification on each node. And this is the point where linked list gets failed in comparison to arrays.
Thanks for your response.
@@shubhamjaiswal2322 No problem, hope that helped! Cheers, and thanks again for your comment.
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!)
Those two lines set different variables equal to different values.
LucidProgramming Thank you!!
what we have to do if swap node is lastNode
Hey
Can't you just swap the data fields when you have access to the specific nodes?
Hi Roopam. What do you mean by "just swap the data fields"? In what way and using what syntax?
@@LucidProgramming I meant save the pointers to those specific nodes in temporary variables and then interchange their data fields. I googled it some more, found out that exchanging the data values is a costly operation. 🤔
@@roopamrajvanshi4724 Ah, okay. Yeah, from an efficiency standpoint, that might not be the best way to go. Thanks for the clarification and happy coding!
@@LucidProgramming def node_swap(self,key_1,key_2):
if key_1 == key_2:
return
prev_1 = None
curr_1 = self.head
while curr_1 and curr_1.data != key_1:
#prev = curr_1
curr_1= curr_1.next
prev_2 = None
curr_2 = self.head
while curr_2 and curr_2.data != key_2:
# prev = curr_2
curr_2= curr_2.next
if not curr_1 or not curr_2:
return
temp = curr_1.data
curr_1.data = curr_2.data
curr_2.data = temp
if prev_2:
prev_2.next = curr1
Isn't prev2 and curr1 both equal to B in the case of swap("B", "C")?
Hi Rahul. Hmm, I'm not sure I know precisely what you mean. For instance, are you using the variable names "prev_2" and "curr1" to denote something specific? I just want to make sure I understand your question before answering. Thanks!
Hey, so I just took your example of list A->B->C->D. In this case the prev2 value would be B and curr1 value would also be B when we call swap("B", "C").
Ah, I see what you mean. Yes, indeed the value of those two variables at the end of the two while loops will have the value of "B". Indeed, if you were to apply the swap function on "A" and "B" (instead of "B" and "C"), then the value of both of those nodes would have the value of "A". However, this works out okay, since you'll notice that the remaining portion of the code handles for this, and the resulting linked list that is returned has the nodes properly swapped. Does this make sense?
yes,i had the same question.but it works out.although the rest of linked list D->...are not connected anymore
would it be valid?
temp=curr_1 or temp=prev_1.next
prev_1.next=curr_2
curr_2.next=temp2
curr_2.next=temp
temp.next=temp
which should be a->c->b->d??
How can I create a linked list first?
Check the first video in the linked lists playlist:
th-cam.com/video/FSsriWQ0qYE/w-d-xo.html
can't I just do the following code:
def swap_node(self, key_1, key_2):
cur = self.head
prev = None
while cur:
if cur.data == key_1:
cur.data = key_2
elif cur.data == key_2:
cur.data = key_1
prev = cur
cur = cur.next
Swapping data instead of the whole node itself.
Not if that's not what the specifications were. Think of a setting where you have massive data and swapping that vs. swapping that node would incur huge time disadvantages.
this man never spend a day in his life as a developer...so much repetitive code
I am trying to understand the logic
so instead of the slides I am trying to get this here
Linked list:
A -----> B -----> C ------> D ------> E ------>
Let's say we are swapping B and D
Step1:
in order to swap you need to connect the previous node's pointer(A.next) to node 2(Node D)
Step2:
find the previous node's pointer(C.next) for the 2nd element(node D)
and connect it to Node1(Node B)
Step 3:
B's next is pointing to C and D's next is pointing to E
when you swap:
B's next would point to what D's next was pointing to i.e E
and D's next would point to B's next i.e C
This the final linked list will change to
A ----> D ----> C ----> B ----> E ----->
Yep, that's the right idea.
NEED HELP FROM SMART PEOPLE !
I made a function to empty an array, can you see why its works only this way and not the other
def deletelist(self):
self.head = None # WORKS ,empties the list
def deletelist(self):
cur_node = self.head
cur_node = None # Does NOT WORK, does NOT do anything to the list.
# I thought cur_node is bound to self.head
#. I tried putting cur_@t = None. , then the remaining list is cleared.(except the head)
Q. what is the meaning of this cur_node = self.head (in first line of the function)?
You're setting a variable equal to the head of the linked list.
"unpause" the video.
Sorry? Not sure I understand.
@@LucidProgramming nothing😂 you said, unpause instead of play. Great tutorial brr
@@shubhamh7451 Ah, gotcha. Cheers!