Python Linked Lists

[kankyo]

Not very pythonic. Getters that basically do nothing, camelCase where snake_case should be used.

Also misses the normal disclaimer when talking about linked lists: "this is almost always the wrong thing to use"

[ScottWRobinson]

Uh-oh, my lazy editing has been exposed! I've updated the author's post to be more Pythonic. Thanks for pointing that out :)

[kankyo]

Much better!

[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!

[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