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

Има множество различни начини за реализация на двусвързан списък. Ще разгледаме реализация на двусвързан списък с (фиктивен) водещ елемент.

Наличието на фиктивен водещ елемент макар на пръв поглед да изглежда като усложнение, всъщност води до опростяване на кода и по-елегантно дефиниране на итератор за списъка.

Елементи на двусвързан списък

За представяне на елементите на двъсвързан списък се използва структура, която съдържа:

• поле next_ от тип указател към структурата, което е насочено към предходният елемент;
• поле prev_ от тип указател към структурата, което е насочено към следващият елемент;
• поле data_, в което се съхраняват данните, асоциирани с даденият елемент на списъка.

Нека приемем, че разработваният от нас списък ще съдържа елементи от тип int. Тогава структурата, дефинираща елементите на списъка е:

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

    ...
};

При създаване на структура от типа Node полето data_ се инициализира със стойността на елемента, а указателите next_ и prev_ с нулева стойност. За тази цел се дефинира констурктор на структурата:

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