Что такое массив и связный список? В чём разница по O-сложности операций?

Массив хранит элементы последовательно и позволяет быстро получить значение по индексу. Связный список состоит из узлов со ссылками на следующие элементы: вставка и удаление известного узла выполняются быстро, но поиск и доступ по индексу требуют прохода по списку.