Bloomberg LP Interview Question
Software Engineer / DevelopersLinkedList is used when access to objects is sequential and the sequence needs often reordering (insertion, deletion, and so on).
ArrayList is used when access is random. Even sequential access might perform faster because of caching (array elements are clustered in same memory pages, while lists could be spread random in memory).
Array List
Advantages of using arrays:
Easier to use and access
Faster access to the elements
Disadvantages of using arrays:
Fixed size - the size of the array is static
One block allocation - if you don't have enough memory to provide a single block (but you have sufficient scattered memory blocks) to allocate the space for the array then you'll need to defragment and other similar stuff to first create a free block of that size. So you may like to term it as improper utilization of memory :-)
Complex position-based insertion - if you want to insert an element at a position already covered by some other element then you got to shift right by one position all the elements to the right of that position. This will vacate the position for you to insert the new element at the desired position. The more elements you have to the right of the desired position, the more expensive the process will be :-)
Linklist
Advantages of using Linked Lists:
Flexibility - insert at (or delete from) any position in contant time
No single allocation of memory needed - fragmented memory can be put to a better use
Dynamic allocation - the size is not required to be known in advance
Disadvantages of using Linked Lists:
Complex to use and access - relatively complex as compared to arrays
No constant time access to the elements - simply because it doesn't involve the simple arithmetic used by arrays to compute the memory address, so relatively inefficient as compared to arrays
1) ArrayList is preferred when the search we are looking for is random index based.
2) LinkedList is preferred when we have require to perform several add and delete operations anywhere in the list.
3) There is more memory overhead in case of LinkedList as the data is an Object (data+node) whereas only data in the case of ArrayList.
4) ArrayList has an Array implementation internally which is of size 10 by default. This makes addition of elements relatively faster in LinkedList as there is no resizing.
5) Iteration is relatively faster in the case of ArrayList as the memory locations are ordered.
Linked list is ideal for iteration in one of both directions. ArrayList is one that has an attached vector to allow random access as well at a cost of using extra memory.
- achacha May 24, 2006