[자료구조] 리스트 구현 - 연결리스트(단순 연결리스트)

연결리스트로 구현된 리스트

연결리스트(Linked List)는 리스트의 항목들을 노드(node)에 분산하여 저장하는 리스트입니다. 노드의 구성으로는 데이터 필드와 링크 필드가 있습니다.

데이터 필드 : 리스트의 원소, 즉 데이터 값을 저장하는 곳

링크 필드 : 다른 노드의 주소값을 저장하는 장소 (포인터)

 

연결리스트의 장점으로는 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요 없고 크기 제한이 없다는 점이 있습니다. 반면에 단점으로는 구현이 어렵고 까다로우며 오류가 발생하기 쉬운 점이 있습니다.

 

연결리스트의 종류에는 단순 연결리스트, 원형 연결리스트, 이중 연결리스트가 존재합니다. 단순 연결리스트는 가장 끝의 노드는 항상 NULL을 가리키게 되며 원형 연결리스트는 NULL이 위치한 곳이 없습니다. 이중 연결리스트는 양 끝 노드가 NULL을 가리키게 됩니다.

 

단순 연결리스트

단순 연결리스트는 하나의 링크 필드를 이용하여 연결하며 마지막 노드의 링크 값은 NULL을 가리켜야 합니다.

 

단순 연결리스트 Abstract Data Type

insert_first()

리스트의 시작 부분에 항목을 삽입하는 함수

insert()

리스트의 중간 부분에 항목을 삽입하는 함수

delete_first()

리스트의 첫 번째 항목을 삭제하는 함수

delete()

리스트의 중간 항목을 삭제하는 함수(도전 문제)

print_list()

리스트를 방문하여 모든 항목을 출력하는 함수

 

 

단순 연결리스트 구현을 위한 기본적인 알고리즘은 다음과 같습니다.

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

typedef int element;
// 노드 타입을 구조체로 정의한다.
typedef struct ListNode { 
	element data;
	struct ListNode* link;
} ListNode;
// 앞부분에 노드 삽입
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(ListNode* head, ListNode* pre)
{
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link; // (2)
	free(removed); // (3)
	return head; // (4)
}
// 리스트 출력
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;

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

/* 실행결과
0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
3->2->1->0->NULL
2->1->0->NULL
1->0->NULL
0->NULL
NULL
*/

 

특정한 값을 탐색하는 알고리즘입니다.

// 특정한 값을 탐색
ListNode* search_list(ListNode *head, element x)
{
	ListNode *p = head;

	while (  p!=NULL ) {
		if (   p->data == x)  return p;
		p = p->link;
	}
	return  NULL ;	// 탐색 실패
}
// 메인
int main(void)
{
	ListNode *head = NULL;

	head = insert_first(head, 10);
	print_list(head);
	head = insert_first(head, 20);
	print_list(head);
	head = insert_first(head, 30);
	print_list(head);
	if (search_list(head, 30) != NULL)
		printf("리스트에서 30을 찾았습니다. \n");
	else
		printf("리스트에서 30을 찾지 못했습니다. \n");
	return 0;
}

/* 실행결과
10->NULL
20->10->NULL
30->20->10->NULL
리스트에서 30을 찾았습니다.
*/

 

두 리스트를 연결하는 알고리즘입니다.

// 두 리스트를 연결
ListNode* concat_list(ListNode *head1, ListNode *head2)
{
	if (head1 == NULL) return  head2 ;
	else if (head2 == NULL) return  head1;
	else {
		ListNode *p;
		p = head1;
		while (p->link != NULL)
			p = p->link;
		p->link = head2  ;
		return  head1  ;
	}
}

 

리스트를 역순화하는 알고리즘입니다.

// 리스트를 역순화
ListNode* reverse(ListNode *head)
{
	// 순회 포인터로 p, q, r을 사용
	ListNode *p, *q, *r;

	p = head;         // p는 역순으로 만들 리스트
	q = NULL;        // q는 역순으로 만들 노드
	while (p != NULL) {
		r = q;		// r은 역순으로 된 리스트 
		q = p;	 	// r은 q, q는 p를 차례로 따라간다
		p = p->link;
		q->link = r;      	// q의 링크 방향을 바꾼다
	}
	return q;
}

 

 

단순연결리스트에 관한 문제입니다. 문제를 먼저 풀어보시고 풀이를 확인해보시기 바랍니다 

다음 중 NULL pointer가 존재하지 않는 구조는 어느 것인가? 
단순 연결리스트, 원형 연결리스트, 이중 연결리스트, 헤더 노드를 가지는 이중 연결리스트

원형 연결리스트는 NULL을 가리키는 노드가 존재하지 않습니다.

 

리스트의 n 번째 요소를 가장 빠르게 찾을 수 있는 구현 방법은?

배열, 단순연결리스트, 원형연결리스트, 이중연결리스트

배열을 역참조 하는 것이 실행속도가 가장 빠릅니다.

 

단순연결리스트의 노드들의 개수를 구하는 함수

int get_length(ListNode* head) {
	int count = 0;
	for (ListNode* p = head; p != NULL; p = p->link)
		count++;
	return count;
}

 

단순연결리스트의 노드들의 데이터 값의 합을 구하는 함수

int get_sum(ListNode* head) {
	int sum = 0;
	for (ListNode* p = head; p != NULL; p = p->link)
		sum += p->data;
	return sum;
}

 

단순연결리스트의 노드들의 데이터 값 중 최대값을 구하는 함수

int get_max(ListNode* head) {
	int maxNum = -32767; // INT_MIN
	for (ListNode* p = head; p != NULL; p = p->link) {
		if (p->data > maxNum)
			maxNum = p->data;
	}
	return maxNum;
}

 

단순연결리스트에서 특정한 데이터 값을 갖는 노드의 개수를 구하는 함수

int count(ListNode* head, int value) {
	int count = 0;
	for (ListNode* p = head; p != NULL; p = p->link) {
		if (p->data == value)
			count++;
	}
	return count;
}

 

단순연결리스트의 특정한 데이터 값을 갖는 노드들을 삭제하는 함수

ListNode* delete_node(ListNode* head, int value) {
	ListNode* pre = NULL;

	for (ListNode* p = head; p != NULL; pre = p, p = p->link) {
		if (p->data == value) {
			if (p == head) {
			ListNode* removed = head;
			head = head->link;
			free(removed);
			}
			else {
				pre->link = p->link;
				free(p);
				p = pre;
			}
		}
	}
	return head;
}

 

데이터를 리스트의 마지막에 삽입하는 함수(1)를 작성하고 이를 이용해 데이터 값이 오름차순으로 정렬된 두 단순 연결리스트를 병합하는 함수(2)를 작성하라 (기존의 두 리스트 list1, list2는 변경하지 않고, 병합된 결과는 새로운 리스트로 만들어 반환한다)

ListNode* insert_last(ListNode* head,var value){
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	if (head == NULL) {
		p->link = head;
		head = p;
	}
	else {
		ListNode* q = head;
		while (q->link != NULL) { q = q->link; }
		p->link = q -> link;
		q->link = p;
	}
	return head;
}
ListNode* merge(ListNode* list1, ListNode* list2) {
	ListNode* result = NULL;
	ListNode* p1 = list1, *p2 = list2;
	if (p1 == NULL) return list2;
	if (p2 == NULL) return list1;
	while (p1 != NULL && p2 != NULL) {
		if (p1->data < p2->data) {
			result = insert_last(result, p1->data);
			p1 = p1->link;
		}
		else {
			result = insert_last(result, p2->data);
			p2 = p2->link;
		}
	}
	while (p1 != NULL) {
		result = insert_last(result, p1->data);
		p1 = p1->link;
	}
	while (p2 != NULL) {
		result = insert_last(result, p2->data);
		p2 = p2->link;
	}
	return result;
}

 

주어진 단순 연결리스트에서 데이터 값이 홀수인 노드들을 추출하여 만들어진 단순 연결리스트를 반환하는 함수를 작성하라. (기존의 리스트 list는 변경하지 않고, 새로운 리스트를 만들어 반환한다.)

ListNode* odd_extract(ListNode* list)
{
	ListNode* oddList = NULL;
	ListNode* p;
	for (p = list; p != NULL; p = p->link)
	{
		if (p->data % 2 != 0) {
		oddList = insert_first(oddList, p->data);
		p = p->link;
		}
	}
	return oddList;
}