C언어 동적 할당과 연결 리스트

 

동적 할당 메모리의 개념

 

프로그램이 메모리를 할당받는 방법

-정적(static)

-동적(dynamic)

 

 

정적 메모리 할당

 

- 프로그램이 시작되기 전에 미리 정해진 크기의 메모리를 할당받는 것- 메모리의 크기는 프로그램이 시작하기 전에 결정ex) int score_s[100];- 처음에 결정된 크기보다 더 큰 입력이 들어온다면 처리하지 못함- 더 작은 입력이 들어온다면 남은 메모리 공간은 낭비됨

 

 

동적 메모리 할당

 

- 실행 도중에 동적으로 메모리를 할당받는 것- 사용이 끝나면 시스템에 메모리를 반납(full)

ex) score = (int *)               malloc(100*sizeof(int));

- 필요한 만큼만 할당(malloc)을 받고 메모리를 매우 효율적으로 사용

 

 

 

예제 1

#include <stdio.h>
#include <stdlib.h>  
// malloc, free, exit 등의 함수를 사용할 수 있도록 한다.

int main(void)
{
    int *list;
    list = (int*)malloc(3 * sizeof(int));   //동적 메모리 할당
    if (list == NULL) {  //반환값이 NULL인지 검사
    	printf("동적 메모리 할당 오류\n");
    	exit(1);   //exit(1)을 호출하여 프로그램을 종료. 1은 일반적으로 오류를 의미하는 종료 상태 코드
    }
    list[0] = 10;
    list[1] = 20;
    list[2] = 30;
    free(list);   //동적 메모리 해제
    return 0;
}

 

할당된 메모리 시작주소 : list

 

list = (int*)malloc(3 * sizeof(int));

 

: malloc 함수를 사용하여 메모리를 동적으로 할당

3 * sizeof(int)는 int형 변수 3개를 저장할 수 있는 크기의 메모리를 요청한다

sizeof(int)는 int형 변수의 크기를 바이트 단위로 반환한다

이 크기만큼의 메모리를 할당받아 list 포인터가 이를 가리키게 된다.

반환값은 void*형이므로 (int*)를 사용하여 int*형으로 형 변환

 

 

 

 

동적 메모리 사용

 

 

동적 메모리를 배열과 같이 취급

 

int *score = (int *) malloc (sizeof(int) * 10)

score[0] = 100;

score[1] = 200;

score[2] = 300;

...

 

할당된 메모리는 배열처럼 인덱스를 통해 접근할 수 있다.

 

• malloc 함수는 sizeof(int) * 10 바이트 만큼 메모리를 할당한다
• 여기서 sizeof(int)는 int형 변수의 크기(보통 4바이트)를 반환. 따라서 10 * 4 바이트 크기의 메모리가 할당된다
• malloc의 반환값은 void* 형이므로 (int *)로 형 변환하여 int*로 사용
• score는 포인터이지만 배열처럼 인덱스를 사용하여 접근할 수 있다. 이는 C에서 포인터와 배열이 매우 유사하게 동작하기 때문. score[i]는 *(score + i)와 같다.

 

 

포인터 연산으로도 사용 가능

 

*score = 100;

*(score+1) = 200;

*(score+2)  = 300;

...

 

• 할당된 메모리는 포인터 연산으로도 다룰 수 있다
• *(score + i)는 score[i]와 같다.
• 포인터 연산을 사용하여 배열의 요소에 접근하고 값을 할당할 수 있다.
• score + 3은 score 포인터를 3만큼 이동시킨 위치를 가리키며, 여기에 역참조 연산자 *를 사용하여 값을 설정

 

 

 

 

 

연결리스트 (linked list)

 

 

배열(array)

 

- 구현이 간단하고 빠르다는 장점이 있지만 크기가 고정되며 중간에서 삽입, 삭제가 어렵다는 단점이 있다. (유연성 떨어짐)

- 중간에 있는 데이터를 빠르게 가져올 수 있다는 장점이 있다. list[3]...

 

 

 

연결리스트(linked list)

 

- 각각의 원소(node)가 포인터를 사용하여 다음 원소(node)를 가리킨다(point한다). 

- 중간에 원소를 삽입하거나 삭제하기 용이하다 (필요할 때마다 동적으로 공간을 만들어서 추가)

- 중간에 있는 데이터를 빠르게 가져올 수 없고 앞에서부터 차례로 검색해야 한다. 구현이 어렵고 오류가 나기 쉽다.

 

 

 

노드와 포인터 생성하기

 

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

struct node{               //노드 생성
    int score;
    struct node* next;
};

void main()
{
    struct node* new_node;
    
    new_node = (struct node*) malloc (sizeof(struct node));   // 포인터 생성
    new_node -> score = 100;
    new_node -> next = NULL;
}

 

 

 

 

노드 생성하기

ex) 5명의 성적을 저장하는 연결 리스트

 

 

 

 

연결리스트 생성과정

#include <stdio.h>
#include <stdlib.h>
#define MAX_COUNT 5

struct node{
    int score;
    struct node* next;   // 다음 노드의 위치를 가리킴
};

void print_list(struct node* list_head)
{
    // 리스트의 내용을 모두 출력
    while(list_head != NULL) {
    	printf("%d => ", list_head->score);
        list_head = list_head -> next;
    }
    printf("\n")
}

void main()
{
    int count = 0;
    int tmp_score = 0;
    struct node* new_node;     // 새로운 노드 위치 저장할 포인터
    struct node* list_head = NULL;   // 리스트의 시작 노드
    
    while (count <  MAX_COUNT){
        // 사용자로부터 입력
        printf("score %d: ", count);
        scanf("%d", &tmp_score);
        
        // 1. 노드 생성
        new_node =
        	(struct node*) malloc (sizeof(struct node));
        new_node->score = tmp_score;
        
        // 2. 노드 연결
        new_node -> next = list_head;
        list_head = new_node;
        
        // 3. 리스트 출력
        print_list(list_head);
        count++;
    }
}

 

 

결과

 

score 0: 77

77 =>

score 1: 100

100 => 77  =>

score 2: 92

92 => 100 => 77 =>

score 3: 87

87 => 92 => 100 => 77 =>

score 4 : 95

95 => 87 => 92 => 100 => 77 =>

계속하려면 아무 키나 누르십시오 . . .

 

 

 

 

 

자료형을 재정의하는 방법 : typedef

 

- struct node를 node_t라는 이름의 자료형으로 정의

- int, double처럼 node_t로 사용

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_COUNT 5

typedef struct node {
    int score;
    struct node* next;
} node_t;

void print_list(node_t* list_head) {
    // 리스트의 내용을 모두 출력
    while (list_head != NULL) {
        printf("%d => ", list_head->score);
        list_head = list_head->next;
    }
    printf("\n");  // 세미콜론 추가
}

int main() {
    int count = 0;
    int tmp_score = 0;
    node_t* new_node;  // 새로운 노드 위치 저장할 포인터
    node_t* list_head = NULL;  // 리스트의 시작 노드
    node_t* temp;  // 임시 노드를 위해 사용

    while (count < MAX_COUNT) {
        // 사용자로부터 입력
        printf("score %d: ", count);
        scanf("%d", &tmp_score);

        // 1. 노드 생성
        new_node = malloc(sizeof(node_t));
        if (new_node == NULL) {
            fprintf(stderr, "Memory allocation failed\n");
            return 1;  // 메모리 할당 실패 시 종료
        }
        new_node->score = tmp_score;

        // 2. 노드 연결
        new_node->next = list_head;
        list_head = new_node;

        // 3. 리스트 출력
        print_list(list_head);
        count++;
    }

    // 동적으로 할당된 메모리 해제
    while (list_head != NULL) {
        temp = list_head;
        list_head = list_head->next;
        free(temp);
    }

    return 0;  // 정상 종료
}

 

 

 

 

성적을 기준으로 내림차순 출력하기 예제

 

- 학생 정보(학번, 이름, 성적)를 입력받고 성적순으로 정렬을 유지하는 프로그램 작성

- next_p라는 포인터로, 새로운 노드가 들어갈 위치(정렬될 수 있는 위치)를 찾아줌

 

struct node* list_head;
struct node* next_p;

newt_p = list_head;

while(next_p){
    if(next_p > score < new_node -> score)
    	break;
    next_p = newt_p -> next;
}

 

 

포인터가 들어갈 전 주소(prev_p)와 후 주소(next_p)가 두 개 다 필요하며 포인터 또한 두 개가 필요하다.

 

void main() {
    int count = 0;
    int tmp_score = 0;
    node_t* new_node;  // 새로운 노드 위치 저장할 포인터
    node_t* list_head = NULL;  // 리스트의 시작 노드
    node_t* next_p;
    node_t* prev_p;

    while (count < MAX_COUNT) {
        // 사용자로부터 입력
        printf("score %d: ", count);
        scanf("%d", &tmp_score);

        // 1. 노드 생성
        new_node = (node_t*) malloc (sizeof(node_t));
        new_node->score = tmp_score;
        
        // 2. 노드 삽입 위치 검색
        next_p = list_head; // 리스트 헤드부터 검색
        prev_p = NULL;  // prev_p는 NULL로 촟기화
        
        while(next_p){
             // 현재 노드의 score 값이 새 노드의 score 값보다 작으면
             // 새 노드를 현재 노드 앞에 삽입해야 하므로 루프 종료
            if(next_p -> score < new_node -> score)
            	break;
            // 현재 노드의 이전 노드를 업데이트
            prev_p = next_p;
            // 다음 노드로 이동
            next_p =  next_p -> next;
        }

        // 2. 노드 삽입
        new_node.next = next_p;   // 새 노드의 다음 노드는 현재 노드(next_p)를 가리킴
        
        if(prev_p){  // 현재 노드가 리스트의 중간에 삽입되었을 때
        	prev_p -> next = new_node;   // 현재 노드(prev_p)의 다음 노드를 새 노드로 업데이트
        } else {  //처음에 삽입할 때 prev_p는 null로 초기화되므로
        	list_head = new_node;   // 리스트의 시작 노드를 새 노드로 업데이트
        }
        
        // 3. 리스트 출력
        print_list(list_head);  // 리스트의 현재 상태를 출력
        count++;                // 다음 노드를 추가하기 위해 카운트 증가
    }
}