CODEWITHSUNDEEP
javacollections
pavan
pavan

Reputation: 101

Do elements in LinkedList class of java have index?

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?

Upvotes: 8

Views: 10553

Answers (2)

Eran
Eran

Reputation: 393851

Elements in LinkedList don't hold any index information, and there is no mapping from an index to an element.

If you request to add an element to the i'th position (by calling add(int index, Object item)), it will require iterating over the elements of the LinkedList from its start or from its end (depending on which one of them is closer to the requested index) until the requested index is reached.

Upvotes: 4

Jon Skeet
Jon Skeet

Reputation: 1500815

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.

Upvotes: 12

Related Questions