[C++]Reverse doubly linked list with sentinel nodes

1. 연결리스트 구현

: 구현 방법 관련한 자세한 설명은 아래 글에

2023.11.29 - [C++/자료구조] - [C++]Doubly linked list with sentinel nodes

[C++]Doubly linked list with sentinel nodes

 

2. 연결리스트 역순으로 

 

• 첫 번째 노드부터 마지막 노드까지 순회
• 해당 노드의 next는 노드의 prev를
• 해당 노드의 prev는 노드의 next를
• 이때, 노드의 next/prev변경하고나면 다음 노드로 순회하지 못하기에 임시로 노드의 next저장하는 노드 포인터 생성
• 다 순회하고나면 head와 tail노드의 각각 next와 prev 업뎃
• 첫번째 노드와 마지막 노드의 prev/next를 head/tail로 업뎃
  (Ⅲ,Ⅳ 과정의 추가로 코드가 조금 복잡해보일 수 있음)

 

 

 

 

 

void reverse() {
	Node* curNode = begin();
	// head 4 5 6 7 tail
	// head 7 6 5 4 tail
	while (curNode != end()) {
		Node* temp_next = curNode->getNext();
		curNode->setNext(curNode->getPrev());
		curNode->setPrev(temp_next);
		curNode = temp_next;
	}
	Node* firstNode = begin();
	Node* lastNode = last();
	head->setNext(lastNode);
	tail->setPrev(firstNode);
	begin()->setPrev(head);
	last()->setNext(tail);
	
}