5 ms·

> the only case for linked lists is doing a lot of in the middle inserts and deletes i thought that was the point of linked lists: O(1) insertion & deletion.

by chii 4y ago

lionkor 4y ago
Yes, but only after finding the element which is O(n) worst case
- adwn 4y ago
  In intrusively linked lists (the one usually used in kernels), you typically already have a pointer to the object, and therefore, to its next/prev pointers. For example, removing a task from the scheduler's RUN list and appending to the WAITING list is O(1), because you already have a pointer to the task, because the system's architecture is structured in such a way that you don't have to traverse the RUN list to find the pointer to the task's entry.
  - gpderetta 4y ago
    Exactly. Linked lists work well for secondary ordering of elements.
mauvehaus 4y ago
It depends on who's getting billed for the traversal to the point of insertion/deletion: If all you're doing is "Remove the mth item of the list" takes O(m) time to traverse and O(1) to do the removal if you're starting from the head. On the other hand, if you already have the pointer to the list element for some other reason, somebody else has already been billed for the traversal and the insert or removal is O(1). You see linked lists used a lot in e.g. the kernel where the traversal has been paid for to get a pointer to an element that has then been used for a bunch of things before a deletion or insertion happens. They also have the advantage that in the face of other threads mutating the list, the address of the elements remains constant. If you have a pointer ti an element in an array, and another thread comes along and does an insertion or deletion that moves it, now you have a problem. Single-threaded performance isn't the only criteria for picking a data structure.
- LorenPechtel 4y ago
  In the real world it's almost certain that somebody else already paid the traversal cost in making the decision of what to act on. The only common cases where that doesn't apply are removing the head (think queue) and adding the tail. The latter case can be handled by keeping a pointer to the tail in your control structure. A queue very well might be best implemented as a linked list rather than an array.

> the only case for linked lists is doing a lot of in the middle inserts and deletes i thought that was the point of linked lists: O(1) insertion & deletion.

by chii 4y ago

> the only case for linked lists is doing a lot of in the middle inserts and deletes i thought that was the point of linked lists: O(1) insertion & deletion.

lionkor 4y ago

Yes, but only after finding the element which is O(n) worst case

adwn 4y ago
In intrusively linked lists (the one usually used in kernels), you typically already have a pointer to the object, and therefore, to its next/prev pointers. For example, removing a task from the scheduler's RUN list and appending to the WAITING list is O(1), because you already have a pointer to the task, because the system's architecture is structured in such a way that you don't have to traverse the RUN list to find the pointer to the task's entry.
- gpderetta 4y ago
  Exactly. Linked lists work well for secondary ordering of elements.

mauvehaus 4y ago

It depends on who's getting billed for the traversal to the point of insertion/deletion: If all you're doing is "Remove the mth item of the list" takes O(m) time to traverse and O(1) to do the removal if you're starting from the head. On the other hand, if you already have the pointer to the list element for some other reason, somebody else has already been billed for the traversal and the insert or removal is O(1). You see linked lists used a lot in e.g. the kernel where the traversal has been paid for to get a pointer to an element that has then been used for a bunch of things before a deletion or insertion happens. They also have the advantage that in the face of other threads mutating the list, the address of the elements remains constant. If you have a pointer ti an element in an array, and another thread comes along and does an insertion or deletion that moves it, now you have a problem. Single-threaded performance isn't the only criteria for picking a data structure.

LorenPechtel 4y ago
In the real world it's almost certain that somebody else already paid the traversal cost in making the decision of what to act on. The only common cases where that doesn't apply are removing the head (think queue) and adding the tail. The latter case can be handled by keeping a pointer to the tail in your control structure. A queue very well might be best implemented as a linked list rather than an array.