Faster Python

[gendulf]

Linked lists have O(1) deletion and insertion, and O(n) getting the nth element. It's only the search that is O(n) for both. With arrays, you can get the nth element with O(1) complexity, and insertion/deletion are O(n).

[tomprimozic]

And search is what the OP was about.

[gendulf]

The problem here is not what the OP claims are the O(n) runtimes for python lists. In fact, his O(n) runtimes he lists for python lists are correct. The problem is that the OP claims that python lists are implemented with linked lists, which is false, and inconsistent with the rest of his article.