1. 링크드리스트

링크드리스트를 배우는 이유

자료 저장할 때 많이 사용됨
큐, 스택,..
ex) 네트워크 상황에서 패킷이 엄청오는데 패킷이 도착하면 그것을 받고 그 명령어에 따라서 무언가 수행을 한다면 오는 패킷을 받아서 전부 큐에 넣는다.
근데 이 큐를 링크드 리스트 형식으로 보통 구현한다.

링크드리스트 구현하는 방법

1. 구조체생성

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

typedef struct data {
    int num;
    char name[20];
    struct data *next;
} data;

2. 초기생성

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

typedef struct data{
        int num;
        char name[20];
        struct data * next;
}data;

data * g_head = NULL;       //전역변수로 초기화
data * g_tail = NULL;       //전역변수로 초기화

// 노드 삽입
int insert(int num, char *name) {
    data *node = (data *)malloc(sizeof(data));
    if (!node) return 0;

    node->num = num;
    if (name != NULL) {
        strcpy(node->name, name);
    }
    node->next = NULL;

    if (!g_head) {
        // 큐가 비어 있을 때
        g_head = node;
        g_tail = node;
    }
    return 1;
}

3. 삽입

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

typedef struct data {
    int num;
    char name[20];
    struct data *next;
} data;

data *g_head = NULL;
data *g_tail = NULL;

// 노드 삽입
int insert(int num, char *name) {
    data *node = (data *)malloc(sizeof(data));
    if (!node) return 0;

    node->num = num;
    if (name != NULL) {
        strcpy(node->name, name);
    }
    node->next = NULL;

    if (!g_head) {
        // 큐가 비어 있을 때
        g_head = node;
        g_tail = node;
    } else {
        // 큐가 비어 있지 않을 때
        g_tail->next = node;
        g_tail = node;
    }
    return 1;
}
int main() {
    char name[20] = "";

    // 데이터 삽입
    for (int i = 0; i < 5; i++) {
        sprintf(name, "test%d", i);
        insert(i, name);
    }
}

4. 출력하기

ex) 큐

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

typedef struct data {
    int num;
    char name[20];
    struct data *next;
} data;

data *g_head = NULL;
data *g_tail = NULL;

// 모든 노드 출력
void printAll() {
    data *temp = g_head;
    while (temp) {
        printf("=====s====\n");
        printf("num : %d\n", temp->num);
        printf("name : %s\n", temp->name);
        printf("====e=====\n");
        temp = temp->next;
    }
}
// 노드 삽입
int insert(int num, char *name) {
    data *node = (data *)malloc(sizeof(data));
    if (!node) return 0;

    node->num = num;
    if (name != NULL) {
        strcpy(node->name, name);
    }
    node->next = NULL;

    if (!g_head) {
        // 큐가 비어 있을 때
        g_head = node;
        g_tail = node;
    } else {
        // 큐가 비어 있지 않을 때
        g_tail->next = node;
        g_tail = node;
    }
    return 1;
}

int main() {
    char name[20] = "";

    // 데이터 삽입
    for (int i = 0; i < 5; i++) {
        sprintf(name, "test%d", i);
        insert(i, name);
    }

    // 모든 데이터 출력
    printAll();
    return 0;
}

출력결과(큐)

=====s====
num : 0
name : test0
====e=====
=====s====
num : 1
name : test1
====e=====
=====s====
num : 2
name : test2
====e=====
=====s====
num : 3
name : test3
====e=====
=====s====
num : 4
name : test4
====e=====

5. 삭제(pop)

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

typedef struct data {
    int num;
    char name[20];
    struct data *next;
} data;

data *g_head = NULL;
data *g_tail = NULL;

// 모든 노드 출력
void printAll() {
    data *temp = g_head;
    while (temp) {
        printf("=====s====\n");
        printf("num : %d\n", temp->num);
        printf("name : %s\n", temp->name);
        printf("====e=====\n");
        temp = temp->next;
    }
}

// 첫 번째 노드 삭제 및 반환
data* pop() {
    if (!g_head) {
        printf("Queue is empty.\n");
        return NULL;
    }

    data *temp = g_head;
    g_head = g_head->next;

    // 큐가 비면 tail도 NULL로 설정
    if (!g_head) {
        g_tail = NULL;
    }

    temp->next = NULL; // 다른 연결 리스트와의 충돌 방지
    return temp;
}

// 노드 삽입
int insert(int num, char *name) {
    data *node = (data *)malloc(sizeof(data));
    if (!node) return 0;

    node->num = num;
    if (name != NULL) {
        strcpy(node->name, name);
    }
    node->next = NULL;

    if (!g_head) {
        // 큐가 비어 있을 때
        g_head = node;
        g_tail = node;
    } else {
        // 큐가 비어 있지 않을 때
        g_tail->next = node;
        g_tail = node;
    }
    return 1;
}

int main() {
    char name[20] = "";

    // 데이터 삽입
    for (int i = 0; i < 10; i++) {
        sprintf(name, "test%d", i);
        insert(i, name);
    }

    // 첫 번째 데이터 삭제 및 출력
    data *popped = pop();
    if (popped) {
        printf("=== Popped ===\n");
        printf("num : %d\n", popped->num);
        printf("name : %s\n", popped->name);
        printf("===============\n");
        free(popped);
    }

    // 모든 데이터 출력
    printAll();
    return 0;
}

6. 검색(search)

코드 예시

data * search(int targetNum){
	data *temp = g_head;
    
    while(temp){
    	if(temp->num == targetNum){
        	return temp;
        }
        temp = temp->next;
    }
	return NULL; //검색실패
}

사용 예시

int target = 5;
data *found = search(target);
if(found){
	printf("found num : %d\n",found->num);
    printf("found name : %s\n",found->name);
}else{
	printf("Number %d not found in the queue. \n",target);
}