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

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

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

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

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

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

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

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

    ptr->next_=front;
    front->prev_=ptr;

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

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

    ...
	void push_front(int val) {
		Node* front=head_->next_;

		Node* ptr=new Node(val);

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

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

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

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

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

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