Basic Concepts(2)

ADT Implementations

Two basic structures to implement ADT’s

1) 배열 기반 구현 — “index → element” 매핑

연속 메모리에 요소를 나란히 저장하여 인덱스로 즉시 접근한다.

시간 복잡도

연산	복잡도	비고
임의 접근 A[i]	O(1)	인덱스 직접 접근
끝에 삽입·삭제	O(1) amortized / 최악 O(n)	용량 2배(doubling) 전략 시 평균 O(1), 재할당 시 O(n)
중간 삽입·삭제	O(n)	뒤 요소 이동 필요
탐색	정렬 X: O(n) / 정렬 O: O(log n)	이분 탐색 가능(정렬 시)

장점

• 캐시 지역성 우수 → 실제 실행 속도 유리
• 오버헤드 작음(포인터 저장 불필요)

단점

• 크기 변경 비용(재할당/복사)
• 연속 공간 요구 → 큰 배열은 할당 실패 가능

전형적 용도

• 스택, 원형 큐(배열), 동적 배열(vector/ArrayList)
• 빈번한 랜덤 액세스가 필요한 경우

---

2) 연결 리스트 기반 구현 — “node → next의 위치” 저장

각 노드는 데이터와 다음 노드의 주소(포인터)를 가진다. 메모리는 불연속 가능.

시간 복잡도

연산	복잡도	비고
임의 접근	O(n)	앞에서부터 순차 추적
앞/뒤 삽입·삭제	O(1)	포인터 갱신만; 뒤 삽입 O(1) 보장엔 tail 유지
노드 위치 알고 있을 때 삽입/삭제	O(1)	참조 노드 주어짐
탐색	O(n)	선형 탐색

장점

• 크기 가변, 중간 삽입·삭제 빈번할 때 유리
• 연속 공간 불필요 → 외부 단편화에 덜 민감

단점

• 포인터 저장 오버헤드(단일/이중 링크에 따라 1~2개)
• 캐시 성능 저하(pointer chasing)
• 동적 할당/해제 비용, 파편화

전형적 용도

• 리스트 ADT에서 중간 삽입/삭제가 많을 때
• 연속 할당이 어려운 환경

---

3) 무엇을 언제 쓰는가 — 결정 규칙

• 랜덤 접근이 많다 → 배열
• 중간 삽입/삭제 빈번 → 연결 리스트
• 크기를 자주 키운다 → 둘 다 가능
  • 배열은 doubling으로 amortized O(1) 유지
  • 매우 큰 객체 복사 비용이 문제면 리스트
• 메모리 지역성/실행 속도가 중요 → 배열
• 연속 할당이 어려움 → 리스트

---

4) 대표 ADT를 두 뼈대로 구현할 때

ADT	배열 기반	리스트 기반
스택	top 인덱스 이동 → push/pop/top O(1) amortized	머리 삽입/삭제 → push/pop/top O(1)
큐	원형 버퍼로 head/tail 모듈러 갱신 → O(1)	head/tail 포인터 유지 → O(1)
순차 리스트(List)	접근 O(1) / 중간 삽입·삭제 O(n)	위치만 알면 삽입·삭제 O(1) / 접근 O(n)

---

5) 구현 시 주의(실전 팁)

• 배열 동적 확장: 용량 2배 전략으로 평균 O(1).
  축소는 히스테리시스(예: 사용률 1/4 이하에서만 축소)로 과도한 재할당 방지.
• 리스트 노드 크기: 데이터가 작을수록 포인터 오버헤드 비율↑.
  이중 연결 리스트는 포인터 2개.
• 캐시/분기 예측: 배열의 선형 순회 매우 빠름, 리스트는 pointer chasing 병목.
• 메모리 소유권: 리스트에 구조체 포인터를 저장할 때 해제 주체(policy)를 명확히 정할 것.

1. “랜덤 접근”의 의미

정의(알고리즘 관점): i가 매번 달라지는 상황에서 i번째 원소를 즉시 읽거나 쓰는 접근이 자주 발생하는 것.
→ 앞에서부터 차례로 스캔하는 순차 접근과 대비된다.

예

• 이분 탐색
• 힙의 인덱스 기반 부모/자식 참조
• DP 테이블에서 dp[i±k] 참조
• 배열 기반 그래프(인접행렬)에서 M[u][v] 질의

---

2. 배열이 랜덤 접근에 강한 이유

2.1 (a) 주소 계산이 O(1)

연속 메모리 + 고정 크기 요소 → 주소 계산: addr = base + i * sizeof(T)
CPU는 한 번의 주소 계산 + 한 번의 메모리 로드/스토어로 끝난다.
⇒ 시간 복잡도 O(1), 상수항도 작다.

2.2 (b) 포인터 추적이 없음

연결 리스트에서 k번째를 읽으려면 헤드부터 k번 포인터 역참조가 필요.
⇒ 기대 시간 O(k), 평균 O(n/2).

m개의 서로 다른 랜덤 인덱스를 질의하면 총 비용이 대략 O(m·n)까지 커질 수 있다.

2.3 (c) 하드웨어 효율

연속 배치 덕분에 캐시 / TLB / 프리페쳐가 잘 작동.
랜덤 인덱스더라도 “요소당 로드 1회”로 끝나는 경향.
반면 리스트는 노드당 데이터 + 다음 포인터 등 여러 로드와 분기 의존이 생긴다.
벡터화(SIMD), 분기 예측 측면에서도 배열이 유리.

---

3. 간단 비교 예시

3.1 배열

int x = A[i];    // i가 매번 바뀌어도 한 번에 O(1)
A[j] = 7;

3.2 단일 연결 리스트

typedef struct Node {
    int val;
    struct Node* next;
} Node;

int get_kth(Node* head, int k){ // 0-index
    for (int t = 0; t < k; ++t) head = head->next; // k번 포인터 추적
    return head->val;
}
// get_kth 자체가 O(k). m번 서로 다른 k를 요청받으면 총 Σk ≈ O(m·n).

---

4. 실제 수치 감각

n = 1,000,000, m = 1,000,000개의 임의 인덱스 조회:

• 배열: m회 × 1 로드 ≈ 1,000,000회 로드
• 리스트: 평균 n/2 ≈ 500,000 단계를 m번 → 5×10^11 회 포인터 추적
  ⇒ 차원이 다르다

---

5. 예외와 주의

• 가변 크기 요소
  가변 길이 문자열 등을 한 덩어리 배열에 섞어 저장하면 i번째의 시작 주소를 계산할 수 없어 O(1)이 깨진다.
  → 오프셋 테이블(인덱스 배열)을 별도로 둔다.

• 완전 랜덤 패턴 + 매우 큰 데이터
  데이터가 L3 캐시를 훨씬 넘으면 캐시 적중률은 낮아진다.
  그래도 배열은 요소당 1회 접근, 리스트는 노드마다 다수 접근 + 의존 체인이라 불리함은 유지.

---

6. 결론 — 의사결정 문장

• 임의 위치 참조가 빈번, k번째 요소를 자주 읽고/쓰는 문제 → 배열(동적 배열/vector) 권장.
• 중간 삽입/삭제가 압도적으로 많고, 접근이 주로 현재 위치 기준이면 → 연결 리스트 고려.

---

부록. 접근 패턴별 요약

A. 임의 접근 (random access)

• 배열: addr = base + i*sizeof(T) 한 번 계산 → 한 번의 메모리 로드로 끝. 사실상 “최대 한 번”.
• 연결 리스트: k번째를 보려면 head부터 next 포인터를 k번 따라감 → k번의 포인터 역참조 + 캐시 미스 가능성.
  결론: 임의 위치 접근이 잦으면 배열이 압도적으로 유리.

B. 순차 스캔 (one-pass scan)

• 이론상 둘 다 O(n).
• 배열은 데이터가 연속이라 캐시/프리페치가 잘 작동해 매우 빠름(루프당 단순 인덱스 증가).
• 연결 리스트는 매 원소마다 next 역참조 → 의존 체인 + 낮은 캐시 효율.
  일반적으로 배열이 더 빠름.

C. 언제 리스트가 낫나

• 중간 삽입/삭제가 매우 잦고, 그 지점의 노드 포인터를 이미 보유하고 있는 경우 → 그 자리에서 O(1) 삽입/삭제.
• 그 외(랜덤 접근·대량 스캔 중심)는 대체로 배열이 낫다.