If you implement Java List using arrays, you get long insert/delete. If you implement it using lists, you also get long insert/delete, so it buys you nothing. Arguing that a list is somehow better than an array in this context is simply misleading the learners. (Actually, arrays should be quicker because of HW acceleration and better locality.)
BTW, what you need here is an implicit treap. But that is not a standard collection and you should provide it yourself as a data structure for this task.
If you implement Java List using arrays, you get long insert/delete. If you implement it using lists, you also get long insert/delete, so it buys you nothing. Arguing that a list is somehow better than an array in this context is simply misleading the learners. (Actually, arrays should be quicker because of HW acceleration and better locality.)
BTW, what you need here is an implicit treap. But that is not a standard collection and you should provide it yourself as a data structure for this task.