Linked lists should be obscure niche data structures for when you absolutely need their unique characteristics, not some front-and-center default.
They're not obscure or niche, they are everywhere in operating systems. The linked list is probably the single most essential and the most used data structure in any kernel.
Implementing an operating system is incredibly niche and obscure.
The practices that apply to kernel development do not generally apply to very much else.
Ah yes, operating system kernels, famously super mainstream programs that almost everyone works on.
This is true for the kind of programmin most people do. Linked Lists make no sense in JS, Python, Rust, etc. But they are without a doubt still an incredibly useful pattern with unmatched performance characteristics. Especially if you're trying to be memory efficient. It's a systems programming pattern, rarely useful if you're just a web developer.
But then again... I never thought I'd need to know music waveform theory while I was watching the magic school bus as a kid... Turns out that was incredibly useful when I needed to implement a music note generator for a VoIP client... You never know when something might actually be really useful.
This comment makes no sense.
1. You have linked lists in Rust. They're in the standard library.
2. Linked lists do not have "unmatched performance" - they are slower than almost anything, outside of highly specialized use cases. Even moreso for intrusive linked lists. Worst of all, they are horrible for cache locality.
There are valid uses of linked lists, that's why they exist, but most people don't have those use cases.
Speed isn't the only performance metric that matters. I probably should have said explicitly that I'm referring to uses where it makes sense to use a linked list. But unfortunately I didn't specify because that wasn't the point I really wanted to make.
There's a lot of things to learn that appear to to not makes sense... until suddenly they do.
> There are valid uses of linked lists, that's why they exist, but most people don't have those use cases.
Isn't that pretty much what I said?
I'm pretty sure we agree that they're useful, but their usefulness isn't as universal nor as common as the pattern is.
Linked lists are worse than flat arrays in every single performance metric other than ordered removal. They use more memory (the links), have inferior cache locality, cause more allocations (unless you're allocating anyway, in the case of intrusive lists).
Their one benefit - O(1) ordered removal - is easily achieved with a flat array, in at least two common ways: swap in the last element if you don't care about the order, or mark the index as vacant if you do care about the order, or if you care about the stability of references.
I mean, I agree that they're kind of neat from a certain perspective, but they're almost never the right choice.
About the ordered removal, if it's not very common, using tombstones (a constant to denote no element) is fine. Too many tombstones would need a compaction phase and still it'd work way better than a linked list.
Personally I have not met a case where a random removal in the middle of a list is common -- b/c finding the needle is slow to begin with O(n). In such case linked hash sets are O(1) but way more memory intense (which is a very advanced linked list)
That being said linked queues are great for concurrent lock free cases.
Dynamic arrays often use doubling as a resize strategy. This means that on average about 25% of capacity is "wasted". Depending on element size and element count it may lead to larger memory usage compared to linked list.
>Especially if you're trying to be memory efficient
Linked list have higher const cost memory wise compared to array backed structures. Even when an array back structure is half empty it's still takes less memory.
> Even when an array back structure is half empty it's still takes less memory.
uh... what?
I’m all about data-oriented design, but I don’t think this is true - you need their unique characteristics in almost every project.
In all of my years, I have seen maybe 2 projects that had one valid use case each. They exist, sure. It's not that common.
Out of curiosity I looked up some of the software I've meaningfully interacted with today. Of all I looked up—the operating system kernel, the init system, the shell, the terminal emulator, the browser, the compilers, the text editor, the windowing system, the window manager, the notification daemon, the audio server, the audio session manager, the GPG agent, the NTP daemon, the SSH daemon, the DHCP client, the wireless network manager, the power manager, the policy manager, D-Bus, the video player, the video editor—each uses linked lists. There's some more system software showing up in ps (which by the way uses linked lists) that I haven't considered but I am rather confident that most of it uses linked lists.
Maybe you only see these projects as a user, but linked lists are not uncommon. Your experience reflects your, well, experience. We all sit in different niches.
I'm wondering what makes you feel confident about the use of linked lists in all of those components.
Mind you, most of those will be written in C on a typical Linux installation, and linked lists happen to be one of the two collection types that are relatively easy to use in C (the other being a flat array), so I will concede that some software is using linked lists out of desperation, rather than it being the correct choice. :-)
> I'm wondering what makes you feel confident about the use of linked lists in all of those components.
Of all of those mentioned I literally looked up their source repositories up and searched for obvious indicators like "linked", "list", ".next" or "->next" and then verified that I was indeed looking at one or more linked lists. Where does your confidence come from? Oh right, you already mentioned it: it's based on your experience of the projects you've worked on.
The rest of your reply is just moving goalposts, mind reading and a glaring category error. Get back if and when you have something useful to add.
Not really desperation, it's just easier. Sometimes this is where perf doesn't matter, any choice would be fine, a linked list of the up to 4 Doodads won't be meaningfully worse or better than a growable array of the 4 Doodads, or I dunno, a HashMap from index to each of the four Doodads. Stop worrying about it and focus on the real problem.
In larger C software sometimes a use of linked lists is costing meaningful performance and a growable array type would be a huge win - but the other side of the coin is that sometimes in these perf critical environments a linked list actually is the right choice, and a C programmer might luck into that since it was the first tool to hand while say a C++ or Rust programmer might take longer to realise that this data structure is the best option.