KnowledgeHub
Questions
Tags
Users
Search
Alex Rivera
|
Logout
Edit Question
Title
Body
I was writing a python function that looked something like this def foo(some_list): for i in range(0, len(some_list)): bar(some_list[i], i) so that it was called with x = [0, 1, 2, 3, ... ] foo(x) I had assumed that index access of lists was O(1) , but was surprised to find that for large lists this was significantly slower than I expected. My question, then, is how are python lists are implemented, and what is the runtime complexity of the following Indexing: list[x] Popping from the end: list.pop() Popping from the beginning: list.pop(0) Extending the list: list.append(x) For extra credit, splicing or arbitrary pops.
Tags (comma-separated)
Save Edits
Cancel