On Sun, May 20, 2018 at 8:35 PM, Daniel Foerster <pydsig...@gmail.com> wrote:
> The third, and probably most convenient based on where you seem to be at > in the curriculum, is to do something like Ian suggested. I think there's a > simpler way to do it with similar performance though I've not benched to > find out; I don't think autoresizing should be too much of a concern, > especially early in a class like this. > > index = 0 > # Could also use a for loop to avoid repeatedly len()ing: > ## for _discarded in range(len(my_list)): > > while index < len(my_list): > if need_to_delete(my_list[index]): > del my_list[index] > # We don't need to update the index after deleting because now the > next > # item is sitting in the current slot > else: > index += 1 > > The `list` type is an array, so the `del` operation is implicitly copying the remaining elements of the list forward. This will be O(n^2) operations over the whole algorithm. My example copies each element at most once, so there are only O(n) operations total. This version may be more clear, though. Ian
