Списки
По своей встречаемости в типичных программах списки занимают второе место после массивов. Многие языки имеют встроенные типы списков, некоторые, такие как Lisp, даже построены на них, но в языке С мы должны конструировать их самостоятельно. В C++ и Java работа со списками поддерживается стандартными библиотеками, но и в этом случае нужно знать их возможности и типичные применения. В данном параграфе мы собираемся обсудить использование списков в С, но уроки из этого обсуждения можно извлечь и для более широкого применения.
Простым цепным списком (single-linked list) называется последовательность элементов, каждый из которых содержит данные и указатель на следующий элемент. Головой списка является указатель на первый элемент, а конец помечен нулевым указателем. Ниже показан список из четырех элементов:
Есть несколько важных различий между массивами и списками. Во-первых, размер массивов фиксирован, а список всегда имеет именно такой размер, который нужен для хранения содержимого, плюс некоторое дополнительное место для указателей на каждый элемент. Во-вторых, списки можно перестраивать, изменяя несколько указателей, что дешевле, чем копирование блоков, необходимое при использовании массива. Наконец, при удалении или вставке элементов остальные элементы не перемещаются; если мы будем хранить указатели на отдельные элементы в другой структуре данных, то при изменениях в списке они останутся корректными.
Эти различия подсказывают, что если набор данных будет часто меняться, особенно при непредсказуемом количестве элементов, то нужно использовать список; напротив, массив больше подходит для относительно статичных данных.
Фундаментальных операций со списком совсем немного: добавить элемент в начало или конец списка, найти указанный элемент, добавить новый элемент до или после указанного элемента и, возможно, удалить элемент. Простота списков позволяет при необходимости легко добавлять новые операции.
Вместо того чтобы определить специальный тип List, обычно в С начинают определение списка с описания типа для элементов, вроде нашего Nameval, и добавляют в него указатель на следующий элемент:
Инициализировать непустой список во время компиляции трудно, поэтому списки, не в пример массивам, создаются динамически. Для начала нам нужен способ создания элемента. Наиболее простой подход – выделить под него память специальной функцией, которую мы назвали newitem:
Функцию emalloc мы будем использовать и далее во всей книге; она вызывает mallос, а при ошибке выделения памяти выводит сообщение и завершает программу. Мы представим код этой функции в главе 4, а пока считайте, что эта функция всегда корректно и без сбоев выделяет память.