Вектор и связанный список

Основные структуры данных

Логические струтктуры данных

Часть 3. Типовые структуры данных

1. Множества – важен только факт вхождения элемента в структуру; примеры: математические множества, таблицы реляционных баз данных.

2. Массивы – важно местоположение (номер) элемента; пример: массивы различной размерности.

3. Графы – важны связи между элементами; пример: деревья, сети, графы.

Примеры: очередь (FIFO, LIFO (стэк)), множество, дерево, поле указателей.

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

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

Связанный список соответствует хранению каждого данного по своему адресу, независящему от адресов других элементов. Каждый элемент хранит служебную информацию – адреса одного или нескольких соседних элементов, благодаря чему осуществляется связь между всеми элементами списка. Также может храниться указатель на управляющую структуру, хранящую обобщённую информацию о списке, например, размер, адрес первого элемента и т.д. В списке нет ограничений на размер каждого элемента и на рост списка.

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

Каждый элемент односвязанного список хранит адрес только следующего элемента, поэтому доступ может быть осуществлён только от начала списка к концу. Элемент двусвязанного списка хранит адреса как предыдущего, так и следующего элементов списка. Это увеличивает удобство работы со списком, но увеличивает размер каждого элемента.

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

Вектор: более быстрый доступ к элементу; малые расходы памяти на вспомогательные структуры данных. Список: размер ограничен только объёмом доступной виртуальной памяти; более быстрое добавление и удаление элементов (кроме последнего). Эти достоинства и недостатки проявляются сильнее с увеличением числа элементов.

Итератор - указатель на определенный элемент составной структуры данных.

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