[C] 싱글 링크드 리스트(Single Linked List)

□ 싱글 링크드 리스트란?

   ▷ Head노드를 기준으로 메모리를 동적할당하여 노드를 추가하며 데이터를 저장하고, 각 노드들은 데이터공간과 다음 노드의 주소를 가리키는 공간으로 구성되어있습니다

 

□ 싱글 링크드의 메모리구조

싱글링크드리스트 메모리 구조

   ▷ stack영역의 포인터가 동적할당(heap영역에 생성)한 노드를 가리키는 구조로 되어있으며, heap영역의 각 노드들은 다음 노드를 가리키고 있습니다. 

 

□ 싱글 링크드 리스트의 구현

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

//TODO 양쪽 끝에 더미노드를 만듦

typedef struct _list {
	int key;
	struct _list* next;
}List; //구조체 선언
List* head, * tail;

void init_list(void) {
	head = (List*)malloc(sizeof(List)); //왼쪽기둥
	tail = (List*)malloc(sizeof(List)); //오른쪽기둥
	head->next = tail;
	tail->next = tail;
} // 구조체 초기화(메모리할당)

    ▷ 구조체를 선언해준 후, head와 tail을 선언합니다. 그리고, head와 tail을 초기화해주는 함수를 만들어줍니다.

 

 

□ 노드 삽입

void insert_list(int data) {
	List* new1;
	new1 = (List*)malloc(sizeof(List));
	new1->key = data;
	new1->next = head->next;
	head->next = new1;
} //노드를 생성후 삽입

    ▷ 노드를 넣어주는 함수로, new1을 생성하여 메모리할당을 해주고, new1에 key와 다음 노드의 주소를 넣어줍니다.

      1. new1->next = head->next; 로 이전연결과 끊기 전에 이어줍니다.

      2. head의 다음에 추가하는 방식으로 만들었으므로, head->next = new1을 넣어줍니다.

 

□ 노드의 데이터 출력

void display_list(void) {
	List* cur;
	cur = head->next;
	printf("==================================\n");
	while (cur != tail) {
	printf("%d\n", cur->key);
	cur = cur->next;
	}
	printf("==================================\n\n");
} //노드를 돌면서 출력

    ▷ head부터 시작하여 노드들을 돌면서 안의 데이터를 출력합니다.

      1. cur를 선언후 head->next주소를 넣어줍니다.

      2. cur가 움직이며 노드 안의 데이터를 출력하고 cur와 tail이 만나면 탈출합니다.

□ 노드의 삭제

void delete_list(int data) {
	List* cur, * del;
	del = head;
	cur = head;
	while (cur != tail) {
		if (data == cur->next->key) {
			del = cur->next;
			cur->next = del->next;
			//del->next = NULL;
			free(del);
			printf("삭제되었습니다 \n\n");
			break;
		}
		cur = cur->next;
	}
	if (cur == tail) {
		printf("삭제할 데이터가 없습니다!\n\n");
	}
} // 노드의 삭제

    ▷ head부터 시작하여 노드들을 돌면서 안의 데이터를 출력합니다.

      1. cur와 del을 선언 후 head의 값을 넣어줍니다.

      2. cur = cur->next를 넣어주며 cur->next의 data와 입력받은 data를 비교합니다.

      3. 일치하는 data를 찾게 되면 del을 cur->next(찾은값)위치를 넣어줍니다.

      4. cur->next에 del->next의 주소를 넣어주어 삭제할 곳 다음과 이어줍니다.

      5. del이 있는 곳을 free(del)을 사용해 메모리를 제거해준 후 반목문을 탈출합니다.

      6. cur가 tail이 만나게되면 삭제할 데이터가 없으므로 반목문을 탈출합니다.

 

□ 전체 코드

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

// 대부분의 자료구조는 반드시 초기화
typedef struct _list {
	int key;
	struct _list* next;
}List;
List* head, * tail;
void init_list(void) {
	head = (List*)malloc(sizeof(List)); //왼쪽기둥
	tail = (List*)malloc(sizeof(List)); //오른쪽기둥
	head->next = tail;
	tail->next = tail;
}

void insert_list(int data) {
	List* new1;
	new1 = (List*)malloc(sizeof(List));
	new1->key = data;
	new1->next = head->next;
	head->next = new1;
}

void display_list(void) {
	List* cur;
	cur = head->next;
	printf("==================================\n");
	while (cur != tail) {
	printf("%d\n", cur->key);
	cur = cur->next;
	}
	printf("==================================\n\n");
}

void delete_list(int data) {
	List* cur, * del;
	del = head;
	cur = head;
	while (cur != tail) {
		if (data == cur->next->key) {
			del = cur->next;
			cur->next = del->next;
			//del->next = NULL;
			free(del);
			printf("삭제되었습니다 \n\n");
			break;
		}
		cur = cur->next;
	}
	if (cur == tail) {
		printf("삭제할 데이터가 없습니다!\n\n");
	}
}

main() {

	init_list(); // 리스트 자료구조의 초기화
	int sel=0;
	int a;
	while (sel != 4) {
		printf("수행할 작업을 입력하시오\n");
		printf("1. insert   2. display   3. delete  4. exit\n");
		scanf_s("%d", &sel);
		puts("");
		switch (sel)
		{
		a = 0;
		case 1: printf("리스트에 넣을 수를 입력하시오.\n");
				scanf_s("%d", &a);
				puts("");
				insert_list(a); break;
		case 2: display_list(); break;
		case 3: printf("삭제할 수를 입력하시오.\n");  
				scanf_s("%d", &a);
				puts("");
				delete_list(a); break;
		case 4: break;
		}


	}
}