선택 기준

7 min read

배열 vs 연결리스트 선택 기준

상황에 따른 올바른 자료구조 선택 가이드

의사결정 플로우차트

데이터 구조 선택이 필요하다
         │
         ▼
┌─ 랜덤 접근이 자주 필요한가? ─┐
│                              │
▼ Yes                          ▼ No
배열                   ┌─ 앞쪽 삽입/삭제가 잦은가? ─┐
                       │                            │
                       ▼ Yes                        ▼ No
                   연결리스트            ┌─ 크기가 자주 변하는가? ─┐
                                         │                        │
                                         ▼ Yes                    ▼ No
                                    동적 배열                    배열

배열을 선택해야 할 때

1. 인덱스 기반 접근이 많을 때

// 배열: O(1)
int value = arr[1000];
 
// 연결리스트: O(n) - 1000번 이동
int value = list.get(1000);

예시 상황:

  • 행렬 연산
  • 이진 탐색
  • 동적 프로그래밍 테이블

2. 순차 처리가 주 작업일 때

// 배열: 캐시 효율 극대화
for (int i = 0; i < arr.length; i++) {
    sum += arr[i];  // 연속 메모리 → 캐시 히트
}
 
// 연결리스트: 캐시 미스 빈번
for (Node n = head; n != null; n = n.next) {
    sum += n.data;  // 흩어진 메모리 → 캐시 미스
}

3. 메모리 효율이 중요할 때

100만 개 int 저장 시:

배열: 4MB (4 bytes × 1,000,000)
연결리스트: 12MB+ (12 bytes × 1,000,000)
             └── data(4) + next(8)

3배 차이!

4. 크기가 고정되어 있을 때

// 미리 알려진 크기
int[] monthlyData = new int[12];
char[] buffer = new char[1024];

연결리스트를 선택해야 할 때

1. 앞쪽 삽입/삭제가 빈번할 때

// 배열: O(n) - 전체 이동
void insertFirst(int[] arr, int value) {
    for (int i = size; i > 0; i--) {
        arr[i] = arr[i-1];
    }
    arr[0] = value;
}
 
// 연결리스트: O(1) - 포인터만 변경
void insertFirst(int value) {
    Node newNode = new Node(value);
    newNode.next = head;
    head = newNode;
}

예시 상황:

  • 스택 구현 (LIFO)
  • 최근 항목 관리
  • 히스토리 기능

2. 중간 삽입/삭제가 빈번하고 위치를 알 때

// 이미 노드 참조를 가지고 있는 경우
void insertAfter(Node target, int value) {
    Node newNode = new Node(value);
    newNode.next = target.next;
    target.next = newNode;
    // O(1) - 위치 찾기 불필요
}

예시 상황:

  • LRU 캐시 (HashMap + LinkedList)
  • 에디터의 커서 위치 관리
  • 작업 스케줄러

3. 크기를 예측할 수 없을 때

// 배열: 재할당 필요
// 1만 → 2만 → 4만 ... 매번 전체 복사
 
// 연결리스트: 필요한 만큼만 할당
// 노드 하나씩 추가, 복사 없음

4. Queue/Deque로 사용할 때

// Java에서 Queue 사용
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);     // O(1)
queue.poll();       // O(1)
 
// Deque 사용
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);  // O(1)
deque.addLast(2);   // O(1)
deque.removeFirst();// O(1)
deque.removeLast(); // O(1)

동적 배열 (ArrayList) vs 연결리스트

ArrayList가 더 나은 경우 (대부분)

✓ 인덱스 접근 필요
✓ 끝에서 추가/삭제
✓ 순차 순회
✓ 메모리 효율 중요
✓ 캐시 성능 중요

LinkedList가 더 나은 경우

✓ 앞에서 자주 추가/삭제
✓ Queue/Deque 용도
✓ Iterator로 순회하면서 중간 삭제
✓ 참조를 유지하며 O(1) 삭제 필요

실무 사례

사례 1: 채팅 메시지 목록

요구사항:
- 새 메시지는 맨 아래 추가
- 스크롤로 특정 위치 이동
- 수천 개 메시지

선택: ArrayList (동적 배열)
이유:
- 스크롤 = 인덱스 접근 → O(1) 필요
- 맨 뒤 추가 → ArrayList도 O(1)

사례 2: 실행 취소 (Undo) 기능

요구사항:
- 작업마다 히스토리 추가
- Undo 시 마지막 작업 제거
- Redo 지원

선택: Deque (LinkedList 또는 ArrayDeque)
이유:
- 양쪽 끝에서만 작업
- 중간 접근 불필요

사례 3: LRU 캐시

요구사항:
- O(1) 조회
- O(1) 삽입
- O(1) 삭제 (가장 오래된 항목)
- O(1) 최신화 (사용된 항목을 맨 앞으로)

선택: HashMap + DoublyLinkedList
이유:
- HashMap: O(1) 조회
- LinkedList: O(1) 순서 변경, 삭제

class LRUCache {
    Map<Key, Node> map;
    DoublyLinkedList list;
 
    Value get(Key key) {
        Node node = map.get(key);  // O(1)
        list.moveToFront(node);    // O(1)
        return node.value;
    }
}

사례 4: 대용량 로그 처리

요구사항:
- 수백만 라인
- 순차 읽기
- 필터링 후 결과 저장

선택: ArrayList + Stream
이유:
- 순차 처리 → 캐시 효율
- 인덱스로 구간 처리 가능

성능 벤치마크 예시

100만 개 요소, 각 연산 1만 회:

                    ArrayList    LinkedList
─────────────────────────────────────────────
get(random)          0.5ms       ~500ms
add(last)            5ms         10ms
add(first)           ~500ms      2ms
remove(last)         2ms         3ms
remove(first)        ~500ms      2ms
sequential iterate   10ms        30ms

면접에서 자주 나오는 질문

Q1: 언제 LinkedList를 사용하나요?

"앞쪽에서 삽입/삭제가 빈번하거나,
Queue/Deque로 사용할 때입니다.
하지만 대부분의 경우 ArrayList가
캐시 효율 덕분에 더 빠릅니다."

Q2: ArrayList의 단점은?

"앞쪽 삽입/삭제가 O(n)이고,
용량 초과 시 재할당이 발생합니다.
하지만 분할 상환으로 평균 O(1)이고,
실제로는 연속 메모리 덕분에 빠릅니다."

Q3: 100만 개 데이터에서 어떤 걸 선택?

"사용 패턴에 따라 다릅니다:
- 인덱스 접근 많음 → ArrayList
- 앞쪽 삽입/삭제 많음 → LinkedList
- 순차 처리 → ArrayList (캐시 효율)

대부분 ArrayList가 답입니다."

정리

상황추천 자료구조
인덱스 접근 필요배열/ArrayList
앞쪽 삽입/삭제 빈번LinkedList
끝쪽 삽입/삭제만ArrayList
Queue/Deque 용도LinkedList 또는 ArrayDeque
메모리 효율 중요배열/ArrayList
크기 예측 불가ArrayList (자동 확장)
O(1) 중간 삭제 필요LinkedList (참조 있을 때)

Backlinks