CPP-101: Двусвързан списък с водещ елемент

Клас List. Конструктор

За реализация на двусвързан списък с водещ елемент дефинираме клас List, който съдържа член променлива head_ от типа Node*. Тази член-променлива е насочена към водещият елемент на списъка. Водещият елемент е фиктивен елемент на списъка, който не е асоцииран с определени данни.

class List {
	struct Node {
		Node* next_;
		Node* prev_;
		int data_;

		Node(int val) :
			next_(0), prev_(0), data_(val)
		{}
	};

	Node* head_;

public:
    ...
};

[note]Обърнете внимание, че структурата Node е дефинирана като вътрешна струкура в скритата част на класа List. Това прави типа Node недостъпен извън класа List и неговите приятели.[/note]

На фигурата е изобразен списък с три елемента [latex]d_1[/latex], [latex]d_2[/latex], [latex]d_3[/latex]. Член-променливата head_ на списъка е насочена към фиктивният елемент.

Двусвързан списък

Конструкторът на класа List заделя памет за водещият елемент head_ и инициализира указателите next_ и prev_ така, че да сочат към самият водещ елемент.

class List {
    ...
public:
	List() : head_(new Node(0)) {
		head_->next_ = head_->prev_ = head_;
	}
    ...
};

Празен списък

Нека добавим и метод empty() към класа List. Този метод връща true когато списъкът е празен. Условието, което е изпълнено, когато списъкът е празен е, че указателите head_, head_->next_ и head_->prev_ имат еднакви стойности. За целите на метода е достатъчно да направим само една от възможните проверки, например:

class List {
    ...
public:
    ...
	bool empty() const {
		return head_==head_->next_;
	}
	...
};