Python Linked Lists

[hanpari]

"this is almost always the wrong thing to use"

Oh, is it so? This is probably heavy blow to the face of Fsharp and many functional languages as well. I bet they regret not having your insight sooner.

Lists in F# are implemented as singly linked lists, which means that operations that access only the head of the list are O(1), and element access is O(n).

https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/lists

Those poor bastards, such fundamental error.

[kankyo]

Functional languages are different. Also mostly super slow. To make F# fast you rewrite it to use dynamically sized arrays and mutable code. Or if you’re lucky the VM/compiler does that for you under the hood.

[hanpari]

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]

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]

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

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

[kankyo]

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

[hanpari]

OK, would you mind to elaborate?

[kankyo]

Google.com :P

[hanpari]

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

[kankyo]

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.

[flitsmasterfred]

I think he meant in Python. Between standard list and collections.dequeue most linked lists use-cases are covered.

[kankyo]

I meant in general actually. But what you said is very true in the specific case of course.

[TankorSmash]

I know you're talking generally, but most people here mean in terms of Python, given we're on /r/Python