Почему доступ к элементам vector-а O(1)?
А с вектором дела обстоят иначе. Каждый элемент хранит указатель на следующий после него.
Такое поведение имеет список, односвязный или двусвязный.

Вектор же реализован как непрерывный блок памяти, внутри которого последовательно размещены его элементы. Благодаря этому элементы вектора доступны не только через итераторы, но и через адресную арифметику.

Именно поэтому доступ к любому элементу вектора имеет сложность O(1). Это просто смещение на индекс элемента относительно начала блока памяти с помощью адресной арифметики.
То, что вы называете вектором - это связанный список, по своей сути. Вот статья навики. Слово вектор, насколько, я знаю, не используется в контексте классических структур банных. Если же под вектором имеется в виду std::vector, то данный вектор создан на основе динамического массива.