An arraylist. A linked list always takes O(n) worst case for searching. On the other hand, an arraylist can be sorted one time, at cost of O(n log(n)). After that, we can do binary search which takes time O(log(n)). The average cost of a search after n searches for the arraylist would be (n log(n) + n * log(n) )/n = O(log(n)). Compare this is the average search time of a linked list: n * n/n = O(n).