개발하는데 다 이유가 있겠지

배열의 크기 조정하기

배열의 크기를 키우려면 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 값을 옮겨야 함

realloc() 함수를 통해 새로운 크기의 메모리를 다시 할당할 수 있음(확장 및 축소 가능)

• 기존 메모리의 내용은 유지하면서 메모리의 크기 변경 가능
• 새로 늘어난 부분의 값은 쓰레기 값
• 사용자가 요구한 크기만큼 연속되게 메모리를 확보할 수 없다면 해당 주소를 버리고 다른 공간에서 필요한만큼 메모리를 확보

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

int main(void)
{
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }

    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // tmp 포인터에 메모리를 할당하고 list의 값 복사
    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
    {
        return 1;
    }

    // list가 tmp와 같은 곳을 가리키도록 지정
    list = tmp;

    // 새로운 list의 네 번째 값 저장
    list[3] = 4;

    // list의 값 확인
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    //list 의 메모리 초기화
    free(list);
}

---

연결 리스트(Linked List)

각 인덱스의 메모리 주소에서 자신의 값과 바로 다음 값의 주소(포인터)를 저장

NULL은 0x0으로 표현 가능

연결 리스트 구조체

typedef struct node
{
    int number;
    struct node *next;
}
node;

• struct(구조체) : 자신만의 구조를 만들 수 있음
• .(점 연산자) : 속성값을 가져올 때 사용
• (역참조 연산자) : 메모리로 접근할 수 있음

시간 복잡도

• O(n) : 검색(Search), 삽입(Insert)

---

연결 리스트 코딩

• 장점
  • 각 원소에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해 연결되는 방식이기 때문에 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음
    (오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리)
  • 크기 변경이 유연하고 효율적으로 메모리를 사용할 수 있음
• 단점
  • 원소들이 메모리 물리주소에 연속으로 위치해있지 않아 특정 원소에 접근이 오래 걸림
  • 참조를 위해 추가적인 메모리 공간이 필요
• 종류
  • 단순 연결 리스트
  • 이중 연결 리스트
  • 원형 연결 리스트
  • 참고 : https://leejinseop.tistory.com/4

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

//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
    //node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다.
    int number; 

    //다음 node의 주소를 가리키는 포인터를  *next로 지정합니다.
    struct node *next;
}
node;

int main(void)
{
    // list라는 이름의 node 포인터를 정의합니다. 연결 리스트의 가장 첫 번째 node를 가리킬 것입니다. 
    // 이 포인터는 현재 아무 것도 가리키고 있지 않기 때문에 NULL 로 초기화합니다.
    node *list = NULL;

    // 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킵니다.
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number 필드에 1의 값을 저장합니다. “n->number”는 “(*n).numer”와 동일한 의미입니다. 
    // 즉, n이 가리키는 node의 number 필드를 의미하는 것입니다. 
    // 간단하게 화살표 표시 ‘->’로 쓸 수 있습니다. n의 number의 값을 1로 저장합니다.
    n->number = 1;

    // n 다음에 정의된 node가 없으므로 NULL로 초기화합니다.
    n->next = NULL;

    // 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꿔 줍니다.
    list = n;

    // 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당합니다.
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number와 next의 값을 각각 저장합니다.
    n->number = 2;
    n->next = NULL;

    // list가 가리키는 것은 첫 번째 node입니다. 
    //이 node의 다음 node를 n 포인터로 지정합니다.
    list->next = n;

    // 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장합니다.
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    n->number = 3;
    n->next = NULL;

    // 현재 list는 첫번째 node를 가리키고, 이는 두번째 node와 연결되어 있습니다. 
    // 따라서 세 번째 node를 더 연결하기 위해 첫 번째 node (list)의 
    // 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정합니다.
    list->next->next = n;

    // 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력합니다. 
    // 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료 조건이 됩니다.
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }

    // 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해줍니다.
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

---

연결 리스트 트리

노드(node)들의 연결을 2차원적으로 구성한 것(이진 검색 트리)

• 이진 검색 트리
  • 임의 접근이 불가능
  • 하나의 노드는 두 개의 자식 노드를 가짐
  • 왼쪽 자식 노드는 자신의 값보다 작고, 오른쪽 자식 노드는 자신의 값보다 큼
  • 검색 실행 시간, 노드 삽입 시간 : O(log n)
  • 가장 높은 층에서 트리가 시작되는 노트 : 루트 노드 (‘4’)
  • 루트 노드는 다음 층의 노드를 가리키는데 루트 노트보다 아래에 있는 노드 : 자식 노드(’2’, ‘6’ …)

이진 검색 함수 코드

//이진 검색 트리의 노드 구조체
typedef struct node
{
    // 노드의 값
    int number;

    // 왼쪽 자식 노드
    struct node *left;

   // 오른쪽 자식 노드
    struct node *right;
} node;

// 이진 검색 함수 (*tree는 이진 검색 트리를 가리키는 포인터)
bool search(node *tree)
{
    // 트리가 비어있는 경우 ‘false’를 반환하고 함수 종료
    if (tree == NULL)
    {
        return false;
    }
    // 현재 노드의 값이 50보다 크면 왼쪽 노드 검색
    else if (50 < tree->number)
    {
        return search(tree->left);
    }
    // 현재 노드의 값이 50보다 작으면 오른쪽 노드 검색
    else if (50 > tree->number)
    {
        return search(tree->right);
    }
    // 위 모든 조건이 만족하지 않으면 노드의 값이 50이므로 ‘true’ 반환
    else {
        return true;
    }
}

---

해시 테이블(Hash Table)**

연결 리스트의 배열
해시 함수(Hash function)를 사용해서 변환한 값을 index로 key와 value를 저장

• 임의 접근이 가능함
• 시간복잡도가 O(n)이지만 연결 리스트와 배열보다는 빠름
• 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문에 검색속도가 빠름

예를 들어 우리가 (Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인
해시 테이블에 저장한다고 하자.
그러면 먼저 index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다.
그리고 array[index] = "521-1234" 로 전화번호를 저장하게 된다.
이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로
매우 빠르게 데이터를 저장/삭제/조회할 수 있다.
해시테이블의 평균 시간복잡도는 O(1)이다.

출처 : https://mangkyu.tistory.com/102

---

트라이(Trie)

각 노드가 배열로 이루어진 ‘트리’형태의 자료 구조 / 문자열을 저장하고 효율적으로 탐색

장점

• 문자열 검색이 빠름
• 문자열 탐색 시 하나씩 전부 비교하면서 탐색하는 것보다 시간 복잡도 측면에서 효율적[O(1)]

단점

• 각 노드가 배열로 이루어져 저장 공간의 크기가 큼(메모리 측면에서 비효율적)

[자료구조] 트라이 (Trie)

---

스택, 큐, 딕셔너리

큐(Queue)

FIFO(First In, First Out / 선입선출)의 특징을 가진 자료 구조

• FIFO(First In, First Out / 선입선출) : 가장 먼저 들어온 값이 가장 먼저 나가는 것
• Enqueue(입력 동작) / Dequeue(출력 동작)

스택(Stack)

LIFO(Last In, First Out / 후입선출)의 특징을 가진 자료 구조

• LIFO(Last In, First Out / 후입선출) : 가장 마지막에 들어온 값이 가장 먼저 나가는 것
• Push(입력 동작) / Pop(출력 동작)

딕셔너리(Dictionary)

Key(키)와 Value(값)을 쌍으로 연결하여 데이터를 저장하는 자료 구조

• Key(키)는 중복되지 않음
• 순서가 없음(index가 없음)
• 수정이 가능함