I'm writing a program in Python. The algorithm that I use is very slow (and it can't be faster for what I want to do) so how quickly the program will execute is important (in other words: computational complexity matters) and this is what I need to do:
- I have a list.
- I need to iterate the list and do some operation on every element.
- When iterating the list, I need to remove some elements from the list.
This can be done very easily, but the problem is that I want removing element to have computational complexity O(1), not O(n), so that the entire process of iterating the list and removing some elements has computational complexity O(n). Now, I don't know what the internal implementation of python lists is, but I'm almost sure that when I remove element like that:
del list[5]
or like that:
list.pop(5)
It will probably have to move all of the elements after fifth element one position back which results in computational complexity O(n).
If it was C++, then I would use list that is implemented using pointers, so that I could go through the entire list and remove the elements that I want to remove in the most quickest way. But in Python, there are no pointers, so I can't implement this list on my own. So is there a way to do the above process in Python with computational complexity O(n)?
In other words:
In C++, there are two ways how you can implement a list: using pointers and using an array. The first implementation is faster for some operations, and the second is faster for other operations. I need to use the first implementation, but I don't know if it's possible in Python.
