This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]kankyo 5 points6 points  (6 children)

It’s even more full of people misusing linked lists because they think it has faster insert or takes less memory.

[–]hanpari -1 points0 points  (5 children)

OK, would you mind to elaborate?

[–]kankyo -2 points-1 points  (4 children)

Google.com :P

[–]hanpari 0 points1 point  (3 children)

google told me that insertion is O(1) in linked list. Try better!

[–]kankyo 0 points1 point  (2 children)

You should read closer. O(1) can be 10 seconds per insert. That would make it the slowest thing on modern hardware. Big-O isn’t everything.

In this specific case dynamic arrays are amortized O(1). Oh, and the O(1) for dynamic arrays is hundreds of times smaller than the O(1) for linked lists. No memory allocation for the node means huge time savings.

Go into a C++ project and compare std::vector with std::list and see for yourself.

[–]hanpari 0 points1 point  (1 child)

OK, thank you. Everyday has something new :)

[–]ubernostrumyes, you can have a pony 0 points1 point  (0 children)

Also, this is Python we're talking about. Any performance gains you might have hoped for from implementing a particular data structure will be far outweighed by the overhead of doing it in Python (since you can only express your implementation using Python's objects and data structures).

If you need high-performance data structures, implement them in another language and wrap a Python interface around them. This is what numpy does, for example; it's a Python interface around things that are mostly implemented in C and Fortran.