Разница между вектором и связанным списком ADT

Question

Может кто-нибудь объяснить мне разницу между Vector и ADT Linked List в контексте языка программирования c.

Спасибо.

Answer 1

Ну, в C нет доступных типов данных "vector" и "list", доступных вам напрямую, как в библиотеке C ++ std. Но в терминах «абстрактного типа данных» вектор обычно считается представляющим непрерывное хранилище, а связанный список считается представленным отдельными ячейками, связанными вместе. Векторы обеспечивают быстрые операции чтения и записи с произвольным доступом в постоянное время, но вставка и удаление векторных элементов занимают линейное время. Списки имеют линейную производительность поиска, чтобы найти элемент для чтения и записи, но, учитывая расположение элемента, имеют постоянное время вставки и удаления. Вы также можете добавлять элементы в начало и конец списка за постоянное время (если реализация ADT кэширует местоположение последнего элемента в списке).

Answer 2

Вектор часто реализуется как непрерывный блок памяти в виде массива. Принимая во внимание, что список может быть распределен по памяти, так как каждый элемент содержит указатели на один или несколько других элементов (может быть дважды связан). Это дает векторам преимущество в скорости доступа, но перечисляет преимущество вставки / удаления.

Answer 3

вектор - это динамический массив.элементы внутри смежны в памяти.Элементы внутри связанного списка не являются смежными.

Answer 4

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

http://www.codeguru.com/forum/archive/index.php/t-309352.html