Is this an application for a genuine linked list in python?

Question

I have a long list of states, which are traversed in order. Traversing a state means a new state is generated, as a replacement for the existing state. After a small number of traversals, I conclude either success of failure. If success, then my new list is the modified states at the top of the list, and all the un-traversed elements unchanged. If I conclude failure, I just return the original list. That is, I 'undo' by throwing away the changes.

The success case could be done by concatenating my list of new states with a slice of the original list. However, slices do shallow copies if I understand correctly. It seems this is an unnecessary cost for a long list. If I had a linked list, I could do this at very low cost, I think.

Should I implement this as a linked list in python? [because if the list needs to be modified, the elements at the head of the list can simply be added to the unmodified tail by changing a pointer, no O(N) copying of the list, which is unavoidable with Python lists]

EDIT Iterators seem to be a good Python solution. See my answer below. Apparently, this requirement is a 'retroactive data structure'

@donkopotamus, Oh, I thought it was: https://stackoverflow.com/a/19068714/4834 — quamrana, Aug 14 '17 at 09:49
@quamrana A list slice might be a "shallow copy" of the list, but the items in it are not "shallow copies" of the items in the original list, which would seem to be the OP's worry (otherwise there's no reason they would think creating a new linked list would possibly be cheaper) — donkopotamus, Aug 14 '17 at 09:50
Oh, I thought the concern of the OP was that producing a slice eg. `oldlist[n:]` where `len(oldlist) >> n` would be expensive. — quamrana, Aug 14 '17 at 09:52
@donkopotamus slicing is an idiom for shallow copy. Quamrana is correct: the cost is O(n), much, much worse than a linked list. — Tim Richardson, Aug 14 '17 at 11:05

score 1 · Answer 1 · answered Aug 14 '17 at 10:00

1

If you expect that only a few items would be traversed, then you could overwrite the new items onto the old list once you know the outcome.

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

usage:

some_states = create_states() # returns list of states

traverse_states(some_states)

some_states is either the original list or the same list with the first few items replaced.

answered Aug 14 '17 at 10:00

quamrana

37,849
12
53
71

I know I could do this:) it's ugly though; it means reiterating. Highest bidder is still a linked list... – Tim Richardson Aug 14 '17 at 11:03
You can easily write code for a linked list and you will attain the performance you require when returning the list (new or old). You will also have to consider code maintenance costs when using a 'list' which is not a builtin type. – quamrana Aug 14 '17 at 11:15
When you read stack overflow on this topic, it's easy to find claims that there are few circumstances when a linked list would be a better choice than a list. But it seems not so hard to find an example afterall. – Tim Richardson Aug 14 '17 at 11:18
But somehow I wonder if there is an iterator solution, chaining an iterator for the new head with the remaining iterator of the original list – Tim Richardson Aug 14 '17 at 11:24
As an aside, the ChainMap data structure is also very helpful: it seems like a fast way to layer changes to dict without changing the original dict. – Tim Richardson Sep 14 '17 at 01:11

Tim Richardson · Answer 2 · 2017-08-14T12:26:35.767

Assuming the cost of iter() is cheap, this code shows a good solution in python, I think.

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

Is this an application for a genuine linked list in python?

2 Answers2