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

Добавяне на елемент в края на списъка

Нека с back обозначим указател от типа Node*, който е насочен към последният елемент на списъка.

Node* back=head_->prev_;

Добавянето на елемент в края на списъка означава, че трябва да вмъкнем елемент между елемента back и head_.

Добавяне на елемнт в края на списъка

За добавяне на нов елемент в списъка дефинираме член-функция push_back() на класа List. За удобство функцията дефинира локална променлива back, която е насочена към последният елемент от списъка. След това динамично се заделя памет за нов елемент на списъка, към който се насочва указателят ptr. Така създаденият елемент трябва да се разположи между елементите, към които са насочени указателите back и head_.

Елементът ptr трябва да бъде след елемента back. Следователно:

    back->next_=ptr;
    ptr->prev_=back;

Елементът ptr трябва да бъде преди елемента back. Следователно:

    ptr->next_=back;
    back->prev_=ptr;

Добавяне на елемент в края на списъка

Комбинирайки тези фрагменти от код получаваме целият метод push_back().

    ...
	void push_back(int val) {
		Node* back=head_->prev_;

		Node* ptr=new Node(val);

		back->next_=ptr;
		ptr->prev_=back;

		head_->prev_=ptr;
		ptr->next_=head_;
	}
    ...

[note]Обърнете внимание, че дефинираната по този начин член-функция е коректна и в случая на празен списък. Ако сисъкът е празен, то променливата back ще бъде насочена към водещията елемент back==head_. Това означава, че при добавянето на елемент в празен списък, кодът който ще се изпълни, ще бъде еквивалентен на следното:

	head_->next_=ptr;
	ptr->prev_=head_;

	head_->prev_=ptr;
	ptr->next_=head_;

което е точно необходимият код за добавяне на елемент в празен списък.[/note]