The true cost of linked lists

Re:The true cost of linked lists by marginalia_nu on Monday June 06, 2022 @08:05AM (#31639412)

I think the problem is that we're thinking about linked lists like they are taught in intro to algorithms. Like

  ListNode* a = new ListNode('A');
  ListNode* b = new ListNode('B');
  ListNode* c = new ListNode('C');
  a.next = b;
  b.next = c;

That's a dumb way of implementing a linked list with no redeeming features outside of explaining the concept.

This is a linked list with the same shape as the list above, but with completely different performance characteristics:

  int* data = new int[3];
  data[0] = 'A';
  data[1] = 'B';
  data[2] = 'C';

  int* links = new int[3];
  links[0] = 1;
  links[1] = 2;
  links[2] = -1;

With some elaboration (say exchange the arrays for a mmap-call, turn it into a tree instead of a list) and you're basically looking at the guts of a DMBS or a file system.

[ Parent | on HN ]

Re:The true cost of linked lists by MontyCarloHall on Monday June 06, 2022 @08:30AM (#31639623)

>turn it into a tree instead of a list

Sounds a lot like “draw the rest of the damn owl.” [0] :-)

DBMSs and file systems use (extremely sophisticated) tree structures under the hood. Not sure that “linked lists are useful if the linking topology is much more complicated than a simple line” is a ringing endorsement of them.

[0] https://pbs.twimg.com/media/Bs13i6LCcAAvwCf.jpg

[ Parent | on HN ]

Re:The true cost of linked lists by marginalia_nu on Monday June 06, 2022 @08:34AM (#31639662)

My point is that this general sketch of a layout with arrays of offset pointers roughly generalizes to something like a B or B+-tree fairly well, and that's a fairly simple data structure. You can absolutely implement a file system with passable performance with either of those tree structures.

( Here's an enjoyably lucid explanation on how to draw such an owl: https://www.youtube.com/watch?v=aZjYr87r1b8 )

[ Parent | on HN ]

Re:The true cost of linked lists by BosStartup on Monday June 06, 2022 @09:19AM (#31640081)

This has the same issues as just using an array to store the data. If you remove a node in the list now you have to rewrite all the values in the links array. If you don't do that then you have to implement your own garbage collector and pay the penalty periodically.

[ Parent | on HN ]

Re:The true cost of linked lists by marginalia_nu on Monday June 06, 2022 @09:28AM (#31640177)

> If you remove a node in the list now you have to rewrite all the values in the links array.

You actually don't. You can just keep two lists within the same structure, one for occupied nodes and one for free nodes, and just move deletions to the head of the free nodes list.

Example List:

  Data: [ a, 0, c, d, e ]
  Links: [ 2, -1, 3, 4, -1 ]

  Head of occupied nodes: 0
  Head of free nodes: 1

Link shape:

  Occupied Nodes: 0 -> 2 -> 3 -> 4 -> []
  Free Nodes: 1 -> []

To Delete C:

  data[2] = empty // free data
  links[2] = 1 // Repoint 2 -> 1
  links[0] = 3 // Repoint 0 -> 3
  firstFreeNode = 1

This changes the data such:

  Data: [ a, 0, 0, d, e ]
  Links: [ 3, 2, -1, 4, -1 ]

  Head of occupied nodes: 0
  Head of free nodes: 2

New shape:

  Occupied Nodes: 0 -> 3 -> 4 -> []
  Free Nodes: 2 -> 1 -> []

[ Parent | on HN ]

Re:The true cost of linked lists by ziml77 on Monday June 06, 2022 @08:20AM (#31639548)

Is there a reason the keep the data and the indices in different arrays? Unless you're navigating to an item by its position in the linked list, you're going to be checking the data at each node and then reading the next index to traverse forward. Since you're reading both, wouldn't it be better to make the index of the next node intrusive?

[ Parent | on HN ]

Re:The true cost of linked lists by marginalia_nu on Monday June 06, 2022 @08:23AM (#31639571)

The design is mostly to provide a clear enough example, you can of course interlace them.

It depends on the use case.

If you're doing a lot of navigating over links before you reach the destination, maybe you want them separate. Could also be the data is large, even maybe stored on disk while the links are in memory, or whatever. There's a thousand different scenarios with different optimal arrangements.

[ Parent | on HN ]

Re:The true cost of linked lists by magicalhippo on Monday June 06, 2022 @09:00AM (#31639891)

It allows you to reorder the data, say sorting it, without moving the actual data. If the element type is say a struct, this can be a huge performance win.

It also allows you to keep multiple different lists to the same data, say sorted by different fields in the struct.

[ Parent | on HN ]