* Под всё имеется в виду относительно быстрое выполнение операций над единичным элементом массива.
Структур данных, которые реализуют список полно. У всех есть свои достоинства и недостатки. Например в мире Java — в зависимости от необходимых операций — можно использовать:
Когда мне понадобилась структура с быстрыми add(obj), get(index), remove(index) и indexOf(obj), то google не дал ответа. Ни примеров кода, ни описания подобных структур я не нашел. Возможно не там искал, пришлось выдумывать самому. Но если кто-то скинет ссылку в комментариях, то буду весьма признателен.
Возможно, кто-то догадался, что можно взять TreeList, который умеет быстро вставлять/удалять элементы в середине списка и добавить к нему HashMap из объекта в индекс в TreeList для быстрого выполнения indexOf(obj). И это будет простое, изящное, но неверное решение. Ведь при добавлении в середину или удалении из середины нужно будет пересчитать индексы, в среднем, для половины элементов. Это ухудшит производительность до O(n).
Дальше я расскажу о структуре данных, которая может всё из перечисленного выше. Которая выполняет любую операцию над одним элементом за O(log(n)) времени. Ну почти — за логарифм выполняется в том случае, когда все объекты в списке различны. Если в списке есть одинаковые объекты, то возможно проседание производительности вплоть до O(log(n) ^ 2).
Структур данных, которые реализуют список полно. У всех есть свои достоинства и недостатки. Например в мире Java — в зависимости от необходимых операций — можно использовать:
- add(obj), get(obj), set(index, obj): базовый набор почти всех списков, например ArrayList.
- add(index, obj): структуры в виде дерева, например TreeList из apache common-collections.
- remove(index): то же, что и выше.
- contains(obj), indexOf(obj): можно использовать связку ArrayList и HashMap.
- remove(obj): … затрудняюсь ответить. В некоторых случаях можно обойтись LinkedHashSet. Решается тривиально при наличии предыдущих двух пунктов, но какие структуры могут и то и другое быстро?
Когда мне понадобилась структура с быстрыми add(obj), get(index), remove(index) и indexOf(obj), то google не дал ответа. Ни примеров кода, ни описания подобных структур я не нашел. Возможно не там искал, пришлось выдумывать самому. Но если кто-то скинет ссылку в комментариях, то буду весьма признателен.
Возможно, кто-то догадался, что можно взять TreeList, который умеет быстро вставлять/удалять элементы в середине списка и добавить к нему HashMap из объекта в индекс в TreeList для быстрого выполнения indexOf(obj). И это будет простое, изящное, но неверное решение. Ведь при добавлении в середину или удалении из середины нужно будет пересчитать индексы, в среднем, для половины элементов. Это ухудшит производительность до O(n).
Дальше я расскажу о структуре данных, которая может всё из перечисленного выше. Которая выполняет любую операцию над одним элементом за O(log(n)) времени. Ну почти — за логарифм выполняется в том случае, когда все объекты в списке различны. Если в списке есть одинаковые объекты, то возможно проседание производительности вплоть до O(log(n) ^ 2).
