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

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

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

Я размещаю свои выводы / догадки как первый ответ.