Каковы временные сложности различных структур данных?

Я пытаюсь перечислить временные сложности операций с общими структурами данных, такими как массивы, двоичное дерево поиска, куча, связанный список и т. Д., И особенно я имею в виду Java. Они очень распространены, но я думаю, что некоторые из нас не уверены на 100% в точном ответе. Любая помощь, особенно ссылки, приветствуется.

Например, для односвязного списка: изменение внутреннего элемента - O (1). Как это сделать? Вы ДОЛЖНЫ выполнить поиск элемента перед его изменением. Кроме того, для вектора добавление внутреннего элемента задается как O (n). Но почему мы не можем сделать это за амортизированное постоянное время, используя индекс? Пожалуйста, поправьте меня, если я что-то упускаю.

Я публикую свои выводы / догадки в качестве первого ответа.

Массивы

• Установить, проверить элемент по определенному индексу: O (1)
• Поиск : O (n), если массив не отсортирован, и O (log n), если массив отсортирован и используется что-то вроде двоичного поиска,
• Как указал Айвен , Deleteоперации с массивами недоступны. Мы можем символически удалить элемент, установив для него определенное значение, например -1, 0 и т. Д. В зависимости от наших требований.
• Точно так же Insertдля массивов в основном, Setкак упоминалось в начале

ArrayList:

• Добавить : Амортизированный O (1)
• Удалить : O (n)
• Содержит : O (n)
• Размер : O (1)

Связанный список:

• Вставка : O (1) , если выполняется в начале , O (n), если где-либо еще, поскольку мы должны достичь этой позиции, перемещаясь по связанному списку линейно.
• Удаление : O (1) , если выполняется в начале , O (n), если где-либо еще, поскольку мы должны достичь этой позиции, перемещаясь по связанному списку линейно.
• Ищем : O (n)

Двусвязный список:

• Вставка : O (1) , если выполняется в голове или хвосте, O (n), если где-либо еще, поскольку мы должны достичь этой позиции, перемещаясь по связному списку линейно.
• Удаление : O (1) , если выполняется в голове или хвосте, O (n), если где-либо еще, поскольку мы должны достичь этой позиции, перемещаясь по связанному списку линейно.
• Ищем : O (n)

Стек:

• Толкать : O (1)
• Поп : O (1)
• Сверху : O (1)
• Поиск (что-то вроде поиска, как специальная операция): O (n) (я так думаю)

Очередь / Deque / Круговая очередь:

• Вставка : O (1)
• Удалить : O (1)
• Размер : O (1)

Дерево двоичного поиска:

• Вставка, удаление и поиск : средний случай: O (журнал n) , худший случай: O (n)

Красно-черное дерево:

• Вставка, удаление и поиск : средний случай: O (журнал n) , худший случай: O (журнал n)

Куча / PriorityQueue (мин. / Макс.):

• Найти минимум / найти максимум : O (1)
• Вставить : O (log n)
• Удалить мин. / Удалить макс . : O (log n)
• Извлечение мин. / Извлечение макс . : O (log n)
• Поиск, удаление (если есть): O (n) , нам придется сканировать все элементы, поскольку они не упорядочены, как BST

HashMap / Hashtable / HashSet:

• Вставить / удалить : O (1) амортизировано
• Изменение размера / хеш : O (n)
• Содержит : O (1)