Библиотеки qt и stl. Иерархия объектов, коллекция, итераторы

Приложение 2. Односвязный линейный список на базе классов ООП
Структура односвязного линейного списка:

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

• 
  Инициализация списка
  
• 
  Добавление узла в список
  
• 
  Удаление узла из списка
  
• 
  Вывод элементов списка
  
• 
  Взаимообмен двух узлов списка
  

Кроме того, можно выделить ряд вспомогательных методов:

• 
  Переход к следующему узлу
  
• 
  Очистка списка
  
• 
  Проверка, пуст ли список
  
• 
  Получение количества элементов в списке
  
• 
  Получение корня списка
  
• 
  Получение последнего элемента списка
  
• 
  Получение значения элемента списка
  
• 
  Установка значения элемента списка
  

Рассмотрим реализацию односвязного линейного списка на базе классов объектно-ориентированного программирования.

Узел списка представляет собой класс, содержащий два обязательных (private) поля — значение и указатель на следующий элемент. Чтобы позволить списку иметь доступ к скрытым полям узла, объявим класс список как дружественный.

Узел является составной частью класса, который также реализует все интерфейсные методы списка, перечисленные выше.

Для добавления необходимо рассмотреть два случая:

• 
  Добавление узла после указанного
  

• 
  Добавление узла в начало списка
  

Рассмотрим метод добавления элемента в список. Метод принимает в качестве аргумента текущий узел со значением по умолчанию, равным NULL. Если узел не передается, добавление нового узла происходит в начало списка.

Для удаления узла также необходимо рассмотреть две ситуации:

• 
  Удаление промежуточного узла
  

• 
  Удаление корневого узла
  

Перемещение к следующему и к предыдущему узлу

Перемещение к предыдущему узлу не является интерфейсным методом, поэтому находится в области видимости private.

Получение последнего узла списка.

Очистка списка

Вывод значений узлов списка

В качестве примера использования ОЛС рассмотрим следующую задачу: создать список из 10 элементов, удалить все элементы, равные нулю: