Iterate through Linked List

Hello, I get stuck at task 16. I have learnt LinkedList in C++ before and I can not use for loop to iterate through LinkedList but with Python, I can.
Is that a feature of Python or what?
Thanks

https://www.codecademy.com/paths/computer-science/tracks/complex-data-structures/modules/cspath-hash-maps/projects/blossom

There’s no reason you can’t iterate through a LinkedList using a common loop. For the purposes of this discussion (and I believe the lesson, though I don’t have access to it), we’ll consider a singly LinkedList rather than a doubly LinkedList for the sake of simplicity.

Defining a LinkedList

You already have a basic idea of what a LinkedList is, and how it works, but I’ll reiterate for clarity:

According to this GeeksForGeeks article

a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list

With this in mind, let’s talk about how to actually iterate through one.

How do I iterate through a LinkedList?

If you always know the next Node (including when it is of value None; nonexistent), it’s simple work to linearly traverse the LinkedList starting from any Node in the sequence by following simple steps in a loop:

  1. Do something to the content of the current Node (let’s say output [print()`] for now)
  2. Check the value of the next Node against the value of None: Does the value exist?
  3. If so, set the current Node equal to the next Node. If not, break from the loop.

So, in “paragraph form”… We want to start on any given Node in our LinkedList, and continue moving from the current Node to the next until the next Node is None (nonexistent). At each stop (Node), we’ll do something to that Node (in this example case, printing out its associated data).

Which type of loop do I use?

We want to continue through our LinkedList until a certain condition is met. If we take another look at the steps in the previous section, we are doing something first, then we are checking a condition (in the example case, does the next Node exist), and if the condition evaluates to True, we are continuing to the next Node.

From a C++ perspective, it makes a lot of sense to use the do{} while() loop. Unfortunately, in Python, there’s no such thing. You can try to emulate one with a while loop, or you can try to modify your logic to fit the standard while() format (I haven’t actually implemented this one, so don’t assume it’ll work). I won’t claim to have worked out the difference in program efficiency between the two, so I’ll leave it to better equipped members to tell you how they rank comparatively.

As a quick aside… In our example, we discuss moving from a defined start Node to the end of the list (an undefined end Node). You could just as easily implement a function or loop that iterates through a linked list from a defined start Node to a defined stop Node. Or, assuming you’ve implemented a LinkedList with a head Node, from an undefined start (assumed to be the head) to a defined end.

You mentioned a for loop version in your initial message, but I haven’t been able to find a way to use one to iterate through a LinkedList in Python. There appears to be a Java builtin that allows iteration using an enhanced for loop (similar functionally to how you might loop through a list in Python: for val in list), but that’s the closest I got. Certainly a custom-built LinkedList class wouldn’t have this functionality by default (unless you specifically implemented it).

How about the implementation?

Here’s an example implementation for a loop that, starting on a given Node will iterate through each Node following it until the final Node, and will print out the data inside each one as it passes:

#Current Node is defined as cur, value starts as defined Node
#with instance variable of data (data in current Node)
#with instance variable of next (next Node)
while(True):
  print(cur.data) #print the data
  if(cur.next is None): #this is our do-while loop emulation, checking if this is the last Node
    break
  cur = cur.next #update cur so we move on in the next iteration

TL; DR

Iterating through a LinkedList doesn’t appear to be built into Python (though I’m happy to be wrong about that if other users have additional perspectives), but it is implementable.

Hope this helps.

1 Like

Yes, I only know to iterate through LinkedList by the way you recommended. But can you watch this video and show me if I misunderstand that at task 16 he used for loop to iterate through LinkedList or what?
I think that list_at_array he defined is a LinkedList. Is that right?

1 Like

I think there’s an omission in this discussion. In the imported linked list file in the video, that linked list has an __iter__ defined (this allows to describe what happens upon iteration of the object). This allows for the iteration to happen. Feel free to correct if I’m wrong it’s been a while since I looked at this one.

Try commenting it out and running the file you’ll see the for loop won’t work.

1 Like

This is what I was missing pre-very-long-response (lol), thanks @toastedpitabread!

1 Like

For me, it’s the long meanderings into nowhere that the best stuff is learned.

1 Like

Thank you i got it guys :smiley: