Подразделы

Другие разделы

Дата и время

29/03/2025 00:56:04

Авторизация

Зарегистрироваться
Восстановить пароль

Линейные АТД

Список Массив и Строка Стек Очередь Двухсторонняя очередь Очередь с приоритетами Множество Словарь

Список

Так как большинство структур данных уже реализовано в STL, мы будем рассматривать их как примеры реализации АТД, возможные альтернативы и сравнивать их эффективность.

АТД Список является представлением математической конечной последовательности, это набор элементов данных, организованных в заданном линейном порядке.

Базовые операции для списка:

Операция	Эффективность	Вызов
конструктор (пустой список)	$O(1)$	`std::list<int> s;` `std::vector<int> s;`
длина списка	$O(1)$	`auto len=s.size();` или `ssize(s);`
получение итератора на первый элемент (конец списка)	$O(1)$	`auto f=s.begin(), e=s.end();`
вставить перед итератором	$O(1)$ для `list` $O(n)$ для `vector`	`auto ne=s.insert(f,3);` возвращается итератор на добавленный элемент
удалить элемент по итератору	$O(1)$ для `list` $O(n)$ для `vector`	`s.erase(ne);` возвращается итератор на следующий элемент

где итератор также является АТД и обеспечивает последовательный доступ ко всем элементам набора:

Операция	Эффективность	Вызов
следующий (опционально предыдущий)	$O(1)$ для `list` и `vector`	`++it; --it;`
конец набора?	$O(1)$	`if(it==s.end()) ...`
доступ к элементу	$O(1)$	`auto x=it; it=x;`
`

Остальные операции списка могут реализованы через базовые без потери эффективности.

Варианты реализации списка:

на основе односвязного списка;
list в STL – на основе двусвязного списка;
vector – на основе массива переменного размера;
через нелинейные структуры данных, если требуется быстрый произвольный доступ и быстрая вставка и удаление