Memory reads and memory writes are not the same. Linked list insert in the middle needs to do only O(1) writes. But because linked lists preclude memory prefetch, they should not be used these days.