CODEWITHSUNDEEP
python
rafalio
rafalio

Reputation: 3946

How does Python's bisect work?

I've read that Python's lists are implemented using pointers. I then see this module http://docs.python.org/2/library/bisect.html which does efficient insertion into a sorted list. How does it do that efficiently? If the list is implemented using pointers and not via contiguous array, then how can it be efficiently searched for the insertion point? And if the list is backed via a contiguous array, then there would have to be element shifting when inserting an element. So how this bisect work efficiently?

Upvotes: 2

Views: 1058

Answers (2)

dstromberg
dstromberg

Reputation: 7177

I believe the elements of a list are pointed at, but the "list" is really a contiguous array (in C). They're called lists, but they're not linked lists.

Actually, finding an element in a sorted list is pretty good - it's O(logn). But inserting is not that good - it's O(n).

If you need a logn datastructure, it'd be better to use a treap or red-black tree.

Upvotes: 2

Thijs van Dien
Thijs van Dien

Reputation: 6616

It's the searching that's efficient, not the actual insertion. The fast searching makes the whole operation "adding a value and keeping all values in order" fast compared to, for example, appending and then sorting again: O(n) rather than O(n log n).

Upvotes: 1

Related Questions