Теоретический раздел

1. Определение списка

Список (англ. list) — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности — кортежа. Экземпляры значений, находящихся в списке, называются элементами списка (англ. item, entry либо element); если значение встречается несколько раз, каждое вхождение считается отдельным элементом.

1.2 Свойства списка

У определённой таким образом структуры данных имеются некоторые свойства:

1. Размер списка — количество элементов в нём, исключая последний «нулевой» элемент, являющийся по определению пустым списком.

2. Тип элементов — тот тип  , над которым строится список; все элементы в списке должны быть этого типа.

3. Отсортированность — список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел).

4. Возможности доступа — некоторые списки в зависимости от реализации могут обеспечивать программиста селекторами для доступа непосредственно к заданному по номеру элементу.

5. Сравниваемость — списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии.

Из вышесказанного следует, что списки используются для хранения наборов однотипных элементов. Такие элементы могут быть отсортированы для использования в функциях поиска или функциях для быстрой вставки новых элементов в список.

1.3 Виды списков

Понятие "списки" включает в себя самые разные структуры данных. Это могут быть и массивы, в том числе массивы записей, и специальные динамические структуры данных, и даже деревья. Общим для них является то, что они содержат набор записей одного вида, ограниченный по размеру или неограниченный, упорядоченный или неупорядоченный. Данные, хранящиеся в этих записях, обычно связаны логически между собой, например, фамилии студентов одной группы и т.п. В тексте программы такая связь может выражаться в том, что все такие элементы хранятся в одном и том же массиве как непрерывном блоке памяти. Но кроме общего имени массива (и адреса его начала) между этими элементами никакой другой физической связи нет, и на физическом уровне подобные списки могут быть названы "несвязными" (или, что (почти) то же самое, "несвязанными"). Иначе говоря внутри них нет связей (их элементы не связаны друг с другом физически).

Типичным примером несвязного (физически) списка является массив.

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

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

По способу организации связей (или по архитектуре) списки могут быть линейными и кольцевыми (циклическими). (Если список не является ни линейным, ни кольцевым, то остаётся единственный вариант – ветвящийся список, фактически являющийся одной из древовидных структур данных.)

По степени упорядоченности хранимых данных списки могут быть упорядоченными и неупорядоченными.