[C언어] 연결리스트 (linked list)

linked representation

동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 연결된 표현

이 연결된 표현은 포인터를 사용하여 리스트들을 연결. 

이는 트리 그래프 스택 큐 등을 구현하는데도 많이 사용된다. 

 

linked list

물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결리스트(linked list)라고 한다. 해당연결은 포인터를 활용

기존의 배열로 구성한 리스트처럼 데이터들을 옮길 필요없이 포인터를 수정하면 된다. 

 

장점 : 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다는 것. 이것은 순차적인 표현 방법은 배열에 비하여 상당한 장점. 

 

단점 : 배열에 비하여 상대적으로 구현이 어렵고 오류가 나기 쉬움 또한 데이터 뿐만 아니라 포인터도 저장해야 하므로 메모리 공간을 많이 사용. 또 i 번째 데이터를 찾으려면 앞에서부터 순차적으로 접근해야함. 

 

연결리스트의 구조

연결리스트는 노드(node)들의 집합. 노드는 데이터필드(data field)와 링크필드(link field)로 구성되어있다.

 

[N] -> [data][link] -> 

 

데이터 필드에는 우리가 저장하고 싶은 데이터가 들어간다. 링크필드에는 다른 노드를 가리키는 포인터가 저장된다. 연결 리스트에서는 연결 리스트의 첫번째 노드를 알아야 만이 전체 노드의 접근할 수 있다. 따라서 연결리스트마다 첫 번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드 포인터(head ponter)라고 한다. 그리고 마지막 노드의 링크필드는 NULL로 설정 이는 더 이상 연결된 노드가 없다는 것을 의미

 

연결 리스트의 종류 

단순 연결리스트 (singly linked list) :단방향 연결 리스트. 체인(chain)이라고도 부름.  단순 방향으로만 연결되어 있는 연결리스트에서 마닞막 노드의 링크는 NULL이다. 

 

이 외에 원형 연결 리스트, 이중 연결리스트 등이 있지만 이건 이후의 포스팅에서 다뤄보도록 하고 오늘은 단순 연결리스트에 대해서만 구현해보겠다. 

 

-노드는 어떻게 정의할 것인가? -> 자기 참조 구조체를 이용한다.

-노드는 어떻게 생성할 것인가? -> malloc()을 호출하여 동적 메모리로 생성한다. 

-노드는 어떻게 삭제할 것인가? -> free()를 호출하여 동적 메모리를 해제한다. 

 

연결 리스트 구현 

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

//
typedef int element;
//
typedef struct ListNode { 	// 노드 타입을 구조체로 정의한다.
	element data;
	struct ListNode* link;
} ListNode;

//
ListNode* search_list(ListNode* head, element value) {
	ListNode* p;
	p = head;
	while (p != NULL) {
		if (p->data == value) {
			return p;
		}
		p = p->link;
	}
	return NULL;
}
ListNode* insert_first(ListNode* head, int value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));	//(1)
	p->data = value;		//(2)
	p->link = head;			//(3)
	head = p;				//(4)
	return head;
}

// 노드 pre 뒤에 새로운 노드 삽입
ListNode* insert(ListNode* head, ListNode* pre, element value)
{
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));	//(1)
	p->data = value;		//(2)
	p->link = pre->link;	//(3)	
	pre->link = p;			//(4)	
	return head;			//(5)	
}

//
ListNode* delete_first(ListNode* head)
{
	ListNode* removed;
	if (head == NULL) return NULL;
	removed = head;			// (1)
	head = removed->link;	// (2)
	free(removed);			// (3)
	return head;			// (4)
}

// pre가 가리키는 노드의 다음 노드를 삭제한다. 
ListNode* delete_pre(ListNode* head, ListNode* pre)
{
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;	// (2)
	free(removed);				// (3)
	return head;				// (4)
}

// linked list 출력하기.
void print_list(ListNode* head)
{
	for (ListNode* p = head; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}

// 테스트 프로그램
int main(void)
{
	ListNode* head = NULL;	// lisked list 를 가리키는 헤드 pointer.
	ListNode* ptr = NULL;
	// 1. 리스트 생성(10,20,30,40,50)
	for (int i = 50; i >= 10; i -= 10) {
		head = insert_first(head, i);
		print_list(head);
	}
	// 2. 40 찾기 
	ptr = search_list(head, 40);
	// 못 찾은 경우 : prt == NULL
	// 찾은 경우 : ptr != NULL
	if (ptr != NULL) { printf("> 데이터를 찾음 (%d)\n", ptr->data); }
	else { printf("데이터를 못찾음 \n"); }

	for (int i = 0; i < 5; i++) {
		head = delete_first(head);
		print_list(head);
	}

	return 0;
}

삽입연산 insert_first() 

단순 연결리스트의 경우 리스트의 처음이나 끝에 새로운 노드를 추가하는 경우가 많음. 

ListNode * insert_first(ListNode *head, element value);

새로운 노드를 하나 생성하고 새로운 노드의 link의 현재의 head 값을 저장 한 후에, head를 변경하여 새로운 노드를 가리키도록 하면 된다. insert_fisrt()는 변경된 헤드 포인터를 반환. 따라서 반환된 값을 헤드 포인터에 저장해야함 

 

삽입연산 insert(head, pre, value)

연결리스트 중간에 새로운 노드를 추가하는 메소드 

1. 새로운 노드를 생성하여 변수 p로 가리킨다. 

2. p의 데이터 필드에 value 를 저장한다.

3. p의 링크 필드가 다음 노드의 데이터 필드를 가리키도록 변경

4. 헤드노드의 링크필드가 pre노드의 데이터필드를 가리키게 한다.  

5. 변경된 헤드 포인터 반환 

 

head -> [data][link] -> pre [data][link] -> p[data][link] -> 다음 노드

 

삭제 연산 delete(head,pre)

delete_first()는 해당 설명을 들으면 이해가 갈것이다. 

1. 삭제할 노드를 찾는다. 

2. pre 가 가리키는 링크필드에 삭제될 노드의 링크필드를 넣는다(다음 노드를 가리키기 때문) 

3. 삭제할 노드의 동적 메모리를 반납 

4. 변경된 헤드 포인터를 반환 

 

방문 연산 print_list(ListNode *head)

노드의 링크값이 NULL이 아니면 계속 링크를 따라가면서 노드를 방문. 링크값이 NULL이면 연결 리스트의 끝에 도달할 것이므로 반복을 중단.