►Использование связанных списков...176

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

___________

¹⁴Это сделано некорректно; как минимум член 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 указывает на первый член списка, а после второй строки заголовок списка указывает на добавленный элемент, что делает его первым элементом списка.