Соображения по поводу эффективности

Соображения по поводу эффективности

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

Использование начального узла

Еще раз просмотрите код вставки и удаления элемента связного списка. Не кажется ли вам неудобным наличие двух случаев для обеих операций? Отдельные специальные случаи нужны для обработки вставки и удаления первого узла - операция, которая, возможно, будет выполняться не очень часто. Может быть, существует другой способ? Другой способ действительно есть, он предусматривает использование фиктивного начального узла. Фиктивный начальный узел - это узел, который нужен только в качестве заполнителя, в нем не будут храниться данные. Первым реальным узлом будет тот, на который указывает указатель Next фиктивного узла. Связный список, как и раньше, заканчивается узлом, указатель Next которого равен nil. При создании такого списка его нужно правильно инициализировать, выделив память под начальный узел и установив его указатель Next равным nil.

var

HeadNode : PSimpleNode;

begin

• • •

New(HeadNode);

HeadNode^.Next := nil;

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

Конечно, введение фиктивного начального узла усложнило реализацию класса: теперь при создании нового связного списка нам нужно распределить и инициализировать дополнительный узел, а при удалении списка - уничтожить этот узел.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

1.4.5. Заключительные соображения по поводу «GNU Coding Standards»

Из книги автора

1.4.5. Заключительные соображения по поводу «GNU Coding Standards» GNU Coding Standards является стоящим для прочтения документом, если вы хотите разрабатывать новое программное обеспечение GNU, обмениваться существующими программами GNU или просто научиться программировать лучше. Принципы


14.2.2.3. Предостережения по поводу блокировок

Из книги автора

14.2.2.3. Предостережения по поводу блокировок Имеется несколько предостережений, о которых нужно знать при блокировках файлов:• Как описано ранее, вспомогательная блокировка является именно этим. Не взаимодействующий процесс может делать все, что хочет, за спиной (так


Комментарии по поводу многопоточных моделей

Из книги автора

Комментарии по поводу многопоточных моделей Для описания методов проектирования многопоточных программ используются такие термины, как пул потоков (thread pool), симметричные потоки (symmetric threads) и асимметричная потоковая организация программ (asymmetric threading), а мы при создании


Замечания по поводу безопасности

Из книги автора

Замечания по поводу безопасности В том виде, как она здесь представлена, данная клиент-серверная система не является безопасной. Если на вашей системе выполняется сервер и кому-то известен номер порта, через который вы работаете, и имя компьютера, то он может атаковать


Дополнительные соображения по оптимизации

Из книги автора

Дополнительные соображения по оптимизации Одним из возможных выходов из сложившейся ситуации будет использование характерных для IE CSS-хаков, чтобы только для него подключить фоновые изображения. В итоге вышеприведенный пример будет выглядеть примерно так:ul {list-style: none;}ul


Соображения производительности

Из книги автора

Соображения производительности Интересны не только затраты на порождение нового процесса (мы еще будем к ним неоднократно возвращаться), но и то, насколько «эффективно» сосуществуют параллельные процессы в ОС, насколько быстро происходит переключение контекста с


1. Общие соображения об анонимности в Интернет

Из книги автора

1. Общие соображения об анонимности в Интернет Человек написал и отправил письмо по электронной почте, посетил какой-то сайт, оставил своё сообщение на форуме и т. д. Любое из указанных действий позволяет найти этого человека и узнать кто он такой. А при желании и привлечь


§ 160. Два соображения

Из книги автора

§ 160. Два соображения 3 июня 2009— Хороший логотип должен быть таким, чтобы любой человек мог его по памяти от руки изобразить.— Это хорошо, если реклама не сразу понятна. Человек потратит время на понимание смысла и лучше запомнит такую рекламу.Из-за этих двух заблуждений


Соображения для преподавателей

Из книги автора

Соображения для преподавателей Было несколько руководящих принципов, которых я старался придерживаться. Я думаю, они делают процесс обучения гораздо более лёгким – ведь учиться программировать и так довольно тяжело. Если вы преподаёте или наставляете кого-то на путь


Важные замечания по поводу циклов For.. .Next

Из книги автора

Важные замечания по поводу циклов For.. .Next Старайтесь, чтобы ваш программный код всегда оставался понятным. Используйте 1 в качестве начального значения для цикла For. . . Next, если только у вас нет серьезных причин выбрать для этого другое число.Такие серьезные причины на


Замечания по поводу платформ STL от Microsoft

Из книги автора

Замечания по поводу платформ STL от Microsoft В начале книги я ввел термин «платформа STL», означающий комбинацию конкретного компилятора и конкретной реализации STL. Различие между компилятором и библиотекой особенно важно при использовании компилятора Microsoft Visual С++ версий 6 и


14.8. Соображения эффективности A

Из книги автора

14.8. Соображения эффективности A В общем случае объект класса эффективнее передавать функции по указателю или по ссылке, нежели по значению. Например, если дана функция с сигнатурой:bool sufficient_funds( Account acct, double );то при каждом ее вызове требуется выполнить почленную


Отборочные соображения

Из книги автора

Отборочные соображения Тайм-аут, в течении которого я отвлёкся от проблем противостояния дистрибутивов, имена которых вынесены в заглавие цикла, подошёл к концу. И пора выполнять своё обещание – подвести окончательные (на сегодняшний день) итоги тому, что было сказано на