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

연결리스트(linked list)

연결리스트는 각 데이터들을 포인터로 연결하여 관리하는 구조이다. 이때, 자기 참조 구조체를 선언하여 '노드'라는 것을 만들고 이를 포인터로 연결한다. 

 

자기 참조 구조체

자기참조구조체란 구조체 안에서 자신과 똑같은 모양의 구조체를 포인터로 가리키는 모양을 띄고 있다. 

 

struct self{
	struct self * link;
};

위 코드가 자기 참조 구조체의 가장 간단한 형태이다. 

struct self 안에서 struct self 형을 가리키는 link를 선언해서 포인터가 가리킬 수 있도록 하였다. 

 

이 것을 이용하면 연결리스트를 구현할 수 있다. 

 

연결리스트

연결리스트의 기본 모양

typedef int element;

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

 연결리스트는 자기 참조 구조체에 data를 담는 칸을 하나 더 생성해주면 된다. data를 담아주고 next가 그 다음 노드를 가리키면서 연결리스트가 구현된다. 

 여기서 typedef int element를 왜 사용했는지 의문을 가지는 사람들이 있을 것이다. 이는 나중에 data가 char, double 등 자료형이 바뀌게 될 때 변경을 조금 더 용이하게 하기 위해서 다음과 같이 만들었다. 

 

연결리스트의 종류

연결리스트는 어떻게 만드냐에 따라 다양하게 이용할 수 있다. 그 중 대표적인 모양만 소개하겠다.

1) 단순 연결리스트

2) 원형 연결리스트

3) 이중 연결리스트

 

각각의 연결리스트를 도식화 하면 다음과 같다.

연결리스트 도식화

head가 시작점을 가리키고 있으며  data에 우리가 담고자 하는 데이터가 담기고, next가 그 다음 데이터가 담긴 구조체를 가리키고 있다. 

연결리스트의 사용 이유

여기서 우리가 한 가지 느껴야 할 것은 연결리스트를 왜 사용하느냐는 것이다. 순차적인 데이터를 저장하는 방법은 배열이라는 편리한 자료구조가 존재한다. index 기능도 지원하고 선언, 데이터 보관도 편리한데 왜 우리는 연결리스트를 사용할까?

 

그 이유는 배열의 데이터 선언방식 때문이다. 배열은 선언할 때 데이터 크기를 정해주어야 한다. 즉, 정적인 메모리타입을 가지고 있다.

 

만약 int array[100]; 으로 선언했다고 하자.  

우리가 이 배열을 선언 한 후 4칸만 사용했다고 하면 나머지 96칸은 메모리 낭비를 일으키고 있는 것이다. 여기까지는 나쁘지 않다. 그냥 크기가 더 큰 램을 사용하면 어느정도 해결될 것이다. 하지만, 어쩌다보지 104칸을 사용해야한다면? 우리는 다시 배열을 선언해서 데이터를 옮겨주어야 한다. 이는 말도 안되는 것이다. 결국 이런 사태를 방지하기 위해 우리는 배열을 점점 더 크게 선언을 하게 될 것이고 이는 결국 메모리 낭비를 일으키게 된다. 

 

그에 비해 연결리스트는 동적으로 메모리를 할당한다. 노드를 생성할 때 malloc으로 생성하고 노드를 삭제할 때 free를 사용해 메모리에서 삭제시킨다. 결국 실제로 사용하는 데이터만을 다룰 수 있다는 좋은 점이 있다. 

 

이 외에도 데이터를 중간에 삽입할 때 연결리스트가 훨씬 유리하다. 배열은 연속적으로 메모리에 할당이 되어있기 때문에 중간에 메모리를 삽입하기 위해서는 이미 있는 데이터를 한칸씩 이동시켜주어야 한다. 이것이 100만개의 데이터라면? 1억개의 데이터라면? 굉장히 불편함이 느껴질 것이다. 연결리스트는 노드의 link만 바꾸어 주면 되기 때문에 중간 삽입이 굉장히 자유롭다. 

 

배열보다 사전적 지식도 많이 알아야하고 포인터를 사용하기 때문에 헷갈리기도 하지만, 연결리스트를 잘 사용한다면 같은 문제도 배열보다 훨씬 쉽게 풀 수 있을 것이다. 

 

단순 연결리스트의 구현

0. 자기참조구조체의 선언

typedef int element;

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

 

 

1. makenode

노드를 동적할당해주는 코드이다.

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

보통 insert할 때 node 생성과정을 같이 하는 경우가 많은데 나는 귀찮아서 makenode 함수를 만들어서 호출하는 형태로 제작했다. 함수가 더 귀찮은 사람들은 그냥 insert 함수에서 node를 생성해주면 된다. 

 

 

2. insert_first

연결리스트의 맨 앞에 노드를 삽입하는 코드이다. 

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

 

 

3. insert

원하는 노드 뒤에 새 노드를 삽입하는 코드이다.

Node* insert(Node* h, Node* p, element data)
{
	Node* curr = makenode(data);
	curr->next = p->next;
	p->next = curr;
	return h;
}

 

 

4. delete_first

가장 앞에 있는 노드를 삭제하는 코드이다.

Node* delete_first(Node* h)
{
	if (h == NULL)
		return NULL;
	Node* f = h;
	h = h->next;
	free(f);
	return h;
}

 

5. delete

원하는 노드를 삭제하는 코드이다. 

Node* delete(Node* h, Node* p)
{
	Node* f = p->next;
	p->next = f->next;
	free(f);
	return h;
}

이 코드에서 주의할 점은 Node * p 는 삭제할 노드가 아닌 삭제할 노드의 바로 앞 노드를 가리킨다.

 

 

6. print_List

연결리스트를 출력해주는 코드이다.

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

출력은 본인 스타일대로 제작하면 된다. 함수 없이 그냥 main에서 실행해도 좋다. 나는 그냥 공부하고 있는 책의 형태를 따라했다.

 

출력 테스트

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

typedef int element;

typedef struct linkedlist {
	element data;
	struct linkedlist* 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);
	curr->next = h;
	h = curr;
	return h;
}

Node* insert(Node* h, Node* p, element data)
{
	Node* curr = makenode(data);
	curr->next = p->next;
	p->next = curr;
	return h;
}

Node* delete_first(Node* h)
{
	if (h == NULL)
		return NULL;
	Node* f = h;
	h = h->next;
	free(f);
	return h;
}

Node* delete(Node* h, Node* p)
{
	Node* f = p->next;
	p->next = f->next;
	free(f);
	return h;
}

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


int main()
{
	Node* h = NULL;

	for (int i = 0; i < 5; i++)
	{
		h = insert_first(h, i);
		printList(h);
	}
	printList(h);
	for (int i = 0; i < 5; i++)
	{
		h = delete_first(h, i);
		printList(h);
	}
	return 0;
}

 

 

[출력결과]

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

 

 

[소감]

우리 학부는 기초프로그래밍을 할 때 연결리스트까지 진도를 나가기 때문에 익숙해서 그리 어렵지 않았다. 하지만, 원형 연결리스트나 이중 연결리스트는 처음 다루어 보는 것이기 때문에 다음 진도에서는 조금 더 정신을 차리고 공부할 필요성이 있는 것 같다.