Retrieval of an arbitrary item from a linked list is O(n). Arbitrary means any of the elements are eligible for selection, without loss of generality.
However, retrieval of a specific item from a linked list has nothing to do with how many items are in the list. It is therefore O(1). Retrieving the 50th item from a linked list takes the same amount of time, no matter whether the list has 50 elements, 50M elements, or 50^50! elements.
I'm not sure what you mean by caching. We are just talking about the standard linked list implementation with a
head
pointer, and where each node has anext
pointer, and nothing more.I make the following claims: