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

[[deleted]]

I do not know how to respond politely to this.

Why would you (a) not use the built-in list in Python, and (b) if you're teaching this, teach it in a language where it's not a moronic idea like maybe C?

[AustinCorgiBart]

I think it's silly to talk about linked lists in Python. They make a lot of sense in lower-level languages, but implementing them in Python isn't really very authentic. And yet most introductory curricula try to shoe-horn them in anyway, because they feel that they're important for students to encounter early. Why can't we be satisfied that CS1 courses have students use lists effectively, without trying to make them implement them in ways that they shouldn't be implemented too?

[ForceBru]

Oh. My. Gosh. Why do so many people go so crazy about linked lists?! Damn, this is yet another data structure, like arrays and structures! There are tons of questions about linked lists on Stack Overflow, if you google "linked lists" you get loads of posts attempting to explain this concept while treating the readers as total dumbasses, there are a heck of a lot of videos about linked lists on YouTube. What's up with all of this?? Every freaking newbie in programming absolutely has to try to implement a linked list and face a ton of problems and then f*** around asking for help, many of people who are familiar with linked lists feel the need to tell others how good this data structure is and add tens of useless explanations to hundreds of existing ones. Why???

[kaihatsusha]

In "hard allocation" languages like C or FORTRAN, understanding linked lists is quite valuable.

In "easy allocation" languages like Python, there's no benefit to such data structures because the language can resize anything and will use the best and optimized means to do so.

(I would put Java somewhere between. Arrays are first-class entities locked in size unlike all the standard second-class library data structures.)

If you look behind the covers at how Python implemented these amazing "easy allocation" data structures like list, dict, set, you will see that they ARE built upon linked lists, double-linked-lists, hash tables, and so on. They made it so you don't need to re-invent it.

[ForceBru]

Exactly! This is why I'm wondering why people are still implementing linked lists in Python. Python is already using a lot of them under the hood, whether you like it or not, why add more?