[C언어로 쉽게 풀어쓴 자료구조] Chapter7. 연결 리스트 II (1)

7.1 원형 연결 리스트

● 원형 연결 리스트의 소개, 정의, 처음에 삽입, 끝에 삽입

· 원형 리스트: 마지막 노드가 첫 번째 노드를 가리키는 리스트.

- 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소를 가리킨다.

- 하나의 노드에서 모든 노드를 거쳐 자기 자신으로 되돌아올 수 있다.

- 삭제나 삽입 시 선행 노드를 가리키는 포인터를 통해 연산이 용이해진다.

- 특히 리스트의 끝에 노드를 삽입하는 연산 시 모든 노드를 다시 탐색할 필요 없이 헤드 포인터가

마지막 노드를 가리키도록 구성한다.

 

아래는 원형 리스트의 처음에 삽입하는 코드이다.

ListNode* insert_first(ListNode* head, element data){
	ListNode *node = (ListNode*)malloc(sizeof(ListNode));
	node->data=data;
	if(head == NULL){
		head= node;
		node->link = head;
	}
	else{
		node->link = head->link;
		head->link = node;
	}
	return head;
}

 

헤드 포인터가 마지막 노드를 가리킨다는 것만 기억하면 삽입된 노드의 링크가

마지막 노드가 가리키던 링크를 받는다는 것을 쉽게 알 수 있다.

 

 

아래는 원형 리스트의 끝에 삽입하는 코드이다.

ListNode* insert_last(ListNode* head, element data){
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data=data;
	if(head==NULL){
		head= node;
		node->link =head;
	}
	else{
		node->link = head->link;
		head->link = node;
		head = node;
	}
	return head;
}

head = node; 라는 한 줄을 통해 head의 위치만 새로 삽입한 노드로 바꾸어주면

새로 삽입한 노드가 마지막 노드가 되면서 쉽게 구현할 수 있다.

 

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct ListNode{
	element data;
	struct ListNode *link;
}ListNode;

void error(char *message){
	fprintf(stderr,"%s\n",message);
	exit(1);
}

void print_list(ListNode* head){
	ListNode* p;
	if(head ==NULL) return;
	p = head->link;
	do{
		printf("%d-> ",p->data);
		p=p->link;
	}while(p!=head);
	printf("%d-> \n",p->data);
}

ListNode* insert_first(ListNode* head, element data){
	ListNode *node = (ListNode*)malloc(sizeof(ListNode));
	node->data=data;
	if(head == NULL){
		head= node;
		node->link = head;
	}
	else{
		node->link = head->link;
		head->link = node;
	}
	return head;
}

ListNode* insert_last(ListNode* head, element data){
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data=data;
	if(head==NULL){
		head= node;
		node->link =head;
	}
	else{
		node->link = head->link;
		head->link = node;
		head = node;
	}
	return head;
}

int get_length(ListNode *head){ //Quiz 02
	ListNode*p = head;
	int count=1;
	if(p==NULL){
		count =0;
	}
	else{
		while(p->link != head){
			p=p->link;
			count++;
		}
	}
	return count;
}

int main(){
	ListNode *head = NULL;
	
	printf("%d개의 노드가 있습니다\n",get_length(head));
	head = insert_last(head,20);
	print_list(head);
	printf("%d개의 노드가 있습니다\n",get_length(head));
	head = insert_last(head,30);
	print_list(head);
	printf("%d개의 노드가 있습니다\n",get_length(head));
	head = insert_last(head,40);
	print_list(head);
	printf("%d개의 노드가 있습니다\n",get_length(head));
	head = insert_first(head,10);
	print_list(head);
	printf("%d개의 노드가 있습니다\n",get_length(head));
	return 0;
}

 

♠ 227p Quiz

01 삽입과 삭제에 용이하며 하나의 노드에서 다른 모든 노드에 접근 가능하다

02 상단 코드에 get_length 구현

 

7.2 원형 연결 리스트는 어디에 사용될까?

1. 여러 응용 프로그램을 하나의 CPU위에서 실행할 때 사용
2. 멀티 플레이어 게임
3. 원형 큐 구현 - front와 rear를 각각 첫 번째 노드, 마지막 노드를 가리키는 포인터로 사용

● 멀티 플레이어 게임

3명의 플레이어가 돌아가면서 보드 게임을 할 때 순서를 나타내는 코드를 작성한다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char element[100];
typedef struct ListNode{
	element data;
	struct ListNode *link;
}ListNode;



ListNode* insert_first(ListNode* head, element data){
	ListNode *node = (ListNode*)malloc(sizeof(ListNode));
	strcpy(node->data,data);
	if(head == NULL){
		head= node;
		node->link = head;
	}
	else{
		node->link = head->link;
		head->link = node;
	}
	return head;
}



int main(){
	ListNode *head = NULL;
	
	
	head = insert_first(head,"KIM");
	head = insert_first(head,"PARK");
	head = insert_first(head,"CHOI");
	
	ListNode *p = head;
	for(int i=0; i<10; i++){
		printf("현재 차례 = %s \n",p->data);
		p=p->link;
	}
	
	return 0;
}

 

7.3 이중 연결 리스트

● 이중 연결 리스트: 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 모두 가지는 리스트

- 링크가 양방향이므로 특정 노드에서 양방향으로 자유롭게 검색 및 접근이 가능하다.

- 공간을 많이 차지하고 코드가 복잡해진다.

- 헤드 노드(head node)라는 특별한 노드를 추가하여 사용하는 경우가 많다.

이때 헤드 노드는 데이터를 가지고 있지 않는 빈 노드로, 삽입 및 삭제의 용이성을 위해 사용한다.

typedef int element;
typedef struct DListNode{
	element data;
	struct ListNode *llink;
	struct ListNode *rlink;
}DListNode;

이중 연결 노드는 왼쪽 링크 필드(선행 노드), 데이터 필드, 오른쪽 링크 필드(후속 노드)를 가지고,

p=p->llink->rlink = p->rlink->llink

위와 같은 관계가 항상 성립한다.

 

● 삽입연산, 삭제연산, 완전한 프로그램

typedef int element;
typedef struct DListNode{
	element data;
	struct DListNode *llink;
	struct DListNode *rlink;
}DListNode;

void init(DListNode* phead){
	phead->llink = phead;
	phead->rlink = phead;
}

void print_dlist(DListNode* phead){
	DListNode* p;
	for(p = phead->rlink; p != phead; p=p->rlink){
		printf("<-| %d |-> ",p->data);
	}
	printf("\n");
}

void dinsert(DListNode *before,element data){
	DListNode *newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data;
	newnode->llink = before;
	newnode->rlink = before->rlink;
	before->rlink->llink = newnode;
	before->rlink = newnode;
}

void ddelete(DListNode *head, DListNode *removed){
	if(removed == head) return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}

int main(){
	DListNode *head = (DListNode*)malloc(sizeof(DListNode));
	init(head);
	
	printf("추가 단계\n");
	for(int i=0; i<5;i++){
		dinsert(head,i);
		print_dlist(head);
	}
	
	printf("tkrwp 단계\n");
	for(int i=0; i<5;i++){
		print_dlist(head);
		ddelete(head,head->rlink);
	}
	free(head);

	return 0;
}

헤드 노드만 알고 있으면 어떤 노드로도 접근할 수 있게 때문에

단순 연결 리스트처럼 별도의 헤드 포인터가 필요 없다.

 

♠ 236p Quiz

01 삽입과 삭제에 용이

02 헤드 노드의 rlink가 새로운 노드를 새로운 노드의 llink가 헤드 노드를 받는다.

 

7.4 예제: mp3 재생 프로그램 만들기

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char element[100];
typedef struct DListNode{
	element data;
	struct DListNode *llink;
	struct DListNode *rlink;
}DListNode;

DListNode* current;

void init(DListNode* phead){
	phead->llink = phead;
	phead->rlink = phead;
}

void print_dlist(DListNode* phead){
	DListNode* p;
	for(p = phead->rlink; p != phead; p=p->rlink){
		if(p == current){
			printf("<-| #%s# |-> ",p->data);
		}
		else{
			printf("<-| %s |-> ", p->data);
		}
	}
	printf("\n");
}

void dinsert(DListNode *before,element data){
	DListNode *newnode = (DListNode*)malloc(sizeof(DListNode));
	strcpy(newnode->data,data);
	newnode->llink = before;
	newnode->rlink = before->rlink;
	before->rlink->llink = newnode;
	before->rlink = newnode;
}

void ddelete(DListNode *head, DListNode *removed){
	if(removed == head) return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}

int main(){
	DListNode *head = (DListNode*)malloc(sizeof(DListNode));
	init(head);
	
	char ch;
	dinsert(head,"Mamamia");
	dinsert(head,"Dancing Queen");
	dinsert(head,"Fernando");
	
	current = head->rlink;
	print_dlist(head);
	
	do{
		printf("\n명령어를 입력하시오(<,>,q): ");
		ch = getchar();
		if(ch =='<'){
			current = current ->llink;
			if(current ==head) current=current->llink;
		}
		else if(ch =='>'){
			current = current ->rlink;
			if(current ==head) current=current->rlink;	
		}
		print_dlist(head);
		getchar();
	} while(ch != 'q');
	
	free(head);

	return 0;
}