Массивы и списки

Для начала сосредоточимся на одном списке — например, списке женщин в порядке предпочтений некоторого мужчины. Возможно, для хранения списка из n элементов проще всего воспользоваться массивом A длины n, в котором A[i] содержит i-й элемент списка. Такой массив легко реализуется практически на любом стандартном языке программирования и обладает следующими свойствами.

• Ответ на запрос вида «Какое значение хранится в i-м элементе списка?» можно получить за время O(1), напрямую обратившись к значению A[i].
• Если мы хотим определить, входит ли в список некоторый элемент e (то есть равен ли он A[i] для некоторого i), необходимо последовательно проверить все элементы за время O(n) — при условии, что нам ничего не известно о порядке следования элементов в A.
• Если элементы массива отсортированы в четко определенном порядке (например, по числовым значениям или по алфавиту), тогда принадлежность элемента e списку проверяется за время O(log n) методом бинарного поиска; в алгоритме устойчивых паросочетаний бинарный поиск не используется, но мы вернемся к нему в следующем разделе.

Массив не так хорошо подходит для динамического ведения списка элементов, изменяющихся со временем (например, списка свободных мужчин в алгоритме устойчивых паросочетаний); поскольку мужчины переходят из свободного состояния в состояние помолвки (а возможно, и обратно), список свободных мужчин должен увеличиваться и уменьшаться в процессе выполнения алгоритма. Обычно частое добавление и удаление элементов из списка, реализованного на базе массива, реализуется громоздко и неудобно.

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

Таким образом, в каждом элемента v должен храниться указатель на следующий элемент; если это последний элемент, указателю присваивается null. Также существует указатель First, ссылающийся на первый элемент. Начиная с First    и последовательно переходя по указателям на следующий элемент, пока не будет обнаружен указатель null, можно перебрать все содержимое списка за время, пропорциональное его длине.

Обобщенный способ реализации связанного списка, в котором набор возможных элементов не может быть зафиксирован изначально, основан на создании записи e для каждого элемента, включаемого в список. Такая запись содержит поле e.val, в котором хранится значение элемента, и поле e.Next с указателем на следующий элемент списка.

Также можно создать двусвязный список, поддерживающий переходы в обоих направлениях; для этого добавляется поле e.Prev со ссылкой на предыдущий элемент списка. (Для первого элемента в списке e.Prev = null.) Также добавляется указатель Last — аналог First, указывающий на последний элемент в списке.

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

• Удаление. Чтобы удалить элемент e из двусвязного списка, достаточно «обойти» его так, чтобы предыдущий элемент (на который указывает Prev) и следующий элемент (на который указывает e.Next) указывали друг на друга. Операция удаления изображена на рис. 2.1.
• Вставка. Чтобы вставить элемент e между элементами d и f в списке, мы присваиваем Next и f.Prev указатель на e, а полям Next и Prev в e — указатели на d и f соответственно. Эта операция, по сути, является обратной по отношению к удалению; чтобы понять происходящее, достаточно просмотреть рис. 2.1 снизу вверх.

При вставке или удалении e в начале списка обновляется указатель First — вместо обновления записи элемента, предшествующего e.

Списки хорошо подходят для ведения динамически изменяемых множеств, но у них имеются свои недостатки. В отличие от массивов, i-й элемент списка невозможно найти за время O(1): переход к i-му элементу потребует перехода по указателям Next, начиная от начала списка, что займет в общей сложности время O(i).

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

Такая предварительная обработка часто приносит пользу; и в таком случае преобразование между массивами и списками легко выполняется за время O(n). Это позволит нам свободно выбрать структуру данных, которая лучше подходит для конкретного алгоритма, не привязываясь к той структуре, в которой были получены входные данные.