Использование начального узла
Еще раз просмотрите код вставки и удаления элемента связного списка. Не кажется ли вам неудобным наличие двух случаев для обеих операций? Отдельные специальные случаи нужны для обработки вставки и удаления первого узла - операция, которая, возможно, будет выполняться не очень часто. Может быть, существует другой способ? Другой способ действительно есть, он предусматривает использование фиктивного начального узла. Фиктивный начальный узел - это узел, который нужен только в качестве заполнителя, в нем не будут храниться данные. Первым реальным узлом будет тот, на который указывает указатель Next фиктивного узла. Связный список, как и раньше, заканчивается узлом, указатель Next которого равен nil. При создании такого списка его нужно правильно инициализировать, выделив память под начальный узел и установив его указатель Next равным nil.
var
HeadNode : PSimpleNode;
begin
• • •
New(HeadNode);
HeadNode^.Next := nil;
После этой небольшой подготовительной части все вставки и удаления можно будет выполнять с помощью операций "вставить после" и "удалить после". Операция "вставить после первого узла" сводится к вставке нового элемента после фиктивного узла, а операция "удалить первый узел" превращается в удаление элемента после начального узла. За счет использования фиктивного начального узла нам удалось избежать специальных случаев.
Конечно, введение фиктивного начального узла усложнило реализацию класса: теперь при создании нового связного списка нам нужно распределить и инициализировать дополнительный узел, а при удалении списка - уничтожить этот узел.
Использование диспетчера узлов
Перед написанием класса связного списка нужно рассмотреть еще один вопрос. Мы начали с того, что объявили тип узла как запись (тип TSimpleNode), в которой хранятся (1) данные и (2) указатель на следующий узел списка. Второе поле записи удалить нельзя - оно требуется для организации связного списка. Но первое зависит от приложения или конкретного использования списка в данный момент. Фактически поле данных может представлять собой не одно, а несколько полей в отдельной записи или даже объект. Очень сложно написать общий класс связного списка, если неизвестен тип данных, который будет в нем содержаться.
Однако решение этой задачи существует, даже целых два. Первое - объявить класс родительского узла, который бы содержал только указатель Next, а пользователь сам в дочернем классе объявит элементы, содержащие данные узла. В таком случае реализация базового класса будет распределять и освобождать память для узла, поскольку все, что нужно для организации связного списка - это выделенные узлы, указателями Next которых можно манипулировать. Такое решение одновременно является как элегантным, так и неэлегантным. Оно соответствует парадигме объектно-ориентированного программирования, но для хранения данных приходится объявлять дочерний класс (а что если элементы, которые необходимо поместить в список, являются экземплярами класса, над которым вы не имеете контроля?).
