2. Arrays & Structures (1)

Arrays & Structures

자료구조의 기본은 데이터를 효율적으로 저장하고 관리하는 방법을 배우는 것부터 시작함.
가장 기초적인 구조 :  배열(Array) & 구조체(Structure)

C의 경우 array를 기본으로 지원함.

---

- Arrays and Array ADT

배열(Array) 은 같은 자료형의 데이터를 연속된 메모리 공간에 저장하는 구조
Array ADT (Abstract Data Type) 로서 배열은 다음과 같은 연산을 지원함:

• insert(A, i, x) : i번째 위치에 x 삽입
• delete(A, i) : i번째 요소 삭제
• retrieve(A, i) : i번째 요소 반환
• update(A, i, x) : i번째 요소를 x로 변경
• length(A) : 배열의 크기 반환

배열의 장점은 인덱스를 이용한 빠른 접근 (O(1))
단점은 크기가 고정되어 있고 삽입/삭제가 비효율적 (O(n)) 이라는 점이다.

---

 - Array in C

C 언어에서 배열은 다음과 같이 선언하고 사용함

int arr[5] = {1, 2, 3, 4, 5};
printf("%d\n", arr[2]); // 출력: 3

• arr[0]은 첫 번째 원소
• 배열의 인덱스는 0부터 시작
• 배열 이름(arr)은 배열의 첫 번째 주소를 가리킴

메모리 구조상 arr[i]는 *(arr + i) 와 동일함

즉, 배열은 포인터(pointer) 와 매우 밀접한 구조다.

---

- Multi-dimensional Array (다차원 배열)

2차원 이상으로 확장된 배열 구조
예를 들어 2차원 배열은 행(row)과 열(column)로 구성됨.

int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};
printf("%d\n", matrix[1][2]); // 출력: 6

메모리상에서는 행이 먼저, 열이 나중에 저장되는 row-major order 방식으로 저장됨.
즉, matrix[1][2]는 내부적으로 *(matrix[0] + 1 * 열개수 + 2)로 계산된다.

---

- Dynamically Allocated Array

C에서 배열 크기를 런타임에 결정하고 싶을 때는 동적 메모리 할당을 사용한다.

 

- malloc()

int *arr = (int *)malloc(5 * sizeof(int));

• 초기화되지 않음 (쓰레기 값 존재)
• malloc은 지정한 크기만큼 메모리를 할당하고, 시작 주소를 반환함

- calloc()

int *arr = (int *)calloc(5, sizeof(int));

• 0으로 초기화됨
• 요소 개수와 크기를 따로 지정 가능

- realloc()

arr = (int *)realloc(arr, 10 * sizeof(int));

• 기존 메모리를 확장하거나 축소
• 기존 데이터는 유지됨

- free()

free(arr);

• 동적 할당된 메모리를 해제해야 메모리 누수를 방지할 수 있음

---

- Structures in C

구조체(Structure) 는 서로 다른 자료형을 하나로 묶을 수 있는 사용자 정의 데이터형

struct Person {
    char name[20];
    int age;
    float height;
};

 

구조체 변수 선언:

struct Person p1 = {"Alice", 25, 162.5};
printf("%s %d\n", p1.name, p1.age);

 

또는 typedef로 이름을 단축할 수 있음:

typedef struct {
    char name[20];
    int age;
} Person;

Person p2 = {"Bob", 30};

 

구조체는 논리적으로 관련 있는 데이터를 하나로 묶을 때 유용하다.
예: 학생 정보, 좌표, 복소수 등.

---

- Self-referenced Structures (자기참조 구조체)

구조체 안에서 자기 자신을 가리키는 포인터를 멤버로 포함할 수 있다.
이 개념은 연결 리스트(linked list) 의 핵심이 된다.

struct Node {
    int data;
    struct Node *next;
};

• next는 같은 구조체 타입(struct Node)을 가리킴
• 이런 구조를 사용하면 연속되지 않은 메모리에서도 데이터들을 연결할 수 있음

---

- List 

리스트(List) 는 배열과 달리 동적으로 크기가 변하는 선형 자료구조다.
대표적으로 연결 리스트(Linked List) 가 있음.

struct Node {
    int data;
    struct Node *next;
};

 

단일 연결 리스트 예시

struct Node *head = NULL;
head = (struct Node *)malloc(sizeof(struct Node));
head->data = 10;
head->next = NULL;

 

연결리스트의 장점	연결리스트의 단점
삽입/삭제가 빠름 (포인터만 변경) 크기 제한이 없음	인덱스 접근이 불가능 (O(n)) 추가적인 포인터 메모리가 필요함

 

---

 

개념	설명	시간복잡도 (접근 / 삽입)
배열(Array)	고정 크기, 인덱스로 빠른 접근	O(1) / O(n)
다차원 배열	행렬 등 표현에 사용	O(1) / O(n²)
동적 배열	실행 중 크기 변경 가능	O(1) / O(n)
구조체	여러 자료형 묶음	-
자기참조 구조체	연결 리스트 구현의 기반	-
연결 리스트	노드 기반 동적 자료구조	O(n) / O(1)