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) ti

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.