자료구조_07.연결리스트(원형 연결 리스트)

원형 연결 리스트

원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트이다.

단순 연결 리스트와 원형 연결 리스트의 차이점을 알아보자.

연결 리스트 종류

위 그림의 단순 연결 리스트를 보면 마지막 노드는 다음 연결할 노드가 없어 NULL값을 가지고 있지만, 원형 연결 리스트의 경우 마지막 노드가 첫번째 노드를 가리키면서 순환하는 모습을 볼 수 있다.

더 구체적으로 얘기하면 단순 연결 리스트의 마지막 노드의 링크는 NULL값을 가지고 있지만, 원형 연결 리스트의 마지막 노드의 링크는 첫번째 노드를 가리키고 있다.

 

예시로 지하철 4호선과 2호선 순환내선을 들 수 있다.

4호선은 단순 연결 리스트이다.

오이도를 head라고 했을 때,

오이도 -> 정왕 -> 신길온천 -> ... -> 창동 ->상계 -> 당고개

으로 오이도에서 시작해 당고개로 끝나고 당고개가 종착역. 즉, 당고개의 다음은 NULL이라고 할 수 있다.

2호선은 원형 연결 리스트이다.

순환내선의 신도림역을 head라고 했을 때,

신도림 ->대림 ->구로디지털단지 ->.... ->성수 -> 뚝섬 -> ... -> 당산 -> 영등포구청 -> 문래 -> 신도림

으로 신도림에서 시작해 영등포구청을 건너 다시 신도림으로 오는 것처럼 원형으로 이어져 있는 것을 알 수 있다.

원형 연결 리스트

변형된 원형 연결 리스트

해당 그림은 원형 연결 리스트를 약간 변형한 원형 연결 리스트이다.

변형된 원형 연결 리스트를 보면 다른 연결리스트와는 달리 head가 첫 번째 노드를 가리키는 것이 아닌 마지막 노드를 가리키고 있는 것을 볼 수 있다.

첫 번째 노드는 head->link가 가리키고 있으므로, 리스트의 마지막에 노드를 삽입하거나 삭제하기 위하여 리스트의 맨 끝까지 힘들게 가지 않아도 된다는 장점이 생긴다.

만약 그림1의 원형 연결 리스트를 사용한다고 해보자.

30이라는 data를 가진 노드 다음에 새로운 노드를 삽입을 한다고 하였을 때, 해당 노드(data가 30인 노드)까지 반복문(for문등)을 사용해서 찾아간 후 새로운 노드를 삽입할 수 있다.

하지만 변형된 원형 연결 리스트의 경우,  head는 data가 30인 노드를 가리키고 있기에 바로 삽입을 할 수 있다.

 

이번에는 원형 연결 리스트에 필요한 기능들을 알아보자.

• 첫번째 노드에 새로운 노드 삽입
• 중간에 새로운 노드 삽입
• 마지막 노드에 새로운 노드 삽입
• 원형 연결 리스트 출력

이렇게 3가지 기능을 볼 수 있고, 순차적으로 진행하겠다.

모든 삽입의 문제는 기존의 리스트에 새로운 노드를 어떻게 삽입할 것이냐가 가장 큰 문제점이다.

삽입을 3가지로 나눈 이유는 head가 가리키고 있는 노드를 바꾸느냐 안바꾸느냐 혹은 head가 가리키고 있는 노드의 정보가 필요하냐 아니냐의 문제로 나눈것 이다.

첫번째와 마지막 노드에 새로운 노드를 삽입하는 경우는 head가 가리키고 있는 노드(즉, 마지막 노드)의 정보가 필요하고, 중간에 새로운 노드를 삽입 하는 경우는 head의 정보가 필요없다. 기존의 단순연결리스트의 중간삽입과 같은 양상을 띄고 있다.

 

원형 리스트의 처음에 삽입

다음 그림과 같이 먼저 새로운 노드가 첫 번째 노드를 가리키게 하고 다음에 마지막 노드의 (head가 가리키고 있는 노드)가 새로운 노드를 가리키게 하면된다.

만약 head(위 그림의 tail)가 NULL일 경우. 즉,  기존의 리스트가 없는 경우에는 어쨋든 원형을 이루어야 하기에 새로운노드가 자기 자신을 가리킨다.

ListNode* insert_first(기존의 리스트 head, 삽입할 노드의 data)
{
	ListNode *node = (ListNode *)malloc(sizeof(LIstNode));	//새로운 노드 생성
    node-> data = data		//삽입할 노드의 data를 새로운 노드에 넣는다.
    
    if (head == NULL){		//만약 기존의 리스트가 없을 경우
    	head = node;		//새로운 노드를 head가 가리킨다.
        node -> link = head;	//node가 가리키는 새로운 노드의 link가 새로운 노드를 가리킨 head를 가리킨다.
        			//즉,노드가 한가지 밖에 없기에 새로운 노드가 자기 자신을 가리킨다.
    }
    else {				//기존의 리스트가 있을 경우
    	node -> link = head -> link;	//head가 가리키고 있는 link가 가리키고 있는 노드를 node가 가리키는 새로운 노드의 link가 가리킨다.
        				//즉, 기존 리스트의 첫번째 노드를 새로운 노드가 가리킨다.
        head -> link = node;		//head가 가리키고 있는 link가 새로운 노드를 가리킨다.
        				//즉, 마지막 노드가 새로운 노드를 가리킨다.
    }
    return head;	//변경된 헤드 포인터를 반환한다.
}

원형 리스트 끝에 삽입

앞의 코드에 한 문장만 추가하면 원형 연결 리스트의 끝에 삽입할 수 있다.

원형 리스트의 처음에 삽입한 부분에서 해당 그림처럼 head의 위치만 새로운 노드로 바꾸어주면 새로운 노드가 마지막 노드가 된다.

(해당 그림은 head가 첫번째 노드를 가리키는 것처럼 오해할 수 있지만 head는 항상 마지막 노드를 가리킨다는 것을 유의하자!!)

원형리스트 끝에 삽입하면 해당 그림과 같이 연결 되어 있다.

ListNode* insert_last(기존 리스트의 head, 삽입할 노드의 data)
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));	//새로운 노드 생성 및 새로운 노드를 가리키는 포인터 생성
    node->data = data;	//새로운 노드에 data를 넣음
    
    if(head == NULL)	//기존의 리스트가 없는 경우
    {			//처음에 삽입과 같이 새로운 노드가 자기자신을 가리킨다.
    	head = node;
        node->link =head;
    }
    else {
    	node->link = head->link;	//head가 가리키고 있던 노드의 링크가 가리키는 노드를, node가 가리키는 새로운 노드의 링크가 가리킨다.
        			//즉, 새로운 노드가 첫번째 노드를 가리킨다.
        head->link = node;	//head가 가리키고 있는 노드의 링크가, 새로운 노드(포인터 node가 가리키는)를 가리킨다.
        			//즉, 마지막 노드가 새로운 노드를 가리킨다.
        head = node;		//node가 가리키고 있는 노드를 head가 가리키게 한다.
                	  	  //즉, 새로운 노드가 마지막 노드가 된다.
    }
    return head;	//변경된 헤드 포인터를 반환한다.
}

 

원형 연결 리스트의 항목 출력

head는 마지막 노드를 가리키고 있다. 그러므로 head가 가리키고 있는 노드(마지막 노드)의 링크가 가리키는 노드가 첫번째 노드가 된다.

그 후에는 해당 노드의 링크를 타고 다음 노드로 이동하여 데이터를 출력해야 한다.

기차가 철도를 타고 다음 역에 가듯이 연결리스트도 다음 노드(역)를 타고가기 위해서는 타고갈 노드(기차)가 하나 필요하다. 철도는 링크가 된다.

void print_list(기존 리스트의 head)
{
	ListNode* p;	//리스트(노선)를 타고 갈 포인터(기차) 생성
    
    if(head == NULL) return;	//기존의 리스트가 없으면 return
    p = head->link;		//head가 가리키고 있는 노드의 link가 가리키는 노드(첫번째 노드, 역)를 포인터 p(기차)가 가리킨다.
    do {
    	printf("%d ->", p->data);	//p(기차)가 가리키는 노드(역)의 data(역 이름) 출력
        p = p-> link;	//p가 가리키는 노드의 링크가 가리키는 노드(다음 역)을 p(기차)가 가리킨다.
    }while (p != head);	//p가 가리키는 노드와 head가 가리키는 노드가 다르면 계속, 같으면 끝
    
    printf("%d->", p->data);	//마지막 노드 출력
}

 

전체 원형 연결 리스트

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

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

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);
	printf("head가 가리키는 노드 : %d\n", head->link->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 main() {
	ListNode* head = NULL;

	head = insert_last(head, 20);
	print_list(head);
	head = insert_last(head, 30);
	print_list(head);
	head = insert_last(head, 40);
	print_list(head);
	head = insert_first(head, 10);
	print_list(head);
	return 0;
}