8-4장 원형 이중 연결 리스트

1. 원형 리스트 알아보기 

 

원형 리스트 (circular list)

 

- 선형 리스트의 꼬리 노드가 머리 노드를 가리킴

- 꼬리 노드의 다음 노드를 가리키는 포인터가 머리 노드의 포인터 값

 

 

- 빈 원형 리스트 

//원형 리스트가 비어 있는지 확인
list->head == NULL;

- 노드가 1개인 원형 리스트 

//노드가 1개 인지 확인 
list->head->next == list->head

- 포인터가 머리 노드를 가리킴 

//p가 가리키는 노드가 머리 노드인지 확인 
p == list->head

- 포인터가 꼬리 노드를 가리킴

//p가 가리키는 노드가 꼬리 노드인지 
p->next == list->head

 

2. 이중 연결 리스트 알아보기 

 

이중 연결 리스트 (doubly linked list)

 

- 양방향 리스트 

- 각 노드에는 다음 노드에 대한 포인터 (next)와 앞쪽 노드에 대한 포인터(prev)를 가짐 

- 포인터가 머리노드를 가리킴

//p가 가리키는 노드가 머리노드인지 확인
p == list->head
p->prev == NULL

- 포인터가 꼬리노드를 가리킴

p->next == NULL

 

 

3. 원형 이중 연결 리스트 만들기 

 

원형 이중 연결 리스트 (circular doubly linked list)

 

- 원형 리스트 + 연결 리스트 

 

 

- 노드를 나타내는 구조체 Dnode

- 원형 이중 연결 리스트를 관리하는 구조체 Dlist

//노드 
typedef struct __node {
	Member data; //데이터 
	struct __node *prev; //앞쪽 노드에 대한 포인터 
	struct __node *next; //뒤쪽 노드에 대한 포인터  
}Dnode; 

//연결 리스트 
typedef struct {
	Dnode *head; //머리의 더미 노드에 대한 포인터 
	Dnode *crnt; // 선택한 노드에 대한 포인터 	
}Dlist;

 

4. 노드를 생성하는 AllocDnode 함수 

 

- Dnode형 객체를 생성하고 해당 객체의 포인터를 반환

//1개의 노드를 동적으로 생성
static Dnode *AllocDNode (void) 
{
	return (Dnode*)calloc(1,sizeof(Dnode));
}

 

5. 노드의 멤버값을 설정하는 SetDnode 함수 

 

- Dnode형 객체의 멤버값을 설정

- 첫 번째 매개변수 n에 전달받은 Dnode형 객체 포인터를 통해 멤버값 설정

//노드의 각 멤버값을 설정
static void SetDNode(Dnode *n, const Member *x, const Dnode *prev, const Dnode *next) 
{
	n->data = *x; //데이터
	n->prev = (Dnode*)prev; //앞쪽 노드에 대한 포인터 
	n->next = (Dnode*)next; //다음 노드에 대한 포인터  
}

 

6. 원형 이중 연결 리스트를 초기화 하는 Initialize 함수 

 

- 텅 비어 있는 상태의 원형 이중 리스트를 만드는 함수 

- 리스트의 머리 부분에 더미 노드가 만들어짐

 

더미 노드만 있는 상태 

 1) 머리 포인터 list->head가 가리키는 대상

 2) 더미 노드의 앞쪽 포인터 list->head->prev가 가리키는 대상

 3) 더미 노드의 뒤쪽 포인터 list->head->next가 가리키는 대상

이 모두 더미 노드를 가리키는 상황

 

//리스트를 초기화(더미 노드만 있는 상태) 
void Initialize(Dlist *list) 
{
	Dnode *dummyNode = AllocDNode(); //더미 노드 생성
	list->head = list->crnt = dummyNode;
	dummyNode->prev = dummyNode -> next = dummyNode;
}

 

7. 리스트가 비어 있는지 검사하는 IsEmpty 함수 

 

- 더미 노드의 뒤쪽 포인터 list->head->next가 자신의 더미 노드인 list->head를 가리키는지 판단

- 비어 있는 경우 1

//리스트가 비어 있는지 검사 
static int IsEmpty(const Dlist *list) 
{
	return list->head->next == list->head;
}

 

8. 선택한 노드의 데이터를 출력하는 PrintCurrent / PrintLnCurrent 함수 

 

- list->crnt가 가리키는 노드의 데이터를 출력

//선택한 노드의 데이터를 출력
void PrintCurrent (const Dlist *list) 
{
	if(IsEmpty(list))
		printf("선택한 노드가 없습니다.");
	else
		PrintMember(&list->crnt->data);		
}

//선택한 노드의 데이터를 출력 (줄바꿈 문자)
void PrintLnCurrent (const Dlist *list) 
{
	PrintCurrent(list);
	putchar('\n');
}

 

9. 노드를 검색하는 Search 함수 

 

- 리스트에서 노드를 선형 검색

- 머리 노드부터 뒤쪽 포인터를 이용해 순서대로 스캔 

- 머리노드는 더미노드가 아니라 더미노드의 다음 노드 (list->head->next)

- compare 함수로 비교한 결과가 0이면 검색 성공 -> 찾은 노드의 포인터 반환

//compare 함수로 x와 일치하는 노드를 검색
Dnode *Search(Dlist *list, const Member *x, int compare(const Member *x, const Member *y)) 
{
	Dnode *ptr = list->head->next;
	while(ptr != list->head){	
		if(compare(&ptr->data,x)==0) { //검색 성공  
			
			list->crnt = ptr;
			return ptr;
		}
		ptr = ptr->next;
	}
	return NULL; //검색 실패  
	
}

 

10. 모든 노드를 순서대로 출력하는 Print 함수 

 

- 리스트의 모든 노드를 머리부터 순서대로 출력

- list->head->next부터 스캔하기 시작해 뒤쪽 포인터를 찾아가며 각 노드의 데이터 출력

//모든 노드의 데이터를 리스트 순서대로 출력
void Print(const Dlist *list)
{
	if(IsEmpty(list))
		puts("노드가 없습니다.");
	else {
		Dnode *ptr = list->head->next;
		puts("[모두보기]");
		while(ptr != list->head) {
			PrintMember(&ptr->data);
			ptr = ptr->next; //다음 노드 선택  
		}
   }
}

 

11. 모든 노드를 거꾸로 출력하는 PrintReverse 함수 

 

- 리스트의 모든 노드를 꼬리부터 거꾸로 출력

- list->head->prev부터 스캔하기 시작해 앞쪽 포인터를 찾아가며 각 노드의 데이터를 출력

//모든 노드의 데이터를 리스트 순서의 역순으로 출력
void PrintReverse(const Dlist *list) 
{
	if(IsEmpty(list))
		puts("노드가 없습니다.");
	else {
		Dnode* ptr = list->head->prev;
		puts("[모두보기]");
		while(ptr != list->head) {
			PrintMember(&ptr->data);
			ptr = ptr->prev; //앞쪽 노드 선택  
		}
	}
}

 

12. 선택한 노드의 다음으로 진행시키는 Next 함수 

 

- 리스트가 비어 있지 않고 선택한 노드의 다음 노드가 있는 경우에만 동작

- 성공 하면 1 반환

//선택한 노드를 다음으로 진행
int Next(Dlist * list)
{
	if(IsEmpty(list) || list->crnt->next == list->head)
		return 0;
	list->crnt = list->crnt->next;
	return 1;
}

 

13. 선택한 노드의 앞쪽으로 진행시키는 Prev 함수 

 

- 리스트가 비어 있지 않고 선택한 노드의 다음 노드가 있는 경우에만 동작

- 성공하면 1 반환

//선택한 노드를 앞쪽으로 진행
int Prev(Dlist * list) 
{
	if(IsEmpty(list) || list->crnt->prev == list->head)
	  return 0;
	list->crnt = list->crnt->prev;
	return 1;
}

 

14. 바로 다음에 노드를 삽입하는 InsertAfter 함수 

 

- 포인터 p가 가리키는 노드의 바로 다음에 노드 삽입

1) 

- 새로 삽입할 노드 D를 만듬

- 만든 노드의 앞쪽 포인터가 가리키는 노드는 B, 뒤쪽 포인터가 가리키는 노드는 C로 설정

 

2)

- 노드 B의 뒤쪽 포인터 p->next와 노드 C의 앞쪽 포인터 p->next->prev 모두 새로 삽입한 노드를 가리키도록 업데이트 

 

3)

- 선택한 포인터 list->crnt가 삽입한 노드를 가리키도록 업데이트 

//p가 가리키는 노드 바로 다음 노드를 삽입
void InsertAfter(Dlist *list, Dnode *p, const Member *x) 
{
	Dnode *ptr = AllocDNode();
	Dnode *nxt = p->next;
	p->next = p->next->prev = ptr;
	SetDNode(ptr,x,p,nxt);
	list->crnt = ptr; //현재 노드가 삽입한 노드를 가리키도록  
}

 

15. 머리에 노드를 삽입하는 InsertFront 함수 

 

- InsertAfter 함수를 사용해 list->head가 가리키는 더미 노드 뒤에 삽입

//머리에 노드를 삽입
void InsertFront(Dlist *list, const Member* x) 
{
	InsertAfter(list,list->head,x);
}

 

16. 꼬리에 노드를 삽입하는 InsertRear 함수 

 

- 꼬리 노드의 바로 뒤 == 더미 노드의 바로 앞

- InsertAfter 함수를 사용해 list->head->prev가 가리키는 꼬리 노드뒤에 노드 삽입

//꼬리에 노드를 삽입
void InsertRear(Dlist *list, const Member* x) 
{
	InsertAfter(list,list->head->prev,x);
}

 

17. 노드를 삭제하는 Remove 함수 

 

- p가 가리키는 노드를 삭제 

 

 

1)

- 노드 A의 뒤쪽 포인터 p->prev->next가 가리키는 노드가 C(p->next)가 되도록 업데이트 

 

2)

- 노드 C의 앞쪽 포인터 p->next->prev가 가리키는 노드가 A(p->prev)가 되도록 업데이트 

- p가 가리키는 메모리 영역 해제 

 

3)

- 선택한 노드가 삭제한 노드의 앞쪽 노드 A를 가리킬 수 있도록 crnt를 업데이트 

//p가 가리키는 노드를 삭제 
void Remove(Dlist* list, Dnode *p) 
{
	p->prev->next = p->next;
	p->next->prev = p->prev;
	list->crnt = p->prev; //삭제한 노드의 앞쪽 노드를 선택
	free(p);
	if(list->crnt == list->head) 
		list->crnt = list->head->next;
}

 

18. 머리 노드를 삭제하는 RemoveFront 함수 

 

- Remove함수를 사용해 list->head->next)가 가리키는 머리 노드 삭제 

//머리 노드를 삭제
void RemoveFront(Dlist * list) 
{
	if(!IsEmpty(list))
		Remove(list,list->head->next);
}

 

19. 꼬리 노드를 삭제 하는 RemoveRear 함수 

 

- Remove함수를 사용해 list->head->prev가 가리키는 꼬리 노드 삭제 

//꼬리  노드를 삭제
void Removerear(Dlist * list) 
{
	if(!IsEmpty(list))
		Remove(list,list->head->prev);
}

 

20. 선택한 노드를 삭제하는 RemoveCurrent 함수 

 

- Remove 함수를 사용해 list->crnt가 가리키는 선택 노드 삭제 

//선택한 노드를 삭제 
void RemoveCurrent(Dlist *list)
{
	if(!IsEmpty(list))
		Remove(list,list->crnt);
 }

 

21. 모든 노드를 삭제하는 Clear 함수 

 

- 더미 노드를 제외하고 모든 노드를 삭제

//모든 노드를 삭제 
 void Clear(Dlist *list) 
 {
 	while(!IsEmpty(list)) //텅빌때 까지  
 		RemoveFront(list); //머리 노드 삭제  
 }

 

22. 원형 이중 연결 리스트를 종료하는 Terminate 함수 

 

- Clear함수를 호출해 모든 노드 삭제

- 더미 노드의 메모리 영역 해제 

//원형 이중 연결 리스트 종료 
 void Terminate(Dlist *list) 
 {
 	Clear(list); //모든 노드를 삭제 
	free(list->head); //더미 노드를 삭제  
 }