Hacker News Reader

Comment by boomlinde | Hacker News Reader

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.

View on HN

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.

That’s an incredible amount of effort to throw at an argument on Hacker News.

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.

Reply on news.ycombinator.com