The true cost of linked lists

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 ]