LinkedList Searching time complexity in java

Question

I am confused over the searching complexity of LinkedList in java. I have read that time complexity to search an element from a LinkedList is O(n). say for example,

LinkedList<String> link=new LinkedList<String>();
    link.add("A");
    link.add("B");
    link.add("C");
    System.out.println(link.get(1));

Now, from here by get(index) method we can say that to search an element It should take O(1) times. But I have read that it will take O(n). Can anybody help me out to get clear concept?

get(index) takes O(n), not O(1). What makes you think it takes O(1)? — Louis Wasserman, Feb 18 '16 at 20:12
Searching an object and getting object at a known index are not the same thing. That said, getting an object from a linked list is usually `O(n)` time since you have to traverse the list (not sure about Java's implementation specifically). — Reut Sharabani, Feb 18 '16 at 20:14
The get(index) method is a constant time, O(1), operation. follow the links:http://stackoverflow.com/questions/2182597/time-complexity-for-java-arraylist — stumbler, Feb 18 '16 at 20:15
@PeterLawrey is that true for `LinkedList`? I assume that's true for other implementations. — Reut Sharabani, Feb 18 '16 at 20:16
@ArindamKotal one of the difference between ArrayList which has a O(1) get method, is that LinkedList has an `O(n)` get method. — Peter Lawrey, Feb 18 '16 at 20:16
@ArindamKotal - That link you posted is for an `ArrayList` not a `LinkedList`. — JonH, Feb 18 '16 at 20:17
@ReutSharabani I am sure you could implement a List which is not O(1) for get(1) but all the ones in Java that I know for start at the start. If you had a singly linked list which was inverted like a stack.... — Peter Lawrey, Feb 18 '16 at 20:18
@ReutSharabani similarly, remove(index) for ArrayList is `O(n)` but `remove(list.size()-1)` is `O(1)` — Peter Lawrey, Feb 18 '16 at 20:19
@ArindamKotal to find the nth element of a link list you have tranverse n nodes, this makes it O(n). In an ArrayList, you can look up any element without looking at any other, the cost is always the same no matter where it is in the array. — Peter Lawrey, Feb 18 '16 at 20:21
@PeterLawrey I know that, I missed the constant `1`. That's key here... — Reut Sharabani, Feb 18 '16 at 20:21

score 7 · Answer 1 · answered Feb 18 '16 at 20:15

7

Access in a linked list implementation, like java.util.LinkedList, is O(n). To get an element from the list, there is a loop that follows links from one element to the next. In the worst case, in a list of n elements, n iterations of the loop are executed.

Contrast that with an array-based list, like java.util.ArrayList. Given an index, one random-access operation is performed to retrieve the data. That's O(1).

answered Feb 18 '16 at 20:15

erickson

265,237
58
395
493

As randomAccess is in ArrayList it takes constant time to search an element in worst case. LinkedList there is no RandomAccess interface, so in worst case it has to search the whole list. – stumbler Feb 18 '16 at 20:29
Yes, that's right. But `LinkedList` doesn't implement the `RandomAccess` interface because it doesn't support random access. The way you said that makes it sound like the effect is the cause. – erickson Feb 18 '16 at 20:36
Not the whole list but a half of the list – MaxZoom Feb 18 '16 at 20:37

score 1 · Answer 2 · answered Feb 18 '16 at 20:28

A linked list is as such, a list of items that are linked together by a means such as a pointer. To search a linked list, you are going to iterate over each item in the list. The most time this will take, will be T(n) where n is the length of your list.

A big-O notation stands for the upper bounds or the worst case scenario.

If you are searching for an item at index 1 it will finish almost immediately, T(1), since it was the first item in the list. If you are to search for the n^th item it will take T(n) time, thus staying in O(n).

A visual representation of a linked list:

[1] -> [2] -> [3] -> [4] -> ... [n-1] -> [n]

An example of what a get() method might look like

get(int i)
{ 
 Node current = head
 while (i > 0)
 {
   current = current.getNext()
   i--
 }
 return current
}

As you see, it iterates over each node within the list.

score 0 · Answer 3 · answered Feb 18 '16 at 20:16

The Ordo function means a maximal approximation. So it is O(n) because if the list has n entries and you want to get the last entry, then the search goes through n items.

On the other hand, lookup for an ArrayList is O(1), because the lookup time is close to constant, regardless the size of the list and the index you are looking for.

LinkedList Searching time complexity in java

3 Answers3