removing element from a list in python

Question

Is there any way of removing an element from a list in python in O(1) complexity.i.e., remove(value): this searches linearly through the list and removes right.? So, is there any way to delete an element in O(1) complexity by specifying index or value?

When input list of size 100000 is given to the following code,it is exceeding time limit..,even after using "del".

l=map(int,raw_input("").split(" "))
n=l[0]
k=l[1]
s=map(int,raw_input("").split(" "))
s=sorted(s)
count=0
tree=[]
while len(s)>0:
    poset=[]
    indices=[]
    i=0
    poset.append(s[i])
    indices.append(0)
    j=i+1
    while j<len(s):
       if s[j]==k*s[i]:
           poset.append(s[j])
           indices.append(j)
           i=j
        j+=1
    tmp=0
    for i in indices:
        del s[i-tmp]
        tmp+=1                  
    tree.append(poset)

for i in tree:
    if len(i)%2==0:
        count+=(len(i))/2
    else:
        count+=(len(i)+1)/2
print count

Answer 1

Formally not.

If you know C++ Python lists are implemented more or less as std::vectors of of pointers to objects (in C parlance they are pointers to a contiguous array of pointers). This gives O(1) access to element given the index and allows resizing, however deleting an element from the list requires shifting all subsequent elements down by one element to fill the gap.

Note however that what are moved are just pointers and this is done without needing to fix reference counters and so it's extremely fast (basically just a single memmov call). The time required for the shifting is extremely small unless the list is huge.

So deleting an element from a list in Python if the index is known using del L[index] is formally O(N) but with a tiny constant factor.

It would be possible to implement list objects so that you can get constant time removal from either end by adding a "phase" value to the list object. This would keep access O(1) (with a slightly larger constant) but also allowing del L[0] to be O(1) making it similar to a deque.

This however was considered and not implemented because it would make list access more complex for a normal case and optimize for a special case for which you have a specific structure deque. It would also break compatibility with any C extension module accessing lists.