Класс итераторов для односвязных списков

После того, как мы написали классы узла и непосредственно списка, нужно добавить класс итераторов. Итераторы используются для перемещения по списку. Концепция итераторов широко распространена и используется со многими структурами данных.

class SListIterator
{
public:
  SListNode* node;
  SLinkedList* list;
};

В классе две переменные: указатель на текущий узел списка и указатель на сам список. Указатель на список используется, чтобы определить, к какому списку принадлежит данный итератор.

Методы класса итераторов

Все методы класса чрезвычайно просты.

Класс Iterator содержит конструктор с двумя аргументами.

SListIterator(SListNode*,SLinkedList*);

SListIterator::SListIterator(SListNode* n, SLinkedList* l)
{
  node = n;
  list = l;
}

В конструктор передаются указатели на узел и список. Заполняются соответствующие поля.

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

void Start();

void SListIterator::Start()
{
  node = list->head;
}

Тут всё просто, полю node мы присваиваем поле head переменной list. Здесь и list, и node являются членами класса Iterator.

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

void Forward();

void SListIterator::Forward()
{
if (node != NULL)
  node = node->next;
}

Обратите внимание на проверку условия. Мы можем продвинуть итератор вперёд на один узел дальше узла tail списка. Этот узел содержит значение NULL.

Следующая функция возвращает значение текущего узла.

int& Item();

int& SListIterator::Item()
{
  return node->data;
}

Метод возвращает значение по ссылке.

И последняя функция итератора проверяет его значение. Если в итераторе содержится NULL (список закончился или в нём нет элементов), то функция вернёт 0. Если в итераторе содержится корректное значение, то функция вернёт 1.

bool Valid();

bool SListIterator::Valid()
{
  return (node != NULL);
}

Теперь перепишем программу. Итератор может добавлять значение, обращаясь к своему полю node. Кроме того, теперь очень легко вывести все элементы списка.

SLinkedList list;

list.PushBack(5);
list.PushBack(6);
list.PushBack(7);
list.PushFront(3);
list.PushFront(2);

SListIterator itr(list.head, &list);

itr.Forward();
itr.node->InsertAfter(4);

for (itr.Start(); itr.Valid(); itr.Forward())
{
  cout << itr.Item() << ", ":
}

Вывод:

2, 3, 4, 5, 6, 7,
Хотя, с помощью итераторов и можно добавлять узлы к списку (метод InsertAfter класса SListNode), делается это чудовищно криво. Если итератор указывает на последний узел, и мы вызываем функцию InsertAfter, то список испортится, так как в InsertAfter никак не обрабатывается проверка tail списка. Поэтому для итераторов более правильным решением будет написать собственную функцию. Причём лучше эту функцию сделать не для итераторов а для списков, а итераторы можно передавать в функцию в виде аргументов:

void SLinkedList::Insert(SListIterator&, int);

void Insert( SListIterator& itr, int d)
{
  if (itr.Valid())
  {
    itr.node->InsertAfter(d);
    if (itr.node == tail)
    {
      tail = itr.node->next;
    }
    count++;
  }
}

Мы делаем проверку, на что указывает итератор. Если он указывает на NULL, то ничего не происходит. Если же в итераторе содержится корректное значение, то мы добавляем узел с помощью функции InsertAfter. И теперь нужно проверить, если мы добавили узел после последнего, нужно передвинуть tail.

И последняя функция которую мы рассмотрим: функция удаления узла из связного списка:

void Remove(SListIterator&);

void SLinkedList::Remove(SListIterator& itr)
{
  SListNode* temp = head;

  if (itr.node == head)
  {
    itr.Forward();
    PopFront();
  }
  else
  {
    while (temp->next != itr.node)
      temp = temp->next;

    itr.Forward();
    if (temp->next == tail)
      tail = temp;

    delete temp->next;
    temp->next = itr.node;
  }
  count--;
}

Данный метод похож на метод удаления последнего элемента списка, здесь также используется временная переменная для хранения указателя на элемент списка.
Двусвязные (двунаправленные) списки

В двусвязных списках (doubly linked list) к узлам добавляется ещё один указатель - на предыдущий узел. Это существенно повышает гибкость структуры данных по сравнению с односвязными списками.

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

В узле двусвязного списка содержатся два указателя. Помимо указателя на следующий узел, есть указатель и на предыдущий. Это резко увеличивает функциональность двусвязного списка по сравнению с односвязным.

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

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

Пожалуйста, внимательно изучите все классы представленные в файле. Именно на основе этой реализации списков в дальнейшем будут создаваться многие структуры данных. Я постарался как можно сильнее упростить код (в коде почти нет комментариев, и так всё понятно), надеюсь, получилось. Кроме того, обязательно выполните упражнения для двусвязных списков.

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

Ещё один вид списков (частный случай двусвязного списка) - замкнутый или ещё встерачающееся название - кольцевой или закольцованный список. Это, кстати, наиболее полезный и часто встречающийся вариант связных списков. При этом у последнего элемента списка в поле next хранится head, а у первого элемента в поле previous - tail.

Заключение.

Ну, вот в общем-то, по спискам и всё. Несколько заключительных слов:

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

Также можно без проблем изменить размер списков, добавив/удавлив новые узлы.

У списков есть конечно же и слабые стороны. Получить доступ к какому-либо элементу не так просто. Необходимо пройти до этого элемента от начала списка, в то время как в массивах доступ к любому элементу можно получить с помощью индекса.

Кроме того, для хранения списков требуется больше памяти.

В списках удобно хранить объекты больших сложных классов. Если у вас множество мелких объектов, будет эффективнее сохнанить их в массиве. Кроме того, доступ к элементам списков происходит медленнее чем к элементам массива, так как узлы списков хранятся в разных участках памяти.

Мы ещё вернёмся к связным спискам когда будем рассматривать создание игрового ландшафта на основе клеток.

На сегодня всё.

Упражнения (односвязные списки):

1. Для односвязного списка реализуйте интерфейс взаимодействия с пользователем. Примерно как на картинке:

Пользователь вводит какую-нибудь команду, и программа должна корректно обработать эту команду.

Во время выполнения программы, загляните в отладчик и понаблюдайте значения переменных, хранящих список и итераторы.

Во время написания данной программы вы увидите все слабости данной реализации односвязных списков. Откровенно говоря, данная реализация написана довольно паршиво.