[자료구조] 단순 연결 리스트(Linked List) ADT + 예제들

(C언어로 쉽게 풀어쓴 자료구조 연결리스트 Lab + 추가 변형)

1. 과일의 이름을 저장하는 단순 연결 리스트 (p.200)

+ 사용자로부터 직접 문자열 입력 받기
+ 맨 앞의 노드에 해당하는 메모리를 반환하는 함수 delete_first 구현


* 주의할점

main 함수에서 저장된 각 동적 메모리를 반환하기 위해서
반복문을 이용하여 delete_first 함수를 호출할 때,
delete_first 함수 내에서 이미 메모리를 반환하고 head의 값이 변경되고 있다는 점을 유의하여 작성해야 함.

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

typedef struct { char name[100]; }element;
typedef struct {
	element data;
	struct ListNode* link;
}ListNode;

ListNode* insert_first(ListNode* head, element value) {
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));

	new_node->data = value;
	new_node->link = head;
	head = new_node;

	return head;
}
void print_list(ListNode* head) {
	for (ListNode* p = head;p != NULL;p = p->link) {
		printf("%s -> ", p->data.name);
		printf("NULL \n");
	}
}

ListNode* delete_first(ListNode* head) {
	if (head == NULL) {
		printf("마지막 노드\n");
		return NULL;
	}
	ListNode* p = head; // 첫번째 노드에 p 대입
	head = p->link;
	printf("\nfree(%s) \n", p->data.name);
	free(p);
	return head;
}

int main(void) {
	ListNode* head = NULL;
	element data;
	int i = 0l;
	while (1) {
		printf("과일 이름 입력(종료는 end) :  ");
		gets(data.name);
		if (strcmp(data.name, "end") == 0) break;
		head = insert_first(head, data);
		print_list(head);
		printf("\n");
	}

	while(head!=NULL){
		head = delete_first(head);
		print_list(head);
	}

	return 0;
}

결과:

 

2. 특정한 값을 탐색하는 함수 추가 구현(p.202)

+ 사용자로부터 문자열 입력받아 연결 리스트에서 해당 값 탐색하기


search_list() 함수는 다음과 같다.

int search_list(ListNode* head, element target) {
	for (ListNode* p = head;p != NULL;p = p->link) {
		if (strcmp(p->data.name, target.name)==0)
			return p;
	}
	return NULL;
}

전체 코드 :

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

typedef struct { char name[100]; }element;
typedef struct {
	element data;
	struct ListNode* link;
}ListNode;

ListNode* insert_first(ListNode* head, element value) {
	ListNode* new_node = (ListNode*)malloc(sizeof(ListNode));

	new_node->data = value;
	new_node->link = head;
	head = new_node;

	return head;
}
void print_list(ListNode* head) {
	for (ListNode* p = head;p != NULL;p = p->link) {
		printf("%s -> ", p->data.name);
		printf("NULL \n");
	}
}

ListNode* delete_first(ListNode* head) {
	if (head == NULL) {
		printf("마지막 노드\n");
		return NULL;
	}
	ListNode* p = head; // 첫번째 노드에 p 대입
	head = p->link;
	printf("\nfree(%s) \n", p->data.name);
	free(p);
	return head;
}

int search_list(ListNode* head, element target) {
	for (ListNode* p = head;p != NULL;p = p->link) {
		if (strcmp(p->data.name, target.name)==0)
			return p;
	}
	return NULL;
}

int main(void) {
	ListNode* head = NULL;
	element data;

	while (1) {
		printf("과일 이름 입력(종료는 end) :  ");
		gets(data.name);
		if (strcmp(data.name, "end") == 0) break;
		head = insert_first(head, data);
		print_list(head);
		printf("\n");
	}

	printf("\n찾고자 하는 과일 이름 :  ");
	gets(data.name);
	if (search_list(head, data))
		printf("\n리스트에서 %s 탐색 성공\n\n", data.name);
	else
		printf("\n리스트이서 %s 탐색 실패\n\n", data.name);


	while (head != NULL) {
		head = delete_first(head);
		print_list(head);
	}

	return 0;
}

결과:

 

3. 두 개의 리스트를 하나로 합치는 함수 구현(p.204)

 

4. 리스트를 역순으로 만드는 연산(p.206)

 

 

5. 사용자가 입력하는 값을 연결 리스트에 저장하고 데이터의 값들의 합 구하기, 탐색한 값 삭제하기(p.217 #9, 10, 11, 12, 13)

 

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

typedef int element;
typedef struct ListType {
	int size;
	struct ListNode* head;
	struct ListNode* tail;
}ListType;

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

// create
ListType* create() {
	ListType* list = (ListType*)malloc(sizeof(ListType));
	list->size = 0;
	list->head = list->tail = NULL;
	return list;
}

// error
void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// insert_last
void insert_last(ListType* list, element item) {
	ListNode* new = malloc(sizeof(ListNode));
	if (new == NULL) error("메모리 동적 할당 실패 \n");

	new->data = item;
	new->link = NULL;

	if (list->tail == NULL) {
		list->head = list->tail = new;
	}
	else {
		list->tail->link = new;
		list->tail = new;
	}
	list->size++;
}

// print_list
void print_list(ListType* list) {
	ListNode* p = list->head;
	for (int i = 0;i < list->size - 1;i++) {
		printf("%d->", p->data);
		p = p->link;
	}
	printf("%d\n", p->data);
}

// get_length
int get_length(ListType* list) { return list->size; }

// add
element add(ListType* list) {
	ListNode* p = list->head;
	element sum = 0;
	for (;p;p = p->link)
		sum += p->data;
	return sum;
}

int search(ListType* list, element key) {
	ListNode* p = list->head;
	int cnt = 0;

	for (;p;p = p->link)
		if (p->data == key) cnt++;
	return cnt;
}

void delete(ListType* list, element key) {
	ListNode* p, * next;
	
	p = list->head;
	while (p != NULL) {
		next = p->link;
		if(p->data==key) free(p);
		p = next; 
	}
	printf("연결 리스트에서 %d를 성공적으로 삭제했습니다.\n\n", key);
}

int main() {
	ListType* list;
	int n, data, key;
	
	list=create();

	printf("노드의 개수 : ");
	scanf("%d", &n);

	for (int i = 0;i < n;i++) {
		printf("노드 #%d 데이터 : ", i + 1);
		scanf("%d", &data);
		element item = data;
		insert_last(list, item);
	}

	print_list(list);
	printf("\n연결 리스트 노드의 개수 = %d\n\n", get_length(list));
	printf("연결 리스트의 데이터 합 : %d\n\n", add(list));
	
	printf("탐색할 값을 입력하시오: ");
	scanf("%d", &key);
	printf("%d는 연결 리스트에서 %d번 나타납니다.\n\n", key, search(list, key));
	
	delete(list, key);


	
	free(list);
}

 

 

 

6. 랜덤으로 생성한 정수 10개를 연결 리스트에 저장하고, 최솟값과 최댓값을 찾고, 오름차순으로 정렬하였다가 홀수번째 노드들을 삭제하고, 다시 내림차순으로 정렬(역순)하여 출력하기

(p.218-219 #15-16, #19)

 

// 랜덤으로 정수 생성하여 리스트에 저장 후, 최댓값과 최솟값 찾기
// 정렬하기
// 홀수번째 노드들이 전부 삭제되기

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

typedef int element;
typedef struct ListType {
	struct ListNode* head, * tail;
	int size;
}ListType;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// ListType 생성, 초기화
ListType* create() {
	ListType* new = (ListType*)malloc(sizeof(ListType));
	new->head = new->tail = NULL;
	new->size = 0;
	return new;
}

// add(insert_last)
void add(ListType* list, element item) {
	ListNode* new = (ListNode*)malloc(sizeof(ListNode));
	if (new == NULL) error("동적 메모리 할당 실패 \n");

	new->link = NULL;
	new->data = item;

	if (list->tail == NULL)
		list->head = list->tail = new;
	else {
		list->tail->link = new;
		list->tail = new;
	}
	list->size++;
}

void bubble_sort(ListType* list) {
	ListNode* p, * q;
	element tmp;

	for (p = list->head;p != NULL;p = p->link) {
		for (q = p;q != NULL;q = q->link) {
			if (p->data > q->data) {
				tmp = p->data;
				p->data = q->data;
				q->data = tmp;
			}
		}
	}
}

ListNode* reverse(ListType* list) {
	ListNode* p = list->head, * q = NULL, * r = q;

	while (p != NULL) {
		r = q;

		q = p;
		p = p->link;
		q->link = r;
	}
	list = q;
}

void delete(ListType* list, ListNode* prev) {
	ListNode* p = prev->link;
	prev->link = p->link;
	free(p);
}

ListType* delete_odd(ListType* list) {
	ListType* new = create();
	ListNode* p = list->head;

	// 짝수번째것만 저장하도록 함
	while(p!=NULL) {
		// 0, 2, 4, 6, 8 (홀수번째는 제외)
		p = p->link;
		add(new, p->data);
		p = p->link;
	}
	free(list);
	return new;
}

int get_length(ListType* list) { return list->size; }

void get_max_min(ListType* list) {
	ListNode* p = list->head;
	element max = p->data, min = p->data;

	for (p->link;p;p = p->link) {
		if (p->data > max) max = p->data;
		if (p->data < min)min = p->data;
	}
	printf("\n최댓값은 %d, 최솟값은 %d\n\n", max, min);
}

void print_list(ListType* list) {
	ListNode* p = list->head;

	for (int i = 0;i < list->size - 1;i++) {
		printf("%d -> ", p->data);
		p = p->link;
	}
	printf("%d\n", p->data);
}

int main() {
	// 랜덤으로 정수 생성하여 리스트에 저장 후, 최댓값과 최솟값 위치 찾기
	// 오름차순으로 정렬하고 출력하기
	// 홀수번째 노드들 전부 삭제하기 (새로운 노드 생성하도록 함)
	// 내림차순으로 변경 후 출력

	ListType* list;
	int randNum;

	list = create();

	srand(time(NULL));

	for (int i = 0;i < 10;i++) {
		randNum = rand() % 100;
		add(list, randNum);
	}
	printf("-------출력 -------\n");
	printf("리스트 요소 개수 : %d\n", get_length(list));
	print_list(list);

	get_max_min(list);

	bubble_sort(list);
	printf("\n------ 오름차순 정렬 -------\n");
	printf("리스트 요소 개수 : %d\n", get_length(list));
	print_list(list);

	list=delete_odd(list);
	printf("\n------ 홀수번째 노드 메모리 해제-------\n");
	printf("리스트 요소 개수 : %d\n", get_length(list));
	print_list(list);

	list->head = reverse(list);
	printf("\n------ 역순 -------\n");
	printf("리스트 요소 개수 : %d\n", get_length(list));
	print_list(list);
}

 

 

 

7. 두 개의 연결리스트에 랜덤으로 숫자 5개씩 저장하고, 오름차순으로 정렬한뒤, 두 연결리스트를 하나로 병합한 새로운 오름차순 정렬된 연결리스트 생성하기 (p.218 #17-18)

 

 

// 랜덤 생성한 번호들 5개씩 연결리스트에 생성
// 오름차순으로 두 연결리스트 각각 정렬
// 두개의 단순 연결 리스트 a,b(오름차순으로 정렬) 를 다시 새로운 오름차순 c 연결리스트 생성

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

typedef int element;
typedef struct ListType {
	struct ListNode* head, * tail;
	int size;
}ListType;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// ListType 생성, 초기화
ListType* create() {
	ListType* new = (ListType*)malloc(sizeof(ListType));
	new->head = new->tail = NULL;
	new->size = 0;
	return new;
}

// add(insert_last)
void add(ListType* list, element item) {
	ListNode* new = (ListNode*)malloc(sizeof(ListNode));
	if (new == NULL) error("동적 메모리 할당 실패 \n");

	new->link = NULL;
	new->data = item;

	if (list->tail == NULL)
		list->head = list->tail = new;
	else {
		list->tail->link = new;
		list->tail = new;
	}
	list->size++;
}

void bubble_sort(ListType* list) {
	ListNode* p, * q;
	element tmp;

	for (p = list->head;p != NULL;p = p->link) {
		for (q = p;q != NULL;q = q->link) {
			if (p->data > q->data) {
				tmp = p->data;
				p->data = q->data;
				q->data = tmp;
			}
		}
	}
}

int get_length(ListType* list) { return list->size; }

void merge(ListType* list1, ListType* list2, ListType* list3) {
	ListNode* head1 = list1->head;
	ListNode* head2 = list2->head;

	while (head1 && head2) {
		if (head1->data == head2->data) {
			add(list3, head1->data);
			head1 = head1->link;
			head2 = head2->link;
		}
		else if (head1->data < head2->data) {
			add(list3, head1->data);
			head1 = head1->link;
		}
		else {
			add(list3, head2->data);
			head2 = head2->link;
		}
	}

	for (;head1;head1 = head1->link)
		add(list3, head1->data);
	for (;head2;head2=head2->link)
		add(list3, head2->data);
}

void print_list(ListType* list) {
	ListNode* p = list->head;

	for (int i = 0;i < list->size - 1;i++) {
		printf("%d -> ", p->data);
		p = p->link;
	}
	printf("%d\n", p->data);
}

int main() {
	ListType* list1, *list2, *list3;
	int randNum;

	list1 = create();
	list2 = create();
	list3 = create();
	
	srand(time(NULL));

	for (int i = 0;i < 5;i++) {
		randNum = rand() % 100;
		add(list1, randNum);
	}
	for (int i = 0;i < 5;i++) {
		randNum = rand() % 100;
		add(list2, randNum);
	}

	bubble_sort(list1); bubble_sort(list2);
	printf("\n------ 오름차순 정렬후 출력 -------\n");
	printf("리스트 요소 개수 : %d\n", get_length(list1));
	print_list(list1);
	printf("\n------ 오름차순 정렬후 출력 -------\n");
	printf("리스트 요소 개수 : %d\n", get_length(list2));
	print_list(list2);

	merge(list1, list2, list3);
	printf("\n------ 오름차순 정렬후 출력 -------\n");
	printf("리스트 요소 개수 : %d\n", get_length(list3));
	print_list(list3);

	free(list1);free(list2);free(list3);
}