If some function parameter recieves List<List<Integer>> nums , then the nums is instanti-CodePudding

Both LinkedList and ArrayList are built on the List interface, yet the LinkedList uses the traditional pointer technique to build a list, and ArrayList uses array to implement List functionality . So what can one claim before using the nums will it be using ArrayList or LinkedList behind the screen?

How I got this question?

    public int[] smallestRange(List<List<Integer>> nums) {
        
    }
}

Most of The Leetcode Java question has this format of the input. Without the prior knowledge of how the nums have been instantiated, how can someone use nums.get(i) function (list.get(i) is O(1) in ArrayList and O(n) in linkedList )

CodePudding user response：

99% of the time, it'll be an ArrayList, and you want to use an ArrayList in your code. They use less memory, are faster, and code taking advantage of LinkedList can usually be rewritten to use two ArrayLists. The main downside is add() occasionally running in O(n) time.

how can someone use nums.get(i)

You don't. You take advantage of the list being Iterable and do things like for-each loops:

for (var i : list) {
    ...
}

this runs in O(n) time for both LinkedList and ArrayList.

Technically, there's an interface called RandomAccess you can check to see if get() is O(1). You probably don't want it, though. Use the iterator.

if (list instanceof RandomAccess) {
    list.get(...);
}

CodePudding user response：

You can't directly predicate that what is default implementation of the List Interface. Interface is just a specification and you have multiple implementations of List Interface like you have mentioned in the image.

Every implementation will just override the method that mentioned in the List interface but their logic will be different based on the data structure.

Now its totally depend upon you which implementation you want based on your requirement. Whether you have space constraint or time constraint. But both will have same method as they are specified in interface.

As per coding challenges platform I think they specify the code from where they have call this method. You can check there But if it is not specified then most probably they will choose ArrayList - for time constraint. And I think a user should not be worried about the implementation that the they chosen. As I told user should know what is his requirement and then only choose implementations.

CodePudding user response：

It can be either of them:

  List<List<Integer>> list1 = new ArrayList<>();
        
  List<List<Integer>> list2 = new LinkedList<>();

  int[] x = smallestRange(list1); //works
  int[] y = smallestRange(list2); //also works

You need to make your code be able to cater to both types