У меня такой вопрос. 
Как с помощью коллекций списков реализовать такой список что бы операции добавления элемента, удаления и поиска не превышали сложность log(n).
Я начал использовать коллекцию ArrayList, но удаление у меня вызывает большие сомнения, так как  в случае удаления например первого элемента должна как я понимаю переписать все индексы, а это O(n) шагов. Помогите срочно нужно. Спасибо заранее.

А List не удовлетворяет? Там все операции есть и индексы меняются там автоматом, но опять таки они там меняются так как ты написал. Иначе я думаю не получится.

посмотри на Dictionary, Remove и Contains по O(1), Add тоже O(1), пока capacity не превышена, иначе - O(n)

Добавлено через 4 минуты и 6 секунд
не заметил твой ответ на свой почти такой же ответ в соседней теме =)

Ещё вопрос есть ли тип который будет реализовывать просто список. Что бы удаление элементов с начала или с конца занимала только 1 операцию, я в принципе придумал выход что для list можно организовывать удаление за O(1), но удалять просто с конца списка, с последнего элемента тогда индексы сдвигать не прийдётся. Вроде бы вариант не плохой, но как бы реализовать удаления из середины списка за O(1) так как сложность то суммироваться будет и через поиск.
Кстати только придумал идея насчёт удаления если переопределять список заново в новый не добавляя старые элементы, по идее максимум O(n) вместе с поиском. выбрать достаточно трудно так как реализую алгоритм со сложностью O(n log(n)). 

И реализация дерева есть ли она, или как реализовать? всё таки дерево двоичное даёт логарифм