Так как большинство структур данных уже реализовано в 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;``
```
Остальные операции списка могут реализованы через базовые без потери эффективности.
Варианты реализации списка:
* на основе [односвязного списка](/viz/list2.html);
* ``list`` в STL -- на основе [двусвязного списка](/viz/list3.html);
* ``vector`` -- на основе массива переменного размера;
* через нелинейные структуры данных, если требуется быстрый произвольный доступ и быстрая вставка и удаление
В С++ есть односвязный список ``forward_list``, который не поддерживает интерфейс АТД Список.
Вместо ``insert`` предлагается применять операции ``insert_after`` и ``push_front``,
а вместо ``erase`` -- ``erase_after`` и ``pop_front``. Кроме того, нет метода ``size``.
Линейные АТД
Начало
Учебные материалы