Java List Get function time complexity


  • 0
    H

    Since we don't know exactly how this List<> is implement.

    To achieve O(n) when iterate through the list,

    should we use for(Object e : List) other then list.get(index) ?

    I am confused.


  • 0
    S

    I think it depends on what the instance of your list is.

    If it's an ArrayList<>, The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. (From Java Doc). So did the for loop.

    If it's an LinkedList<>, list.get(index) would require O(n) time as far as I know. So use list.get(index) to go through the list would require O(n^2) time. The for loop will require O(n) time to loop through all elements.

    And the best way to loop through a list/set/map is to use Iterator. It always optimize the run time to call iterator.next().


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.