# 내부 저장 구

내부 저장조(Internal Storage Structure)는 프로그래밍 및 데이터 구조 분야에서 데이터가 메모리 상에 어떻게리적으로 저장되고 조직되는지를 설명하는 개념이다. 이는 특정 데이터 구조(Data Structure)의 성능, 접근 속도, 메모리 사용 효율성에 직접적인 영향을 미치며, 알고리즘 설계와스템 최적화의 핵심 요소로 작용한다. 본 문서에서는 내부 저장 구조의 기본 개념, 주요 유형, 저장 방식의 차이점, 그리고 실제 프로그래밍 언어에서의 구현 사례를 중심으로 설명한다.

---

## 개요

데이터 구조는 정보를 효율적으로 저장하고 조작하기 위한 논리적 틀이지만, 실제로 컴퓨터가 데이터를 처리할 때는 이 논리적 구조를 물리적인 메모리 공간에 매핑해야 한다. 이 과정에서 사용되는 방식이 바로 **내부 저장 구조**이다. 내부 저장 구조는 데이터의 위치, 배열 방식, 메모리 할당 전략 등을 포함하며, 프로그램의 실행 속도와 리소스 사용량에 큰 영향을 준다.

예를 들어, 배열(Array)과 연결 리스트(Linked List)는 동일한 데이터를 저장할 수 있지만, 내부 저장 구조가 다르기 때문에 삽입, 삭제, 접근 등의 연산에서 성능 차이가 발생한다.

---

## 주요 내부 저장 구조 유형

### 1. 연속 저장 구조 (Contiguous Storage)

연속 저장 구조는 데이터 요소들이 메모리 상에 **연속된 공간**에 저장되는 방식이다. 가장 대표적인 예는 **배열**이다.

#### 특징:
- **빠른 접근**: 인덱스를 통해 O(1) 시간에 접근 가능.
- **메모리 할당**: 고정 크기 또는 동적 할당(예: C++의 `std::vector`).
- **삽입/삭제 비용**: 중간에 삽입 또는 삭제 시, 나머지 요소들을 이동해야 하므로 O(n) 소요.

#### 예시:
```cpp
int arr[5] = {10, 20, 30, 40, 50};
// 메모리 상에서 10, 20, 30, 40, 50이 연속된 주소에 저장됨
```

---

### 2. 비연속 저장 구조 (Non-contiguous Storage)

비연속 저장 구조는 데이터 요소들이 메모리 상에 **분산되어 저장**되며, 각 요소는 다음 요소의 주소(포인터)를 포함하여 연결된다. 대표적인 예는 **단일 연결 리스트**(Singly Linked List)와 **이중 연결 리스트**(Doubly Linked List)이다.

#### 특징:
- **유연한 크기**: 필요 시 동적으로 노드를 추가/삭제 가능.
- **접근 속도 느림**: 순차 탐색이 필요하므로 O(n) 시간 소요.
- **삽입/삭제 효율적**: 특정 위치에서 O(1) 삽입/삭제 가능 (단, 위치 탐색은 별도).

#### 예시 (C 구조체 기반):
```c
struct Node {
    int data;
    struct Node* next;
};
```

---

### 3. 인덱스 기반 저장 구조

해시 테이블(Hash Table)과 같은 자료구조는 **해시 함수**를 사용하여 키(Key)를 인덱스로 변환하고, 해당 인덱스 위치에 값을 저장한다. 이는 내부적으로 배열을 기반으로 하되, 논리적 키와 물리적 주소를 매핑하는 구조이다.

#### 특징:
- **평균 O(1) 탐색**: 이상적인 해시 함수 사용 시.
- **충돌 처리 필요**: 체이닝(Chaining) 또는 오픈 어드레싱(Open Addressing) 방식 사용.

---

## 저장 구조의 비교

| 구조 유형 | 접근 속도 | 삽입/삭제 | 메모리 효율 | 사용 사례 |
|----------|----------|-----------|--------------|-----------|
| 배열 (연속) | O(1) | O(n) | 높음 | 정적 데이터, 매트릭스 |
| 연결 리스트 (비연속) | O(n) | O(1)* | 중간 | 동적 데이터, 큐/스택 |
| 해시 테이블 | 평균 O(1) | 평균 O(1) | 낮음~중간 | 딕셔너리, 캐시 |

> *: 특정 노드를 이미 알고 있을 경우

---

## 프로그래밍 언어별 내부 저장 구조 사례

### Python: 리스트와 딕셔너리
- **리스트**: 동적 배열 기반 (C에서의 `PyListObject` 구조체 사용). 내부적으로 여유 공간을 확보하여 추가 시 재할당 빈도를 줄임.
- **딕셔너리**: 해시 테이블 기반. Python 3.6+부터는 삽입 순서 유지 기능이 내장됨.

### Java: `ArrayList` vs `LinkedList`
- `ArrayList`: 배열 기반, 연속 저장.
- `LinkedList`: 노드 기반 비연속 저장.

### C++: `std::vector`와 `std::list`
- `std::vector`: 동적 배열, 연속 저장.
- `std::list`: 이중 연결 리스트, 비연속 저장.

---

## 최적화 고려사항

1. **캐시 친화성 (Cache Locality)**  
   연속 저장 구조는 CPU 캐시 효율이 높아 성능이 우수하다. 데이터가 인접해 있을수록 캐시 미스(cache miss)가 줄어든다.

2. **메모리 조각화 (Fragmentation)**  
   비연속 저장 구조는 빈번한 할당/해제로 인해 메모리 조각화를 유발할 수 있다.

3. **가비지 컬렉션 영향**  
   자바나 파이썬 같은 언어에서는 비연속 구조가 가비지 컬렉션에 더 큰 부담을 줄 수 있음.

---

## 참고 자료 및 관련 문서

- Cormen, T. H., et al. (2009). *Introduction to Algorithms*. MIT Press.  
- Sedgewick, R. (2011). *Algorithms*. Addison-Wesley.  
- [C++ Standard Library - cppreference.com](https://en.cppreference.com)  
- [Python Data Model - docs.python.org](https://docs.python.org/3/reference/datamodel.html)

---

내부 저장 구조는 데이터 구조의 성능을 결정짓는 핵심 요소이며, 시스템 설계 시 반드시 고려되어야 한다. 적절한 저장 방식의 선택은 응용 프로그램의 효율성과 확장성에 직접적인 영향을 미친다.