For an ArrayList of a particular type, we can find the size of object (of a particular type) in the ArrayList, and directly access the object at any index in O(1). This is because object references are stored in contiguous chunk of memory in ArrayList, and hence by skipping object_size * index memory locations, we access the memory location where the reference of desired object is residing.
Whereas, in LinkedList, we would have to iterate through each object till we reach the desired object.
For a generic ArrayList, containing different types of objects (with varying sizes), is get(index i) done in O(1)? If so, how?
Advertisement
Answer
You working under a misconception. Objects are not stored in arrays, only references (i.e. pointers) to objects are stored in the array. Objects themselves are on the heap. Therefore finding a specific object in an ArrayList by index will always be O(1) regardless of what it contains, and a LinkedList will be O(n).