Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
"If you frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList. These operations require constant-time in a LinkedList and linear-time in an ArrayList. But you pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList."
The question pertained to collection framework , you can put an object in the middle by specifying index in Linkedlist.
What answer I gave to him was is that when you add an element to an array outside its bound. The arraylist expands by 50% but here the problem is for one element you expand by 50% which is not required by LinkedList.
ArrayList implements the Random Access Interface, which means u can access an element like an array by using its index. LinkedList implementation in collections helps you to specify the location index as well, but it uses the head or tail pointer to traverse to that node, based on whichever is close by.
Random Resizing is another feature of arrayList which can be done to ensureCapacity() for incoming elements. No such specs in linkedList.
LinkedList takes lesser space as it never stores null nodes, ArrayLists might be augmented or decremented by a constant value which might occupy more space.
Array:
In array we cannot add or delete an element, except that we can add at the end
Arrays have fixed length
Finding an element takes O(1) time
LinkedList:
In LinkedList an element can be added at any place after creation at any time
Insertion and deletion takes O(1) or constant time
There is no particular size in linked list, so any number of elements can be added until memory runs out
Finding an element takes O(n) times
If you frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList. These operations require constant-time in a LinkedList and linear-time in an ArrayList. But you pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList.
- llval April 11, 2012