Do elements in LinkedList class of java have index?

Question

Do elements in LinkedList class of java have index? If yes then why is its performance o(n) in worst case for search operation when it can directly search using index of the object? If no then how can we insert an object in the middle of the linkedlist using the void add(int index, Object item) method?

Answer 1

They have a logical index, yes - effectively the number of times you need to iterate, starting from the head, before getting to that node.

That's not the same as saying "it can directly search using index of the object" - because it can't.

Typically O(1) access by index is performed by using an array lookup, and in the case of a linked list there isn't an array - there's just a chain of nodes. To access a node with index N, you need to start at the head and walk along the chain N times... which is an O(N) operation.