'which is better a sorted ArrayList or a sorted linkedList?
When adding an element to a sorted arrayList you can find the position in O(logN) using binary search but you still have to move all the elements in front of it in order to add it. And in the worst case in which the position has to be the first element, all the elements of the list would have to be moved. Not to mention that it is possible that there is no space and there to call the reAllocate() method which I understand adds another O(N) in time complexity. In the worst case the time complexity would be O(logN) (binary search) + O(N) (having to move all the elements) + O(N) (reAllocate())? In a linked List you could not use binary search but you would not have to worry about having to move the elements forward one position or having to reAllocate(). I don't know how to conclude which one is better or if I'm missing something or if I'm misunderstanding something.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
