newPtr

б) firstPtr

newPtr

Рис. 15.5. Выполнение функции insertAtFront

3)Если список пустой, тогда и указатель firstPtr, и указатель lastPtr устанавливаются равными newPtr.

4) Если список не является пустым, тогда узел, на который указывает newPtr, как бы вставляется в начало списка путем копирования указателя firstPtr в указатель newPtr->nextPtr, так что этот новый узел будет теперь указывать в качестве следующего тот, который ранее являлся первым в списке; кроме того, в результате копирования newPtr в указатель firstPtr новое значение firstPtr будет указывать на новый узел как на первый в списке.

Рис. 15.5 иллюстрирует работу функции insertAtFront. Рис. 15.5 а) показывает состояние списка и нового узла до выполнения insertAtFront. Пунктирные стрелки на рис. 15.5 Ь) иллюстрируют шаги 2 и 3 при выполнении функции insertAtFront, которые позволяют узлу, содержащего число 12, стать новым первым узлом списка.

Функция insertAtBack (см. рис. 15.6) помещает новый узел в конец списка. Функция выполняется в несколько шагов:

1) Вызывается функция getNewNode, которой передается value - константная ссылка на значение вставляемого узла.

2) Функция getNewNode использует операцию new для создания нового узла списка и возвращает указатель на этот узел в Ptr. Если этот указатель имеет ненулевое значение, то функция getNewNode возвращает указатель на вновь помещенный узел и передает его в newPtr в функции insertAtBack.

3)Если список пустой, тогда и указатель firstPtr, и указатель lastPtr устанавливаются равными newPtr.

4) Если список не является пустым, тогда узел, на который указывает newPtr, как бы вставляется в конец списка путем копирования указателя newPtr в указатель lastPtr->nextPtr, так что теперь на этот новый узел будет указывать как на следующий тот узел, который ранее был последним в списке; кроме того, в результате копирования newPtr в указатель lastPtr новое значение lastPtr будет указывать на новый узел как на последний в списке.

а>

firstPtr

lastPtr

newPtr

firstPtr

lastPtr

> A

Рис. 15.6. Графическая иллюстрация выполнения функции insertAtBack

Рис. 15.6 иллюстрирует выполнение функции insertAtBack. Рис. 15.6 а) показывает состояние списка и нового узла до выполнения функции insertAtBack. Пунктирные стрелки на рис. 15.6 Ь) иллюстрируют действия функции insertAtBack, которая позволяет добавить новый узел в конец уже заполненного списка.

Функция removeFromFront (см. рис. 15.7) удаляет первый узел списка и копирует значение этого узла в параметр ссылки. Функция возвращает О, если предпринята попытка удаления узла из пустого списка, и возвращает 1, если удаление было успешным. Функция выполняется в несколько шагов:

1) Создается экземпляр указателя tempPtr как копия указателя firstPtr. Указатель tempPtr будет использован для освобождения области памяти удаляемого узла.

2) Если firstPtr равен lastPtr, то есть до начала удаления в списке имелся только один элемент, то указателям firstPtr и lastPtr присваиваются нулевые значения (список становится пустым).

3)Если в списке до начала удаления имелось более одного узла, то указатель lastPtr остается неизменным, а указатель firstPtr устанавливается равным firstPtr->nextPtr, то есть теперь firstPtr указывает на второй узел первоначального списка (теперь этот узел становится первым).

4) После того, как все эти манипуляции с указателями завершены, в параметр ссылку value копируется элемент data удаляемого узла.

5) Операция delete освобождает область памяти, выделенную для узла, на который указывает tempPtr.

6) Возвращается 1, что указывает на успешное удаление.

firstPtr

lastPtr

6) firstPtr

lastPtr

tempPtr

Рис. 15.7. Графическое представление выполнения функции removeFromFront

Рис. 15.7 иллюстрирует выполнение функции removeFromFront. Рис. 15.7 а) показывает состояние списка до удаления. На рис. 15.7 Ь) показаны реализованные операции с указателями.

Функция removeFromBack (см. рис. 15.8) удаляет последний узел списка и копирует значение узла в параметр ссылки. Эта функция возвращает О, если была осуществлена попытка удаления из пустого списка, и возвращает 1, если удаление было успешным. Функция выполняется в несколько шагов:

1) Создается экземпляр указателя tempPtr как копии указателя lastPtr. Указатель tempPtr будет использован для освобождения области памяти удаляемого узла.

2) Если firstPtr равен lastPtr, то есть до начала удаления в списке имелся только один элемент, то указателям firstPtr и lastPtr присваиваются нулевые значения (список становится пустым).

3)Если в списке до начала удаления имелось более одного узла, то создается экземпляр указателя currentPtr как копия указателя firstPtr.

4) Теперь осуществляется просмотр списка с помощью указателя currentPtr, пока он не укажет на узел перед последним узлом. Это делается в цикле while, который осуществляет замену указателя currentPtr на currentPtr>nextPtr до тех пор, пока currentPtr->nextPtr не станет равным lastPtr.

5) Осуществляется копирование currentPtr в lastPtr для того, чтобы убрать последний узел из списка.

6) Указатель currentPtr->nextPtr, т.е. указатель связи в новом последнем узле списка, устанавливается равным нулю.

7) После того, как завершены все манипуляции с указателями, в параметр ссылку value копируется элемент data удаляемого узла.