Infinite Loop when Iterating through a Linked List Python 3

Question

I am trying to write a function that removes all pdf files from a linked list, however after running this, I quickly realized that it became an infinite loop. My first while loop is supposed to catch all pdf files at the beginning of the linked list. My second while loop is supposed to iterate through the linked list as many times as it takes to get rid of the pdf files. I guess my logic for while not loops is incorrect.

def remove_all(lst):
    ptr = lst
    while ptr['data'][0] == 'pdf':
        ptr = ptr['next']
        lst = ptr
    all_removed = True
    while not all_removed:
        all_removed = False
        while ptr['next'] != None:
            if ptr['next']['data'][0] == 'pdf':
                ptr['next'] = ptr['next']['next']
                all_removed = True
            ptr = ptr['next']
    return lst

I am getting the error that none type is not subscriptable for the the second while loop, which confuses me since it is supposed to stop when ptr['next'] is None.

My linked list looks like this:

{'data': ['pdf', 2, 4], 'next': {'data': ['csv', 1, 1], 'next': {'data': ['pdf', 234, 53], 'next': 
{'data': ['xml', 1, 2], 'next': {'data': ['pdf', 0, 1], 'next': None}}}}}

You never advance ptr in your second loop. I also do not get that while not all_removed loop. Also, what is supposed to be return value of that function? Also also, how do you handle cases where the first element should be removed? You just replace your lst reference but this will not update the caller’s lst instance. — poke
– poke, Commented Aug 13, 2017 at 18:21
Now that I returned the lst, if you completely ignore the second loop, the return value is not returning the caller's lst, but the new instance of lst. — DrJessop
– DrJessop, Commented Aug 13, 2017 at 18:52
@ poke What I'm trying to do with the while not loop is if the loop encounters a pdf, at the end of it's iteration, it should iterate again just to make sure it didn't miss any pdf's. This is because ptr['next']=ptr['next']['next'] might make ptr['next'] a pdf file if there were two adjacent pdf files. — DrJessop
– DrJessop, Commented Aug 13, 2017 at 18:54

Nir Alfasi · Accepted Answer · 2017-08-13 18:24:46Z

1

First, try:

ptr['next'] = ptr['next']['next']

instead of:

ptr['next'] == ptr['next']['next']

Second, since we have a 'next': {'data': ['xml', 1, 2] in your structure (with xml and csv - not pdf), the execution goes into the nested while loop:

while ptr['next'] != None:

and since the if condition if ptr['next']['data'][0] == 'pdf': evaluates to False it gets stuck in the loop infinitely.

edited Aug 13, 2017 at 18:24

answered Aug 13, 2017 at 18:19

Nir Alfasi

53.6k12 gold badges94 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

DrJessop Over a year ago

I just made some edits, and now I'm getting the error that none type is not subscriptable for while ptr['next'] != None. Why is this, given that I stop iterating through the loop when ptr['next'] = None.

DrJessop Over a year ago

Also, how would I make it so that the first loop starts over through the entire linked list when not_all_removed = False?

Nir Alfasi Over a year ago

@DrJessop when not_all_removed == False the loop condition evaluates to True and will run again. ptr already points to the beginning of the list.

DrJessop Over a year ago

I just changed the variable name cause it makes more sense. Also, I don't understand why the loop runs infinitely since I set all_removed to False inside my first loop, so if it doesn't encounter any more pdf files, I thought that the loop would terminate?

Nir Alfasi Over a year ago

If you want to stop looping (even though there are more items) then after setting 'all removed' to true, simply break

DrJessop · Accepted Answer · 2017-08-13 19:28:12Z

0

Given that I do not fully understand while not, while true loops, I resorted to recursion to answer my question.

def remove(lst):
    ptr=lst
    while ptr['data'][0]=='pdf':
        ptr=ptr['next']
        lst=ptr
    while ptr['next']!=None:
        if ptr['next']['data'][0]=='pdf':
            ptr['next']=ptr['next']['next']
            return remove(lst)
        ptr=ptr['next']
    return lst

If there are any pdf's at the start of the list, they are removed, and then if there are any pdf's encountered later, they are removed and the function returns itself just in case there are adjacent pdf's.

answered Aug 13, 2017 at 19:28

DrJessop

4726 silver badges26 bronze badges

Comments

Manuel Denegri Willms · Accepted Answer · 2023-12-01 03:59:48Z

6 years later, but you got me interested. Here I present a solution to simplify complexity and a linked-list generator for testing purposes. But I don't adress the infinity loop, as I'm focusing on the first while loop of DrJessop:

The way I see it, the first while loop only "erases" consecutive pdfs at the start. But I see more potential for it as the condition is cristal clear:

Following up you find some changes:

Introducing a new condition to the while loop tu run till the last node, namely lst['next'] != None. Mind that the loop only stops, if the last node is linked to a None type and the loop misses the last node.
The condition ['data'][0] == 'pdf' got moved into the while loop as an if condition. This allows to ignore all pdfs not just the ones at the start.
Initialized a final linked-list final_ll and a temporary linked-list temp_ll as dictionaries, to store the relevant documents alog the iterations. These are used in the else-case:
At the end I'm adding the final node.

def remove_all(lst):
    # initiating final ll and temporary LL for single nodes to be stored
    final_ll = {}
    temp_ll = final_ll # a link for temp_ll to store final results in final_ll
    
    while lst['next'] != None: # running through all but the last node
        
        if lst['data'][0] == 'pdf':  # ignoring all pdfs
            lst = lst['next']        # jump to next node
         
        else:                           # including desired nodes   
            temp_ll['data'] = lst['data'] # add node data
            temp_ll['next'] = {}          # add node link    
            temp_ll = temp_ll['next']     # update temp_ll
            lst = lst['next']             # jump to next node
    
    # catching the last node
    temp_ll['data'] = lst['data']
    temp_ll['next'] = None
    return final_ll

For testing purposes here is an random generator of linked lists containig documents and in the format you displayed:

from random import randint as r_
documents = ['pdf', 'xml', 'csv', 'json', 'html']

def prod_doc_ll_list(size = 3):
    ll_docs = {}
    ll_doc = ll_docs
    for i in range(size):
        ll_doc['data'] = [documents[r_(0,4)], r_(0,250), r_(0,250)]
        if i < size-1:
            ll_doc['next'] = {}
            ll_doc = ll_doc['next']
        else:
            ll_doc['next'] = None
    return ll_docs
        
docs = prod_doc_ll_list(8)
docs

Collectives™ on Stack Overflow

Infinite Loop when Iterating through a Linked List Python 3

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related