Est-ce une application pour une véritable liste liée en python?

Question

J'ai une longue liste d'états, qui sont traversés dans l'ordre. La traversée d'un état signifie qu'un nouvel état est généré, en remplacement de l'état existant. Après un petit nombre de traversées, je conclus soit un succès d'échec. En cas de succès, ma nouvelle liste est les états modifiés en haut de la liste, et tous les éléments non-traversés sont inchangés. Si je conclus l'échec, je retourne juste la liste originale. Autrement dit, je «défais» en rejetant les changements. Le cas de réussite pourrait être fait en concaténant ma liste de nouveaux états avec une tranche de la liste d'origine. Cependant, les tranches font des copies superficielles si je comprends bien. Il semble que ce soit un coût inutile pour une longue liste. Si j'avais une liste chaînée, je pourrais le faire à très bas prix, je pense. Dois-je l'implémenter en tant que liste liée en python?

EDIT Les itérateurs semblent être une bonne solution Python. Voir ma réponse ci-dessous. Apparemment, cette exigence est un "retroactive data structure"

Answer 1

Si vous prévoyez que seulement quelques éléments seraient traversés, vous pouvez remplacer les nouveaux éléments dans l'ancienne liste une fois que vous connaissez le résultat.

def traverse_states(states): 
    new_list = [] 
    for state in states: 
     new_state, result = traverse(state) # result is in [None, True, False] 
     new_list.append(new_state) 
     if result is not None: 
      if result == True: 
       for index, new_state in enumerate(new_list): 
        states[index] = new_state 
      return 

utilisation:

some_states = create_states() # returns list of states 

traverse_states(some_states) 

some_states est soit la liste originale ou la même liste avec les premiers éléments remplacés.

Answer 2

En supposant que le coût de iter() est bon marché, ce code montre une bonne solution en python, je pense.

import itertools 
from random import randint 

original_iterator = range(0, 99) 
processing_iterator = iter(original_iterator) 
outcome = 'Failure' 

l2 = [] 
for i in processing_iterator: 
    l2.append('a') # change the state 
    random_event = randint(0, 9) 
    if random_event == 1: # success 
     result_list = itertools.chain(l2, processing_iterator) 
     outcome = 'Success' 
     break 
    elif random_event == 2: # failure 
     result_list = original_iterator 
     break 
else: # failure by exhaustion 
    result_list = original_iterator 

print("Result", outcome, (list(result_list)))