자료구조 개요

이 Part에서 다루는 것

• 자료구조의 큰 분류: 선형 vs 비선형
• 선형 자료구조 3종의 핵심 차이
  • 배열(Array)
  • 동적 배열(Dynamic Array, vector)
  • 연결 리스트(Linked List)
• “실전에서 무엇을 먼저 선택할지” 판단 기준

학습 목표

• 왜 대부분의 일반 데이터 처리에서 동적 배열이 기본 선택인지 설명할 수 있다.
• 삽입/삭제/탐색/임의 접근 요구사항에 따라 배열·벡터·리스트를 구분해 선택할 수 있다.

---

자료구조의 큰 분류: 선형 vs 비선형

구분	관계	대표 구조	대표 문제
선형 구조	데이터가 한 줄로 이어짐(1:1 인접)	배열, 벡터, 리스트, 스택, 큐	순차 처리, 정렬/탐색
비선형 구조	한 노드에서 여러 방향으로 분기(1:다)	트리, 그래프	길찾기, 계층 구조

핵심 감각:

• 선형 구조는 “앞/뒤가 분명한 줄”을 다루는 데 강합니다.
• 비선형 구조는 파일 시스템/길찾기처럼 분기가 많은 문제에서 필요합니다.
• 하지만 기초 단계에서는 선형 구조 이해가 우선입니다.

---

배열(Array): 고정 크기 + 연속 메모리

호텔 비유로 보면:

• 미리 “연속된 방 N개”를 계약하는 방식
• 계약 후 크기를 바꾸기 어렵다

특징:

항목	내용
저장 방식	연속 메모리
크기	고정
임의 접근	매우 빠름 O(1)
중간 삽입/삭제	느림 O(N) (뒤 원소 이동 필요)

언제 적합한가:

• 크기가 거의 고정이고
• 인덱스로 빠르게 접근해야 할 때

---

동적 배열(Dynamic Array): 벡터의 핵심

동적 배열은 배열의 장점(연속 메모리 + 빠른 임의 접근)을 유지하면서,
크기 조절을 지원합니다.

핵심 개념: size vs capacity

• size: 실제로 사용 중인 원소 개수
• capacity: 재할당 없이 담을 수 있는 총 용량

왜 빠른가(평균적으로)

• 용량이 찰 때마다 보통 1.5~2배로 늘려 재할당
• 평소 삽입은 빠르고, 가끔 큰 비용(재할당/복사)이 발생
• 결과적으로 맨 뒤 삽입(push_back)은 평균(암화) O(1)로 봅니다.

특징 요약:

항목	내용
저장 방식	연속 메모리
크기	유동적 (size, capacity)
임의 접근	빠름 O(1)
중간 삽입/삭제	느림 O(N)
재할당	가끔 큰 비용 발생

실전 결론:

• 일반적인 C++ 컨테이너의 기본 선택은 보통 std::vector

---

연결 리스트(Linked List): 연결은 유연, 접근은 느림

호텔 비유로 보면:

• 방이 흩어져 있어도 상관없고
• 각 방이 “다음 방 주소(포인터)”를 들고 연결됨

핵심 특징:

항목	동적 배열	연결 리스트
임의 접근(인덱스)	O(1)	O(N)
중간 삽입/삭제(위치 노드 이미 알고 있을 때)	O(N)	O(1)
캐시 친화성	좋음(연속)	나쁨(비연속)

중요한 현실:

• “리스트는 삽입/삭제가 빠르다”는 말은 삽입 위치 노드를 이미 잡고 있을 때 이야기입니다.
• 실제로는 위치를 찾는 데 O(N)이 걸리는 경우가 많아, 전체 성능이 기대보다 안 나올 수 있습니다.

그래서 실무에서는:

• 일반 데이터 저장/순회/정렬에서는 벡터가 더 유리한 경우가 많습니다.
• 리스트는 특정 상황(잦은 노드 재배치, iterator 안정성 요구 등)에서만 선택적으로 사용합니다.

---

선택 가이드 (짧은 결론)

• 인덱스 접근이 많다 -> 배열/동적 배열
• 크기가 자주 늘고 줄어든다 -> 동적 배열(vector) 우선 검토
• 중간 노드 연결 변경이 매우 잦고, 위치 노드를 이미 알고 있다 -> 리스트 검토

체크 질문 (스스로 답해보기)

• vector의 size와 capacity는 무엇이 다른가?
• 연결 리스트가 “항상 삽입/삭제가 빠르다”는 말이 왜 반만 맞는가?
• 네 프로젝트에서 “기본 컨테이너”를 벡터로 두는 이유는 무엇인가?

---