Большое всем спасибо.

Естественно, нас интересует очередь с приоритетом. Храниться она будет всегда в отсортированном виде.
Ну смотри. Если у тебя отсортированный массив (по дате запуска команды), то чтобы добавить к нему элемент ты делаешь push + sort. Второй вариант для массива - это search + splice (то есть находим нужную позицию и на нее уже вставляем). Оба варианта рождают новый массив и нифига не кажутся оптимальными.
В случае со связным списком - ты делаешь search + insert. Где insert - это просто переписывание 2 ссылок (список односвязный). И даже если геттерами и сеттерами, оно все равно выглядит лучше, чем создание и перезапись нового массива.
Перебирать список можно циклом while, так что по скорости доступа будет почти то же самое что и массив (ну да, за исключением гарантированного вызова геттера (node = node.next) на каждую итерацию).
Далее, что касается удаления из связного списка - то покуда у тебя есть ссылка на удаляемый элемент, это будет тебе стоить максимум перезапись 2 ссылок (опять же, односвязный список)

Старовато, но тут даже какие-то бенчмарки есть.