undefined | Better HN

0 pointstialaramex3y ago0 comments

Why a linked list?

The linked list is a peculiar data structure which makes a lot of sense in the 1970s because all memory reads cost the same and addresses are small, but is terrible in most cases in 2022 because we have huge addresses and very fast local cache. There still are good uses for the linked list, but they're now pretty esoteric.

Using the list concept with recursion is great, but fast implementations of languages in 2022 do not lean on the linked list. Java's ArrayList, and the terribly named C++ std::vector, are more appropriate structures for a lot of cases where a 1970s algorithms book says "list".

0 comments

2 comments · 1 top-level

dahart3y ago· 1 in thread

Linked lists are probably most common in memory managers, and in embedded programming where memory is very tight, timing is critical, and the cache might be limited. Memory managers use intrusive linked lists to manage the free list; they need a data structure that doesn’t require malloc or new, can grow & shrink dynamically without relocating, and has constant time inserts & deletes from the middle of the list.

Linked lists aren’t very common in desktop application programming, if they ever were, and non-intrusive linked lists as container classes do seem particularly prone to having better alternatives, especially naïve implementations that allocate the list nodes and node content separately. One of the best reasons to reach for a linked list is to avoid all calls to new or malloc or free, so doubling up on them is especially silly.

I don’t think this is really a 70s thing though. Linked lists might have been used slightly more often in the past, but I think they’ve always been used far less than arrays, and my old algorithms books that predate std::vector just use arrays. Maybe the main utility of linked lists is to teach about pointers and algorithm complexity. They do make good examples of pointer management and of algorithms with different big-O than arrays, hashes, trees, etc. I maybe used linked lists a couple of times in games programming, but have rarely ever used them, while they were covered thoroughly in school.

tialaramexOP3y ago

For a conventional malloc-type memory manager I can see this, you don't want to actually walk this list in most cases, you may be concurrent (in which case cache defeating is a feature) and so on.

In embedded my guess would be that you see linked lists because lots of embedded programmers are C programmers and that's what they learned to do, not because it's actually a good choice. I reckon if you look at C programs I wrote in the 1990s there are a lot of linked lists, and I can't defend any of those as the right solution.