CODEWITHSUNDEEP
python-3.xwhile-looplinked-list
DrJessop
DrJessop

Reputation: 472

Infinite Loop when Iterating through a Linked List Python 3

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

Upvotes: 1

Views: 652

Answers (3)

Manuel Denegri Willms
Manuel Denegri Willms

Reputation: 21

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:

  1. 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.
  2. 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.
  3. 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:
  4. 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

Upvotes: 0

DrJessop
DrJessop

Reputation: 472

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.

Upvotes: 0

Nir Alfasi
Nir Alfasi

Reputation: 53535

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.

Upvotes: 1

Related Questions