C언어 자료구조 List(3) - 원형 연결리스트? 이중 연결리스트? 에 대해서 알아보고 직접 만들어보기

안녕하세요 올라프입니다! 이때까지 자료구조의 리스트에서 단순 연결리스트까지 알아보았습니다. 오늘은 리스트의 나머지 종류인 원형 연결리스트와 이중 연결리스트에 대해서 알아보겠습니다.
 원형, 이중 연결리스트를 알기 위해서는 앞의 내용인 단순 연결리스트에 대해서 알아야 합니다.

2020/09/01 - [전공지식/자료구조 와 알고리즘] - C언어 자료구조 List(2) - 단순 연결 리스트란?

C언어 자료구조 List(2) - 단순 연결 리스트란?

원형 연결 리스트(Circular Linked List)는 마지막 노드의 링크가 가장 첫 번째 노드를 가리키는 리스트를 의미합니다. 모든 노드가 연결되어 있으므로 한 노드에서 다른 노드로 접근을 쉽게 할 수 있습니다. 헤드가 첫 번째 노드를 가리킬 때 마지막 노드의 링크는 헤드가 가리키는 첫 번째 노드를 가리킵니다.
 헤드가 마지막 노드를 가리키면 바로 다음 노드는 리스트의 첫 번째 노드를 가리킵니다. 그래서 헤드가 마지막 노드에 있으면 리스트의 처음이나 마지막에 더욱더 쉽게 접근할 수 있습니다. 삽입 연산을 쉽게 할 수 있습니다.

 자료구조에서 가장 많이 쓰였던 리스트는 이중 연결리스트입니다.
이중 연결리스트 (Double Linked List)는 단순 연결리스트에서 앞의 노드로도 링크가 가리키도록 설계한 리스트입니다. 이때까지 사용한 노드는 데이터와 링크로 이루어진 쌍이었지만 이중 연결리스트는 앞에 있는 선행노드도 가리켜야 하므로 링크, 데이터, 링크로 노드가 이루어져 있습니다.
 데이터 앞의 링크는 선행노드에 대한 링크하고 있고 데이터 뒤의 링크는 후행 노드에 대한 링크하고 있습니다. 따라서 모든 방향으로 노드를 이동하여 검색할 수 있다는 장점이 있어서 좀 더 빠르고 효율적으로 검색 연산을 수행할 수 있습니다.
 하지만 양방향의 링크를 노드에 담고 있으므로 공간을 많이 차지하고 리스트 구현과 연산이 복잡합니다.

 이중연결리스트에서 사용되는 연산들에 대해 알아보겠습니다. 탐색 연산 등은 단순 연결리스트와 같은 방식이지만 삽입과 삭제 연산은 조금 다릅니다.
 삽입 연산에는 선행노드와 새로 삽입하는 노드가 필요합니다. 과정은 꽤 복잡합니다. 순서대로 하는 것이 중요합니다.
1. 새로운 노드의 왼쪽 링크에 선행노드를 가리키게 먼저 합니다.
2. 새로운 노드의 오른쪽 링크는 선행노드의 원래 후행 노드를 가리키게 합니다.
3. 선행노드의 원래 후행 노드의 왼쪽 링크는 새로운 노드를 가리켜야 합니다.
4. 선행노드의 오른쪽 링크는 새로운 노드를 가리키게 합니다.
 이 순서대로 하는 것이 중요합니다.

void dinsert_node(DlistNode *before, DlistNode *new_node)
{	
	new_node->llink = before;
	new_node->rrlink = before->rlink;
	before->rlink->llink = new_node;
	before->rlink = new_node;
}

 삭제 연산은 삽입 연산보다는 간단합니다. 
만약 removed 즉 삭제하려는 노드가 phead_node이면 빈 노드이므로 반환할 것이 없습니다.
 빈 노드가 아닐 때 삭제할 노드의 선행노드가 뒤로 가리키는 방향을 removed의 후행 노드로 가게 해야 합니다.
 그런 후 removed의 후행 노드가 removed를 가리키는 것을 선행노드를 가리키게 해야 합니다. 그럼 removed를 가리키는 링크가 없어지므로 removed 노드만 남으므로 메모리 할당을 해제합니다.

void dremove_node(DlistNode *before, DlistNode *removed)
{	
	if(removed == phead_node ) return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}

 이중연결리스트는 노드별로 양방향으로 연결해야 하므로 매우 어렵습니다. 또한, 연산작업도 복잡해서 실수로 인해서 오류가 자주 발생하는 구간입니다.

먼저 예시로 배열로 구한 리스트를 구현해보겠습니다.
구조체를 선언하는데 리스트 배열의 크기는 MAX_LIST_SIZE로 50으로 지정하였습니다. length는 배열에 저장된 항목들의 개수입니다.

 init 함수는 리스트를 초기화시킵니다.
 is_full 함수는 length의 길이와 MAX_LIST_SIZE와 비교하여 가득 찼는지 판단합니다.
 add 함수는 리스트에 특정 position이라는 정수를 받아서 그 위치에 item이라는 항목을 추가합니다.
 리스트가 가득 차지 않아야 하고 위치는 0보다 크며 position이 길이보다 짧아야 합니다. position 위치를 비우기 위해서 position부터 끝까지는 모두 한 칸 미루고 리스트[position]에 item을 추가합니다. 그리고 길이도 한 개 늘려줍니다.
 del 함수는 삭제 함수입니다. 리스트에서 position 위치의 항목을 제거한 후 뒤의 항목들을 한 칸 당깁니다.

 이제 메인 함수에서 예시를 들어 실행해보겠습니다. 50, 40, 30, 20을 순서대로 넣으면 20-30-40-50이 됩니다. 그리고 del을 이용하여 0번 자리 항목을 제거하면 30-40-50이 됩니다.
 반복문을 이용하여 리스트를 순서대로 출력하면 30, 40, 50 순서대로 출력됩니다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_LIST_SIZE 50
typedef int element;
typedef struct {
	element list[MAX_LIST_SIZE]; 
	int length; 
} ArrayListType;
void init(ArrayListType* L) {
	L->length = 0;
}
int is_full(ArrayListType* L) {
	if (L->length == MAX_LIST_SIZE) return 1;
	return 0;
}

void add(ArrayListType* L, int position, element item)
{
	int i;
	if (!is_full(L) && (position >= 0) && (position <= L->length)) {
		for (i = (L->length - 1); i >= position; i--)
			L->list[i + 1] = L->list[i];
		L->list[position] = item;
		L->length++;
	}
}


element del(ArrayListType* L, int position) {
	element item; int i;
	if (position < 0 || position >= L->length) printf("error");
	item = L->list[position];
	for (i = position; i < (L->length - 1); i++) L->list[i] = L->list[i + 1];
	L->length--;
	return item;
}
 
int main() {
	ArrayListType list2;
	int i;

	init(&list2 );
	add(&list2, 0, 50);
	add(&list2, 0, 40);
	add(&list2, 0, 30);
	add(&list2, 0, 20);

	del(&list2, 0);

	for (i = 0; i < list2.length; i++) {
		printf("%d\n", list2.list[i]);
	}

	return 0;
}

 배열로 리스트를 구성하는 법은 매우 간단하고 쉽습니다.

이제 동적 메모리를 이용하여 단순 연결리스트를 구현해보겠습니다.
먼저 리스트의 노드를 구성해주었습니다. 단순 연결리스트이기 때문에 데이터, 링크로 구성된 한 쌍만 만들면 됩니다. 구조체로 ListNode를 만들었는데 데이터와 포인터로 만든 링크가 있습니다.
 display 함수는 헤드 포인터를 이용하여 데이터들을 출력하다가 마지막 노드의 링크는 NULL이므로 NULL이 되면 반복을 멈추는 원리를 가지고 있습니다.
 create_node 함수는 malloc을 이용하여 데이터를 할당받아 새로운 노드를 생성합니다. 새로운 노드의 링크는 NULL입니다!

 이제 메인 함수에서는 10, 20, 30을 순서대로 삽입하였지만 고쳐서 10, 30, 50을 삽입하게 하였습니다. 
그렇게 10, 30, 50을 삽입하면 리스트가 50 - 30 - 10으로 출력됩니다. 그런 후 첫 번째 노드를 제거할 경우 헤드 포인터가 제거된 노드가 가리키던 두 번째 노드를 가리키므로 30-10이 됩니다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
typedef int element;

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

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


ListNode *create_node(element data)
{
	ListNode *new_node;
	new_node = (ListNode *)malloc(sizeof (ListNode));

	if (new_node == NULL) {
		printf("메모리 할당 오류 \n");
		exit(1);
	}

	new_node->data = data;
	new_node->link = NULL;

	return(new_node);
}

int main() {
	ListNode* phead1 = NULL, * new_node = NULL;
	ListNode* removed = NULL, * p = NULL;
	int i, data;
	
	printf("add 10 30 50 nodes \n");
	for (i = 0; i < 3; i++) {
		printf("input:");
		scanf("%d", &data);
		new_node = create_node(data);
		if (phead1 == NULL) { 
			phead1 = new_node;
		}
		else { 
			new_node->link = phead1;
			phead1 = new_node;
		}
	}
	display(phead1);


	printf("remove 50 node (first node) \n");
	removed = phead1;
	phead1 = phead1->link;
	free(removed);
	display(phead1);
	return 0;

} 

 오늘까지 배열, 연결을 이용한 리스트에 대해 알아보고 마지막에는 배열, 연결을 이용하여 리스트를 구현해보았습니다. 다음에는 스택, 큐, 덱 등 다양한 자료구조에 대해서 알아보겠습니다.

 단순 연결리스트를 먼저 아는 것이 좋습니다!

2020/09/01 - [전공지식/자료구조 와 알고리즘] - C언어 자료구조 List(2) - 단순 연결 리스트란?

C언어 자료구조 List(2) - 단순 연결 리스트란?