7

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?

Vlad
  • 18,195
  • 4
  • 41
  • 71
pavan
  • 91
  • 1
  • 6

2 Answers2

11

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.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • So if I have 100000 objects and I need to insert a new object at 99998th position then which one is better ArrayList or LinkedList??? – pavan Jul 19 '15 at 07:22
  • 1
    @user3275663: Unfortunately, with the API that `LinkedList` provides, `ArrayList` would definitely be the winner there. In other APIs, you could work *backwards* from the end (so just 2 positions) and then insert cheaply at that point. – Jon Skeet Jul 19 '15 at 07:24
  • 1
    Can you please mention the API through which we can work backwards and insert an object?? – pavan Jul 19 '15 at 07:29
  • @user3275663: Well in .NET you could use `LinkedList.Last` to get the last node, then keep calling `Previous` on that. But as I said, the API that the Java `LinkedList` exposes doesn't have that ability. – Jon Skeet Jul 19 '15 at 07:30
  • 1
    @user3275663 Actually, inserting a new object at 99998 for a list of 100000 will have similar performance for both ArrayList and LinkedList. For LinkedList, `Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index`. Therefore your insert will iterate from the end of the linked list and only visit two elements. And you can also get to the last node of the LinkedList and move backwards from it by using a ListIterator. – Eran Jul 19 '15 at 07:47
  • @Eran: Ah, I wasn't aware of that. Nice. – Jon Skeet Jul 19 '15 at 08:02
  • ArrayList vs LinkedList http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – cahen Jul 19 '15 at 09:14
3

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.

Eran
  • 387,369
  • 54
  • 702
  • 768
  • 1
    They *do* have an index, which is why you can use `indexOf`, `get(index)` etc. It's just that that doesn't map to "an index in an array". They may not have a field called `index`, but that doesn't mean you can't find out where they occur within the list. – Jon Skeet Jul 19 '15 at 07:16
  • @JonSkeet If by having an index you mean having an order, then yes, you can say they have an index. Using that logic you can say that elements in a SortedSet have an index too. – Eran Jul 19 '15 at 07:17
  • 2
    There clearly *is* a mapping from an index to an element: `LinkedList.get(index)`. In what way is that *not* a mapping from index to element? (And actually, I'd say that for *Sorted*Set as opposed to other sets, there's a reasonable index too, but it's not typically viewed that way.) – Jon Skeet Jul 19 '15 at 07:19