4 ms·

Because (doubly) linked lists can do something an array cannot? Like join operations in O(1)? Or removing an arbitrary element in O(1) once you have its handle?

• blibble 10y ago
  if it's unordered (like you'd expect a list of sockets to be) you can get O(1) removal for an array by swapping the end item into the removed slot
  • dozzie 10y ago
    ...unless something else holds a pointer to the handle you're swapping with.
    • blibble 10y ago
      kernels don't tend to give userspace raw pointers into kernel memory
      • dozzie 10y ago
        But kernels tend to give raw pointers to other kernel code.
        • blibble 10y ago
          a good chunk of the fun in kernel code is maintaining the various layers of self-referential lists and dealing with the cleanup
    • staticassertion 10y ago
      This is already a problem if you're removing an item, regardless of whether it's done with swap remove or not.
      • toast0 10y ago
        For the item you're removing, you are presumably removing it because all handles have been closed. But the item you're potentially swapping with may certainly have open handles.
        • staticassertion 10y ago
          True.