[자료구조] C - 연결리스트(linkedlist) - 2. 원형연결리스트

오늘은 지난시간에 이어서 연결리스트에 대한 이야기를 할 것이다. 

 

 

연결리스트의 개념과 단순연결리스트에 대한 내용은 아래 링크를 참고해라.

https://mobuk.tistory.com/8?category=1076684 

[자료구조] C - 연결리스트(linkedlist) - 1. 단순연결리스트

 

원형연결리스트의 구조

지난시간에는 단순연결리스트에 대해 공부했다. 이번에는 단순 연결리스트의 처음과 끝이 연결되어 있는 형태인 원형연결리스트에 대해 공부했다. 

 

원형 연결리스트 구조는 기본적으로는 다음과 같다. 

head가 첫번째 노드를 가리키고 있고 마지막 노드가 첫번째 노드를 가리키고 있다. 하지만, 우리는 이 연결리스트를 아래의 모습으로 변형하여 사용하고자 한다. 

여기서는 head가 가리키는 것이 첫번째 노드가 아닌 마지막 노드이다. 첫번째 노드는 head가 가리키는 것이 아닌 head->next가 가리키고 있다.

 

왜 이렇게 변형해서 사용할까? 그 이유는 연결리스트에 노드를 마지막에 삽입하는 것을 조금 더 쉽게 하기 위해서이다. 우리는 노드를 마지막에 삽입하려면 연결리스트를 순회하여 마지막을 찾아야했다. 원형 연결리스트도 원형이지만 단방향이기 때문에 결국 원을 순회하여 마지막 지점을 찾아야한다. 이는 마지막에 삽입해야하는 경우 너무 시간을 낭비하는 일이다. 그래서 조금 코드가 복잡해지더라도 head가 마지막 노드를 가리키게 하도록 코드를 짜보았다. 

 

원형 연결리스트의 구현

0. 자기 참조 구조체로 노드 선언(단순연결리스트와 동일하다.)

typedef int element;

typedef struct node {
	element data;
	struct node* next;
}Node;

 

 

1. makenode

Node* makenode(element data)
{
	Node* curr = (Node*)malloc(sizeof(Node));
	curr->data = data;
	curr->next = NULL;
	return curr;
}

 

2. insert_first

Node* insert_first(Node* h, element data)
{
	Node* curr = makenode(data);
	if (h == NULL)
	{
		h = curr;
		curr->next = curr;
	}
	else
	{
		curr->next = h->next;
		h->next = curr;
	}
	return h;
}

 

 

3. insert_last

Node* insert_last(Node* h, element data)
{
	Node* curr = makenode(data);
	if (h == NULL)
	{
		h = curr;
		curr->next = curr;
	}
	else
	{
		curr->next = h->next;
		h->next = curr;
		h = curr;
	}
	return h;
}

이 함수의 특이한 점은 insert_first와 코드가 한줄밖에 변한 것이 없다는 것이다. 마지막 노드를 처음 자리에 넣고 head의 위치를 바꾼 것이 특징이다. 이전까지는 위치를 직접 찾아서 넣어주었지만, head의 위치를 변경한 것은 이번 코드가 처음이다. 

 

4. printList

//내가 만든 printList 코드
void printList(Node* h)
{
	if (h == NULL)
		return;
	for (Node* p = h->next; p != h; p = p->next)
	{
		printf("%d->", p->data);
	}
	printf("%d->\n", h->data);
}

나는 while 문 보다 for문을 더 좋아하기 때문에 (한눈에 조건 변화가 보이기 때문에) 외의 코드와 같이 for문을 사용했다. 하지만, 책에서는 do-while문을 사용해서 만들고 있다. 책에서 소개한 코드는 아래와 같다.

/*책에서 소개한 print_list 코드*/

void print_list(Node* h)
{
	if (h == NULL)
		return;
	Node* p = h->next;
	do {
		printf("%d->", p->data);
		p = p->next;
	} while (p != h);
	printf("%d->", p->data);
}

근데 나는 여기서 do-while문을 왜 사용해야하는지 잘 모르겠다. 아무리 생각해도 do-while문을 사용하면 오류가 난다. 아마 책에서 노드가 하나 있는 경우는 항상 p==h이기 때문에 최초 1회를 출력해주기 위해서 do-while문을 사용한 것 같다. 하지만, while문 밖에 printf가 있기 때문에 조건에 맞지 않아도 최초 1회는 실행이 자동으로 된다. 즉, do-while문을 사용하면 중복 출력이 되어서 오히려 틀린 답을 출력하게 된다. 

내가 코드를 잘못 이해했거나 잘못 입력했을 가능성도 있어서 여러 번 더 검증해본다음 출판사 측에 한번 질문을 남겨봐야겠다. 

 

 

출력테스트

#include<stdio.h>
#pragma warning(disable:4996)
#include <stdlib.h>

typedef int element;

typedef struct node {
	element data;
	struct node* next;
}Node;

Node* makenode(element data)
{
	Node* curr = (Node*)malloc(sizeof(Node));
	curr->data = data;
	curr->next = NULL;
	return curr;
}

Node* insert_first(Node* h, element data)
{
	Node* curr = makenode(data);
	if (h == NULL)
	{
		h = curr;
		curr->next = curr;
	}
	else
	{
		curr->next = h->next;
		h->next = curr;
	}
	return h;
}

Node* insert_last(Node* h, element data)
{
	Node* curr = makenode(data);
	if (h == NULL)
	{
		h = curr;
		curr->next = curr;
	}
	else
	{
		curr->next = h->next;
		h->next = curr;
		h = curr;
	}
	return h;
}

void printList(Node* h)
{
	if (h == NULL)
		return;
	for (Node* p = h->next; p != h; p = p->next)
	{
		printf("%d->", p->data);
	}
	printf("%d->\n", h->data);
}

int main(void)
{
	Node* h = NULL;
	int i;
	for (i = 0; i < 5; i++)
	{
		h = insert_first(h,i);
		printList(h);
	}
	printf("\n");
	for (i = 10; i < 15; i++)
	{
		h = insert_last(h, i);
		printList(h);
	}
}

0~4는 앞에서부터 원형리스트에 넣어주었고, 10~14는 뒤에서부터 원형리스트에 넣어주었다. 

 

 

 

정상적으로 잘 작동하는 모습을 볼 수 있다. 

 

 

+)추가 코드

내가 사용하고 있는 책은 여기서 원형 연결리스트에 대한 소개가 끝난다. 하지만, 삭제하는 코드가 없어서 아쉬움이 남아 내가 코드를 짜보았다. 이 코드가 효율적인지 모든 케이스에서 정상적으로 돌아가는 것인지는 잘 모르겠으나, 연습삼아 열심히 만들어 보았다. 

 

delete_first

Node * delete_first(Node* h)
{
	Node* f = h->next;

	if (h == NULL)
		return;
	if (f == h)
		h = NULL;
	else
	{
		h->next = f->next;
		free(f);
	}
	return h;
}

 

 

delete_last

Node *delete_last(Node* h)
{
	Node* p = h;
	while (p->next != h)
		p = p->next;
	h = delete_first(p);
	return h;
}

 이 코드는 만들 때 굉장히 고민을 많이 했다. head는 가장 마지막 노드를 가리키고 있는데, 그 마지막 노드를 삭제하는 것이기 때문에 head를 마지막에서 하나 앞에 있는 노드를 가리키도록 해야했다. 하지만, 내가 만든 연결리스트는 단방향으로 향하기 때문에 앞으로 순회할 수는 없어서 결국 모든 노드를 순회하는 방향으로 짜야했다. 그리고 직접 노드를 삭제할 수 있었지만, 귀찮아서 이미 만들어둔 delete_first 함수를 그냥 이용했다. 뒤쪽을 공부하면서 더 효율적인 방안이 생각나면 다시 돌아와서 글을 수정하겠다. 

아마도 이런 불편함 때문에 다음시간에 공부 할 이중연결리스트가 탄생했을 것이다. 

 

 

코드를 만들 때 했던 필기(?)

자료구조를 공부하고 코드를 짤 때 나는 그림을 최대한 많이 그려보려고 노력한다. 머릿속으로 그려지고 그걸 코드로 짜면 참 좋겠지만.. 내 머리는 그정도로 똑똑하지는 못하기 때문에 이런 과정을 거친다. 그대신 한번 이렇게 공부해두면 장기적으로 기억에 남는 것 같고 코드 응용할 때 훨씬 수월해지는 것 같다.