원형 연결 리스트

이번에 소개할 자료구조는 원형 연결 리스트입니다.

---

1. 원형 연결 리스트 소개

원형이라는 이름에서 볼 수 있듯이 동그란 형태를 가진 연결 리스트입니다. 하지만 연결 리스트 소개에서 이야기 했듯이 실제 물리적으로 원형이 아니라 처음과 끝이 이어져 있기 때문에 원형이라고 불리우는 것 입니다. 지난번 까지 배운 연결 리스트는 head 노드와 tail 노드가 정해져 있어서 시작과 끝이 확실한 하나의 선 같은 구조였습니다. 그러나 원형 연결 리스트는 끝의 주소 필드가 처음을 가리켜서 마치 원형처럼 보이게 됩니다.

 

2. 노드 정의

노드 구조 자체는 연결리스트와 같이 [데이터 필드-링크 필드] 쌍으로 이루어져있기 때문에 지난번 노드 정의와 다르지 않습니다.

typedef struct ListNode {
	char data[10];
	struct ListNode* link;
}listNode;

//헤드 노드 정의
typedef struct {
	listNode* head;
}linkedList_h;

 

 

3. 노드 삽입하기

원형 연결 리스트에서 노드를 삽입하는 방법은 두가지 입니다. 처음에 넣는 방식과 중간에 삽입하는 방식 두가지 뿐입니다. 왜냐하면 끝이 따로 없기 때문에 마지막에 넣으나 중간에 넣으나 다른 작업이 필요없고 동일한 작업을 하기 때문입니다.

3-1. 리스트 처음에 노드 삽입하기

리스트 처음에 삽입하는 작업에서 유의할 점은 원형이기 때문에 빈 리스트가 아니라면 마지막 노드의 링크 필드가 새로 삽입한 첫 노드를 가리키게 하고 삽입한 노드가 이전의 첫 노드를 가리키게 하는 것을 해줘야 한다는 것에 유의해야 합니다.

void insertFirstNode(linkedList_h* CL, char* x) {
	listNode* newNode, * temp;

	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);

	//빈 리스트일대 노드 삽입
	if (CL->head = NULL) {
		CL->head = newNode;	//새노드를 head로 만들어줍니다.
		newNode->link = newNode;
	}
    //빈 리스트가 아닐때 노드 삽입
	else {
		temp = CL->head;

		while (temp->link != CL->head) {
			temp = temp->link;
		}

		newNode->link = temp->link;
		temp->link = newNode;	//마지막 노드와 새로 삽입한 노드를 연결
		CL->head = newNode;
	}
}

 

3-2. 리스트 중간에 노드 삽입하기

리스트 중간 삽입도 지난번과 별반 차이없습니다. 그냥 모든 노드에 대해서 이전 노드의 링크 필드가 가리키던 주소를 새 노드가 가리키게 해서 삽입하면 됩니다.

void insertMiddleNode(linkedList_h* CL, listNode* pre, char* x) {
	listNode* newNode;

	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);

	if (CL == NULL) {
		CL->head = newNode;
		newNode->link = newNode;
	}
	else {
		newNode->link = pre->link;
		pre->link = newNode;
	}
}

 

 

4. 노드 삭제하기

노드 삭제 또한 기존 연결 리스트에서 따로 추가적인 기술을 요구하지 않습니다. 삭제한 노드가 가리키는 링크 필드를 이전 노드가 가리키게만 하면 되는 것 이죠.

void deleteNode(linkedList_h* CL, listNode* oldNode) {
	listNode* pre;

	//빈 리스트라면 삭제 연산을 멈춥니다.
	if (CL->head==NULL) {
		return;
	}

	//리스트에 노드가 한 개일 때
	if (CL->head->link == CL->head) {
		free(CL->head);
		CL->head = NULL;	//리스트의 head를 NULL로 설정
		return;
	}
	else if (oldNode == NULL) {
		return;
	}
	else {
		pre = CL->head;

		while (pre->link != oldNode) {
			pre = pre->link;
		}

		pre->link = oldNode->link;

		if (oldNode == CL->head) {
			CL->head = oldNode->link;
		}

		free(oldNode);
	}
}

---

이번 리스트는 지난 연결리스트에서 확장한 수준이라서 중복되는 코드나 설명을 제외했습니다. 전체 코드는 깃허브나 지난 연결 리스트 포스트를 참조해주세요.

2021.09.03 - [Programming/자료구조] - 연결 리스트 Linked List

연결 리스트 Linked List

https://github.com/Bam-j/DataStructureByC/blob/master/DataStructure/CircularLinkedList.c

GitHub - Bam-j/DataStructureByC: 블로그 작성용 자료구조 코드들, C언어 버전