Класс односвязного списка sLinkedList

class SLinkedList

{

public:

SListNode* head; // первый элемент списка

SListNode* tail; // последний элемент списка

int count;

};

В списке будет хранится три переменные. Два указателя на узлы: на первый (head) и на последний (tail) и переменная целого типа count, в которой будет храниться количество элементов (узлов) связного списка.

Конструктор односвязного списка

Конструктор списка в нашей реализации довольно прост:

SLinkedList();

SLinkedList::SLinkedList () : count(0), head(NULL), tail(NULL)

{}

Здесь полям класса присваиваются инициализирующие значения. count - 0, а head и tail - NULL.

Деструктор списка

В данном примере у нас впервые возникает потребность в деструкторе класса. Деструктор класса - это функция вызываемая при уничтожении класса. Также как и конструктор, деструктор не нужно вызывать явно. Имя деструктора совпадает с именем класса (а соответсвенно и с именем конструктора), но перед именем стоит знак тильда ~ (обычно расположен на месте буквы ё в английской расскладке):

~SLinkedList();

SLinkedList::~SLinkedList()

{

SListNode* delNode = head;

SListNode* temp;

while (delNode != NULL)

{

temp = delNode->next;

delete delNode;

delNode = temp;

}

}

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

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

В цикле идёт проверка значения текущего элемента списка. Если в укзателе содержится NULL, значит список кончился.

Если в списке ещё есть узлы, то мы сохраняем указатель на следующий узел во временном узле temp. Затем удаляем текущий узел операцией delete. Теперь мы не можем указать на следующий узел с помощью текущего узла:

delNode->next; // этот код не работает!!!

Память выделенную под delNode мы уже отпустили, а указатель теперь указывает на совершенно другую область памяти. Именно для этого нам и нужна была вспомогательная переменная temp. Если бы её не было, мы бы потеряли все следующие узлы. Теперь указателю delNode присваивается next и в следующей итерации цикла всё повторяется.

Метод добавления элемента в конец списка

void PushBack (int);

void SLinkedList::PushBack (int d)

{

if (count == 0) // В списке нет элементов.

{

head = tail = new SListNode;

head->data = d;

}

else // В списке есть хотя бы один элемент

{

tail->InsertAfter(d);

tail = tail->next;

}

count++;

}

При добавлении узла в конец списка, возможны два варианта: в списке совсем нет элементов или в списке есть хотя бы один элемент. Эти условия мы проверяем с помощью поля count, хранящей количество элементов списка.

Так вот, если в списке нет элементов, то мы создаём новый узел, а указателям tail и head присваиваем адрес этого элемента.

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

Конечно же, в функции PushBack нужно не забыть увеличить переменную count, так как количество узлов увеличилось.

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

Метод добавления узлов в начало связного списка

void PushFront (int);

void SLinkedList::PushFront (int d)

{

if (count == 0)

{

head = tail = new SListNode;

head->data = d;

}

else

{

SListNode* new_node = new SListNode;

new_node->data = d;

new_node->next = head;

head = new_node;

}

count++;

}

Также как и в функции PushBack, здесь возможны два варианта: список пустой или в списке уже есть хотя бы один узел.

В случае если список пуст, мы делаем то же самое, что и в функции PushBack.

Если же в списке есть элементы, мы создаём новый узел. Полю next нового узла присваиваем head. А затем меняем значение head, чтобы он указывал на новый узел.

Теперь наш список умеет добавлять узлы в конец и в начало. Кроме того, список корректно уничтожается с помощью деструктора. Неплохо было бы иметь возможность удалять узлы из списка во время выполнения програмы. В рамках класса SLinkedLIst мы можем удалить элементы из начала и из конца. Удаление элементов из середины, в данном классе реализовать невозможно. Поэтому удаление элементов из середины списка мы рассмотрим позже, когда будем рассматривать итераторы. А сейчас: