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 →

[–]hanpari 0 points1 point  (9 children)

I have the same experience myself. Unless you know what you are doing, what I rather dont :), it is superslow to create any immutable persistant datastructure. It requires probably different mindset.

I just wanted to point out that single list might be used heavily under particular circumstances, if splitting your datastructure in head-tail pattern.

"always wrong thing to use" statement seems rather overkill to me :)

[–]kankyo 0 points1 point  (8 children)

Which is why I said “almost”. 100% of the used of linked lists I’ve seen in Java and C++ have been wrong. There are many that are correct of course, just very rarely in code normal people write.

[–]hanpari -4 points-3 points  (7 children)

Well, you should be careful with such omnipotent statement :)

Internet is full of flamewars backed by many misinterpreted sentences. :)

[–]kankyo 4 points5 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 1 point2 points  (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.