[FIXED] Infinite Loop when Iterating through a Linked List Python 3

Issue

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}}}}}

Solution

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.

Answered By - Nir Alfasi