Inserting and removing into/from sorted list in Python

Question

I have a sorted list of integers, L, and I have a value X that I wish to insert into the list such that L's order is maintained. Similarly, I wish to quickly find and remove the first instance of X.

Questions:

1. How do I use the bisect module to do the first part, if possible?
2. Is L.remove(X) going to be the most efficient way to do the second part? Does Python detect that the list has been sorted and automatically use a logarithmic removal process?

Example code attempts:

i = bisect_left(L, y)

L.pop(i)                 #works
del L[bisect_left(L, i)] #doesn't work if I use this instead of pop

Answer 1

1. You use the bisect.insort() function:

   bisect.insort(L, X)
   

2. L.remove(X) will scan the whole list until it finds X. Use del L[bisect.bisect_left(L, X)] instead (provided that X is indeed in L).

Note that removing from the middle of a list is still going to incur a cost as the elements from that position onwards all have to be shifted left one step. A binary tree might be a better solution if that is going to be a performance bottleneck.

Answer 2

You could use Raymond Hettinger's IndexableSkiplist. It performs 3 operations in O(ln n) time:

• insert value
• remove value
• lookup value by rank

---

import skiplist
import random
random.seed(2013)

N = 10
skip = skiplist.IndexableSkiplist(N)
data = range(N)
random.shuffle(data)
for num in data:
    skip.insert(num)

print(list(skip))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for num in data[:N//2]:
    skip.remove(num)

print(list(skip))
# [0, 3, 4, 6, 9]