Circle Double Linked List 구현

원형 이중 연결리스트 구현

• 원형 이중 연결리스트: 첫 노드와 마지막 노드가 이어지는 형태
  

ReversePrint를 할 때, 마지막 노드까지 이동할 필요 없음
head -> prev를 통해 마지막 노드로 이동 가능

Struct Node_{
	int data;
	struct Node_* prev;
	struct Node_* next;
}
typedef struct Node_ Node;

Node head;

int main(){
	head = NULL;
	Insert(2);
	Insert(4);
	Insert(6);
}

---

main을 보자.

int main(){
	head = NULL; //(1)
	Insert(2); //(2)
}

(1)을 실행하고 나면 다음과 같은 형태가 된다.

(2)를 실행한다.

---

insert함수를 자세히 살펴보자.

void Insert(int x){
	Node* tmp = GetNewNode(x);
	if(head == NULL){
		head = tmp;
		tmp -> prev = head;
		tmp -> next = head;
		return;
	}
	head -> prev -> next = tmp;
	tmp -> prev = head -> prev;
	head -> prev = tmp;
	tmp -> next = head; 
}

insert 함수를 한 라인씩 살펴본다.

//insert function
	Node* tmp = GetNewNode(x);

//insert function
	if(head == NULL){
		head = tmp;
		tmp -> prev = head;
		tmp -> next = head;
		return;
	}

head가 NULL이므로 if문에 진입한다.

return한다.

return하며 Insert function에서 선언한 로컬 변수가 사라지며 다음과 같이 마무리된다.

---

//main
	Insert(4);

Insert함수에 파라미터 4를 준다.

void Insert(int x){
	Node* tmp = GetNewNode(x);
	if(head == NULL){
		head = tmp;
		tmp -> prev = head;
		tmp -> next = head;
		return;
	}
	head -> prev -> next = tmp;
	tmp -> prev = head -> prev;
	head -> prev = tmp;
	tmp -> next = head; 
}

다시, insert 함수를 한 라인씩 살펴본다.

//insert function
	Node* tmp = GetNewNode(x);

head가 NULL이 아니므로 if문에 진입하지 않는다.

//insert function
	head -> prev -> next = tmp;

//insert function
	tmp -> prev = head -> prev;

//insert function
	head -> prev = tmp;

//insert function
	tmp -> next = head; 

return되며 Insert함수에서 선언된 로컬 변수가 사라지며 다음과 같은 형태가 된다.

---

//main
	Insert(6);

Insert함수에 파라미터 6를 준다.

void Insert(int x){
	Node* tmp = GetNewNode(x);
	if(head == NULL){
		head = tmp;
		tmp -> prev = head;
		tmp -> next = head;
		return;
	}
	head -> prev -> next = tmp;
	tmp -> prev = head -> prev;
	head -> prev = tmp;
	tmp -> next = head; 
}

다시, insert 함수를 한 라인씩 살펴본다.

//insert function
	Node* tmp = GetNewNode(x);

head가 NULL이 아니므로 if문에 진입하지 않는다.

//insert function
	head -> prev -> next = tmp;

//insert function
	tmp -> prev = head -> prev;

//insert function
	head -> prev = tmp;

//insert function
	tmp -> next = head; 

insert함수를 빠져나오며 아래의 형태로 마무리된다.

---

정리

원형 이중연결리스트
1. 마지막 노드의 next와 생성한 노드의 prev를 연결(노드가 하나일 경우, 자기 자신을 연결)
2. 첫 노드의 prev와 생성한 노드의 next를 연결