[C언어와 친구들] 구조체(Struct)와 연결리스트(Linked List) wow

0. typedef 문법

- typedef는 'type define'의 줄임 표현

- 기존 자료형 이름의 길이가 긴 경우 자료형을 재정의하여 사용하는 문법

- #define 과 비슷해 보이지만 다른 기능

- 배열, 포인터와 같은 형식도 재정의 가능

typedef int MY_DATA[5];
MY_DATA temp; // int temp[5]; 라고 선언한 것과 같음

int (*p)[5]; // 20바이트의 사용 범위를 가지는 포인터 변수

typedef int MY_DATA[5];
MY_DATA *p; // int (*p)[5]; 라고 선언한 것과 같음

typedef를 활용해서 새로운 AGE라는 자료형을 만들었다고 생각하면 됨.

---

1. 구조체(Struct)

- 사용자 정의 자료형 정의 방법 중 한 가지

- C언어는 크기나 형식이 다른 데이터를 그룹으로 묶어 사용할 수 있도록 '구조체(Structure)' 문법을 제공

 

배열은 C언어가 제공하는 가장 기본적인 자료구조이면서, 몇 없는 ... 그냥 다(?) 없는 C언어의 자료구조 중 하나라고 했었다. C의 자료구조인 배열은 하나의 배열에 동일한 형만 담을 수 있다. 예를 들어, int형 배열이면 int 값만, char형 배열이면 char 값만 들어간다. 그런데 하나의 자료형에 여러 자료형을 담을 수 있다? 이를 해결할 수 있는 방법이 바로 구조체이다.

 

구조체는 배열과는 전혀 다른 방식으로 여러 데이터를 구조화한다.

기존 자료형을 조합해 새로운 자료형을 정의할 수 있도록 허용하는 방식이다. 이때, 자료형을 새로 정의한다는 말을 잘 이해해야 하는데, 자료형을 정의하는 것을 구조체를 선언한다고 잘못 이해하는 경우가 발생한다. "선언"한다는 것은 컴파일러에게 메모리 공간의 확보를 지시하는 것이다. 따라서 구조체를 선언하기 위해서는 구조체를 정의한 이후에야 가능한 일이다. 즉, 구조체의 정의와 구조체의 선언은 다르다. From here..

 

💡정확하게 말하기 👻

구조체의 정의를 구조체라는 자료형을 선언한다고 하고, 구조체의 선언은 그냥 구조체의 선언이라고 하면 된다. 

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

// 구조체의 정의(구조체 자료형 선언)
typedef struct USERDATA {
    int age;
    char name[30];
    char phoneNo[30];
} USERDATA;

int main(){
    USERDATA user; // 구조체의 선언
    user.age = 10;
    strcpy(user.name, "Justin");
    strcpy(user.phoneNo, "01012345678");

    printf("%d_%s_%s\n", user.age, user.name, user.phoneNo);
    // 출력결과
    // 10_Justin_01012345678
    return 0;
}

* struct와 typedef를 조합해서 사용

: struct People이라는 구조체를 만들고, typedef를 이용해서 Person이라는 새로운 자료형을 만든 것

* 구조체 변수 선언

: struct People이라는 자료형을 만들고, Person이라는 새로운 변수를 만든 것

---

2. 구조체 포인터 변수 

- 구조체는 정의되면 이에 대응하는 포인터 변수 자료형도 자동적으로 정의(자료형 선언)된다고 이해할 수 있다.

- 구조체 포인터`로 선언된 경우 멤버를 지시할 때 '.'연산자가 아니라

멤버 지시와 '*'연산자 기능을 함께 가진 '->' 연산자를 사용한다는 점을 유의해야 한다. 

 

즉, '->' 화살표 연산자로 구조체 멤버에 접근할 수 있다. 매번 *과 ()로 사용하기 불편하기 때문에 ->를 사용하는 것이다.

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

// 구조체의 정의(구조체 자료형 선언)
typedef struct USERDATA {
    int age;
    char name[30];
    char phoneNo[30];
} USERDATA;

int main(){
    USERDATA * user; // 구조체 포인터의 선언

    user = (USERDATA *)malloc(sizeof(USERDATA)); // 구조체 포인터 초기화

    user->age = 10;
    strcpy(user->name, "dad");
    strcpy(user->phoneNo, "01012345678");

    printf("%d_%s_%s\n", user->age, user->name, user->phoneNo);

    free(user); // 동적 메모리 해제

    return 0;
}

구조체 포인터 변수도 일반 포인터 변수 그리고 함수 포인터 변수처럼 반드시 '초기화'를 해줘야지만 간접 액세스 연산자를 사용할 수 있다. 이는 초기화를 자동으로 해주는 배열 포인터 변수와 다른 점이다. 

---

3. 구조체의 요소는 같은 크기끼리 모아 주는 것이 좋다.

구조체의 크기를 구할 때에는 sizeof 연산자를 사용하는 것이 안전하다.

struct Test *p1 = (struct Test *)malloc(16); // 설정에 따라 오류 발생
struct Test *p2 = (struct Test *)malloc(sizeof(struct Test));

---

4. 구조체를 활용한 연결 리스트

- 배열: 정해진 숫자만큼 배열을 선언하여 숫자를 입력받음

- 동적 할당: 사용자에게 숫자의 개수를 입력 받아 그 개수만큼 메모리를 동적 할당하여 숫자를 저장

- 연결 리스트: 사용자가 입력한 모든 숫자를 저장하고 합산

 

💡if 여러 개의 숫자를 입력 받아서 합산하는 '더하기 프로그램'을 만든다고 가정 !

=> 사용자가 입력한 모든 숫자를 저장하려면, 사용자가 숫자를 입력할 때마다 그 숫자를 저장하는 동적 메모리를 하나씩 늘려가는 방법을 사용한다. 근데 여기서 문제점 !!!!!!💥💥💥💥💥💥

사용자가 입력한 숫자를 저장하기 위해 동적으로 할당된 메모리의 주소 값을 저장하려면 그 개수만큼 포인터가 필요하다. 

그 숫자를 기억하기 위한 포인터도 메모리 개수만큼 만들어야 할 것이니라.... ! 도 문제겠지만,

포인터가 늘어나면 '포인터 1'과 '포인터 2' 사이에도 서로 연결 고리가 있어야 연결이 유지가 되야하는데 그렇지 못 할 것이다. 

 

그래서 해결책 👍👍👍👍

=> '포인터 1'과 '포인터 2'를 가리키기 위해서 '숫자 1'과 '포인터 2'를 하나의 메모리로 묶어서 동적으로 할당 !

== 연결 리스트

이런 형식으로 자료를 관리하는 방법이 바로 연결 리스트(Linked List)이다. !!!!!!!!!! 와우

1) 연결 리스트의 노드를 구조체로 선언하기

Q. 노드가 뭐라고 생각하세요?

A. 노드가 말이죵 ....~

- 노드(Node): 연결 리스트에서 숫자와 포인터를 함께 저장하기 위해 할당한 메모리

노드란 말이죵 ~ '숫자 1'과 '포인터 2'를 하나의 메모리로 묶어서 동적으로 할당한 부분을 노드라고 생각하면 된다.

typedef struct node{ // 이 구조체를 연결 리스트에서 노드!!라고 함.
    int number;             // 숫자를 저장할 변수
    struct node *p_next;    // 다음 노드를 가리킬 포인터 
} Node;

 

2) 연결 리스트에 노드를 추가하며 이어가기

   1단계: 연결 리스트의 시작 상태

- 동적으로 할당되는 첫 노드의 주소 값을 저장해야 하기 때문에 포인터가 필요

- 연결 리스트의 시작점이 되는 포인터가 헤드 포인터 (Head Pointer)

연결 리스트이 시작점이 되는 포인터가 헤드 포인터이며 헤드 포인터는 노드가 아니다. 그리고 NULL로 초기값을 지정해준다. 

// 첫 노드를 가리킬 헤드 포인터를 선언하고 NULL을 초기값으로 대입
NODE *p_head = NULL;

 

   2단계: 숫자 12를 저장하기 위한 새 노드 추가

1) 사용자가 입력한 12라는 숫자를 저장하기 위해 새로운 노드를 추가

2) 새로운 노드를 위한 메모리를 malloc 함수를 사용해 동적으로 할당  => 노드 크기만큼 메모리 할당

3) 할당된 새 노드의 주소 값은 헤더 포인터에 저장

4) 할당된 노드의 number에는 12를 저장하고, p_next에는 NULL을 대입

원래 NULL 값이었던 헤드 포인터에 할당된 새 노드의 주소 값인 100번지의 주소가 헤더 포인터에 저장된 것을 확인할 수 있다. 할당된 노드의 number에는 12가 들어갔고 노드의 p_next에는 NULL이 들어감으로써 다음 노드가 없다는 것을 알 수 있다.

p_head = (NODE *)malloc(sizeof(NODE));
p_head->number = 12;    // 노드의 number에 값 12를 저장
p_head->p_next = NULL;  // 다음 노드가 없음을 명시

 

   3단계: 숫자 15를 저장하기 위한 새 노드 추가

1) 사용자가 입력한 15라는 숫자를 저장하기 위해 새로운 노드를 추가

2) 새로운 노드를 위한 메모리를 malloc 함수를 사용해 동적으로 할당 

3) 할당된 새 노드의 주소 값은 첫 노드의 p_next 포인터에 저장

4) 할당된 노드의 number에는 15를 저장하고, p_next에는 NULL을 대입

할당된 새 노드의 주소 값을 첫 노드의 p_next 포인터에 저장한다. 확인해보면 첫 번째 노드의 p_next에 두 번째 노드의 주소 값인 108번지가 저장된 것을 확인할 수 있다. 여기서 포커싱 할 점은 코드이다. 코드를 보면 p_head->p_next->p_next = NULL;과 같이 명시되어 있는데 있는 포인터의 개수가 늘어날 수록 가독성이 떨어질 것이다. 이를 해결하기 위해 반복문을 사용한다.

p_head = (NODE *)malloc(sizeof(NODE));
p_head->p_next->number = 15;    // 노드의 number에 값 15를 저장
p_head->p_next->p_next = NULL;  // 다음 노드가 없음을 명시

 

3) 반복문으로 연결 리스트에서 마지막 노드 탐색하기

추가적인 포인터를 더 사용하여  p->p_next가 NULL이 아닐 때까지 while문을 돌려 마지막 노드를 탐색한다.

// 반복문은 p_head에 저장된 주소 값에서 시작
NODE *p = p_head;

// p_next가 NULL일 때까지 반복. p_next 값이 NULL이면 마지막 노드라는 뜻
while(NULL != p->p_next){
    p = p->p_next; // p->p_next값을 p에 대입하면 p는 다음 주소로 이동
}

 

4) 조건을 체크하여 연결 리스트에 새로운 노드 추가하기

연결 리스트에 노드가 하나도 없는 경우에는 문제 발생하므로 예외 처리가 필요하다.

void AddNumber(NODE **pp_head, int data){
    NODE *p;
    if(NULL != **pp_head){
        p = **pp_head;
        while(NULL != p->p_next) p = p->p_next; // p->p_next값을 p에 대입하면 p는 다음 주소로 이동
        p->p_next = (NODE *)malloc(sizeof(NODE));
        p = p->p_next; // 새로 만든 노드의 주소 값을 p에 저장
    } else {
        *pp_head = (NODE *)malloc(sizeof(NODE));
        p = *pp_head; // 새로 만든 노드의 주소 값을 p에 저장
    }
    p->number = data; // 새 노드의 number에 data값을 저장
    p->p_next = NULL; // 다음 노드가 없음을 명시
}

NODE *p_head = NULL;
AddNumber(&p_head, 15);

 

5) 연결 리스트의 마지막 노드 기억하기

- 노드가 추가될 때마다 마지막 노드를 찾기 위해 탐색을 하면 노드가 많아질수록 수행시간이 점점 길어진다.

- 마지막 노드의 값을 기억하는 테일 포인터(Tail Pointer)를 사용

// 마지막 노드를 탐색하는 반복문이 필요하지 않음
while(NULL != p->p_next) p = p -> p_next;

void AddNumber(NODE **pp_head, NODE **pp_tail, int data)
{
    if(NULL != **pp_head){
        (*pp_tail)->p_next = (NODE *)malloc(sizeof(NODE));
        *pp_tail = (*pp_tail)->p_next; // 새로 만든 노드의 주소 값을 p에 저장
    } else {
        *pp_head = (NODE *)malloc(sizeof(NODE));
        *pp_tail = *pp_head; // 새로 만든 노드의 주소 값을 p에 저장
    }
    *pp_tail->number = data; // 새 노드의 number에 data값을 저장
    *pp_tail->p_next = NULL; // 다음 노드가 없음을 명시
}

 

6) 연결 리스트의 전체 노드 제거하기

- 프로그램이 끝날 때 동적으로 할당된 노드를 모두 제거해야 함

- 연결 리스트를 구성하는 노드를 탐색하여 하나씩 노드를 제거

NODE *p = p_head;
while(NULL!=p){
    freep(p);       // p가 가리키는 노드를 삭제
    p = p -> p_next; // 오류 발생: 다음 노드로 이동 불가
}

=> 이미 해제된 메모리를 사용하려 했기 때문에 오류 발생

=> 이동할 다음 노드의 주소를 미리 저장하여 문제를 해결

NODE *p = p_head, *p_save_next;
while(NULL!=p){
	// 새로운 포인트를 하나 만들고 주소를 저장해놓은 다음 지워야지 삭제된 뒤 연결 된다.
    p_save_next = p -> p_next; // 다음 노드의 주소를 미리 저장
    free(p);       // p가 가리키는 노드를 삭제
    p = p_save_next; // 다음 노드로 이동
}
p_head = p_tail = NULL; // 연결 리스트의 시작과 끝을 초기화

 

연결 리스트 친구들 ... 이진 트리... 이진 탐색 트리... 기다려라.... 내가 뿌수러 간다...

 

 

공부 참고 블로그

구조체와 객체: https://m.post.naver.com/viewer/postView.nhn?volumeNo=17986958&memberNo=21815

 'Do it! C언어 입문' - 18장 구조체와 연결리스트 (2/2):

https://www.youtube.com/watch?v=Q8OT_EdYMEo&list=PLiZvlxkcLhakQwbPjkyfuHFy1IVG-VXrP&index=30