배열vs동적배열vs연결리스트

✅ 선형 구조 vs 비선형 구조

📍 선형 구조 (Linear Structure)

• 자료가 순차적으로 나열된 구조
• 예: 배열, 동적 배열, 연결 리스트, 스택, 큐

📍 비선형 구조 (Non-Linear Structure)

• 하나의 자료 뒤에 다수의 자료가 연결되는 구조
• 예: 트리, 그래프

분류	구조	예시
선형	일대일 관계	배열, 연결 리스트, 스택, 큐
비선형	일대다 관계	트리(Tree), 그래프(Graph)

---

📦 배열 (Array)

💡 개념

• 연속된 메모리 공간을 미리 예약하여 데이터를 저장
• 고정 크기: 선언 시 크기 결정 → 이후 변경 불가

🏨 호텔 비유

"1인 1실 고정 방 예약제"
예: 3명 예약 시 301호~303호를 고정으로 계약

✅ 장점

• 빠른 접근 속도 (Random Access)
  → N번째 데이터를 바로 찾을 수 있음
• 캐시 친화적 (메모리 연속성 때문)

❌ 단점

• 크기 변경 불가
• 중간 삽입/삭제 비효율 (모든 데이터를 이동시켜야 함)

---

🧱 동적 배열 (Dynamic Array, std::vector)

💡 개념

• 크기를 유동적으로 확장 가능한 배열
• 메모리는 여전히 연속적으로 할당됨

📌 동적 배열 확장 정책

실제 필요한 크기보다 1.5~2배 더 크게 예약
→ 이사(복사) 횟수 최소화

🏨 호텔 비유

"3명 예약했지만, 2명 더 올 걸 대비해 5개 방 예약"
이사할 필요가 없도록 넉넉하게 잡아둠

✅ 장점

• 크기 확장 가능 (push_back 등)
• 메모리 재할당 최소화 전략

❌ 단점

• 중간 삽입/삭제 시 모든 요소 복사/이동
• 여전히 연속된 공간 필요 → 큰 데이터는 메모리 단편화 문제 가능

---

🔗 연결 리스트 (Linked List)

💡 개념

• 연속되지 않은 메모리 공간에서 각 노드가 포인터로 다음 노드를 가리킴
• 필요한 만큼만 동적으로 메모리 할당

🏨 호텔 비유

"301호, 405호, 507호를 예약하고, 각 방에 다음 방 번호 메모만 적어두는 구조"

✅ 장점

• 중간 삽입/삭제 O(1)
  (단, 위치를 알고 있어야 함 → iterator 사용)

❌ 단점

• 임의 접근(Random Access) 불가
  → N번째 데이터를 찾기 위해 처음부터 순차 탐색 필요

---

🔍 세 자료구조 비교

항목	배열	동적 배열	연결 리스트
메모리	연속	연속	비연속
크기	고정	유동적	유동적
접근 속도	빠름 (O(1))	빠름 (O(1))	느림 (O(n))
중간 삽입/삭제	느림 (O(n))	느림 (O(n))	빠름 (O(1), 위치 알고 있어야 함)
장점	빠른 접근	유연한 크기	삽입/삭제 용이
단점	크기 제한	중간 수정 느림	느린 임의 접근

---

🎯 실전 팁

• 대부분의 경우 std::vector(동적 배열) 사용
• 연결 리스트는 삽입/삭제 중심 알고리즘 학습에서 활용
• 면접 대비:

  배열 vs 벡터 vs 연결 리스트 차이 설명 + 예시 & 시간복잡도

---

📌 임의 접근(Random Access) 이란?

N번째 데이터에 직접 접근 가능한지 여부

자료구조	지원 여부	비고
배열	✅	arr[5] 가능
동적 배열	✅	vec[5] 가능
연결 리스트	❌	n번째 노드까지 순회 필요

---

🖼 이미지 예시 정리

자료구조	메모리 구조
배열	[301][302][303][304][305]
동적 배열	[301][302][303][(빈)][(빈)] → 확장 가능
연결 리스트	[301] → [405] → [507] (포인터 연결)
트리	[Root] / \ [L] [R]
그래프	Node들 간 자유 연결

---