►Использование связанных списков...176
Связанный список является второй по распространённости структурой после массива. Каждый объект в связанном списке указывает на следующий, образуя цепочку в памяти.
___________
14Это сделано некорректно; как минимум член valFriend не может быть определён в классе того же типа, не считая массы других ошибок. Поэтому к данному примеру следует относиться как к не более чем поясняющей сугубо теоретической модели, которая никогда не будет даже скомпилирована. — Прим. ред.
_________________
176 стр. Часть 3. Введение в классы
К связанному списку легко добавить ещё один элемент — путём изменения указателя в последнем объекте списка. В этом заключается основное преимущество связанного списка — отсутствие необходимости задавать фиксированный размер на этапе компиляции: связанный список может уменьшаться и увеличиваться в зависимости от потребностей программы. Цена этой гибкости — скорость работы со списком, поскольку обратиться к какому-то из элементов списка можно, только пройдя по всем предыдущим.
Не всякий класс может быть использован для создания связанного списка. Связываемый класс объявляется так, как показано в приведённом ниже фрагменте.
class LinkableClass
{
public :
LinkableClass* pNext ;
/* Прочие члены класса */
} ;
Ключевым в этом классе является указатель на объект класса LinkableClass. На первый взгляд несколько необычно выглядит то, что класс содержит указатель сам на себя. В действительности в этом объявлении подразумевается, что каждый объект класса содержит указатель на другой объект этого же класса.
Указатель pNext и есть тот элемент, с помощью которого дети объединяются в цепочки. Фигурально выражаясь, можно сказать, что список детей состоит из некоторого количества объектов, каждый из которых имеет тип "ребёнок". Каждый ребёнок указывает на следующего ребенка.
Головной указатель является указателем типа LinkableClass*, и если использовать аналогию с цепочкой детей, держащихся за руки, то можно сказать, что учитель указывает на объект класса "ребёнок" ( любопытно отметить, что сам учитель не является ребёнком — головной указатель не обязательно должен иметь тип LinkableClass ).
«Не забывайте инициализировать указатели значением 0. Указатель, содержащий нуль, так и называется — нулевым. Обычно попытка обращения по адресу 0 вызывает аварийную остановку программы.»
[Атас!]
«Преобразование целочисленного нуля в тип LinkableClass* не обязательно. С++ воспринимает 0 как значение любого типа ( в частности, как "универсальный указатель" ).»
[Советы]
Чтобы увидеть, как связанные списки работают на практике, рассмотрим следующую функцию, которая добавляет переданный ей аргумент в начало списка.
void addHead( LinkableClass* pLC )
{
pLC -> pNext = pHead
pHead = pLC ;
}
Здесь после выполнения первой строки поле pNext указывает на первый член списка, а после второй строки заголовок списка указывает на добавленный элемент, что делает его первым элементом списка.