시간복잡도 비교

6 min read

배열 vs 연결리스트 시간복잡도 비교

각 연산별 시간복잡도를 비교하고 왜 그런지 이해하기

시간복잡도 비교표

연산배열동적 배열단일 연결리스트이중 연결리스트
접근 (인덱스)O(1)O(1)O(n)O(n)
맨 앞 삽입O(n)O(n)O(1)O(1)
맨 뒤 삽입O(1)*O(1)**O(n)***O(1)
중간 삽입O(n)O(n)O(n)O(n)
맨 앞 삭제O(n)O(n)O(1)O(1)
맨 뒤 삭제O(1)*O(1)O(n)O(1)
중간 삭제O(n)O(n)O(n)O(n)****
탐색 (값)O(n)O(n)O(n)O(n)

* 공간 있을 때 ** Amortized O(1) *** tail 포인터 있으면 O(1) **** 노드 참조 있으면 O(1)

연산별 상세 분석

1. 접근 (Access)

배열: O(1)

arr[i]의 주소 = base + i * size
→ 한 번의 계산으로 바로 접근

연결리스트: O(n)

head에서 시작해서 i번 next를 따라가야 함
→ 최악의 경우 n번 이동

2. 맨 앞 삽입/삭제

배열: O(n)

삽입 전: [A][B][C][D][ ]
삽입 후: [X][A][B][C][D]

모든 요소를 한 칸씩 뒤로 이동해야 함

// 배열 맨 앞 삽입
void insertFirst(int[] arr, int value, int size) {
    for (int i = size; i > 0; i--) {
        arr[i] = arr[i-1];  // O(n) 이동
    }
    arr[0] = value;
}

연결리스트: O(1)

삽입 전: head -> [A] -> [B] -> [C]
삽입 후: head -> [X] -> [A] -> [B] -> [C]

포인터 2개만 변경

// 연결리스트 맨 앞 삽입
void insertFirst(Node newNode) {
    newNode.next = head;  // O(1)
    head = newNode;       // O(1)
}

3. 맨 뒤 삽입/삭제

동적 배열: Amortized O(1)

일반적: O(1) - 빈 공간에 추가
확장 시: O(n) - 전체 복사

분할 상환: 여러 연산의 평균 → O(1)

단일 연결리스트

삽입: O(n) (tail 없으면) / O(1) (tail 있으면)

// tail 없을 때 - O(n)
void insertLast(int data) {
    Node current = head;
    while (current.next != null) {  // O(n) 순회
        current = current.next;
    }
    current.next = new Node(data);
}
 
// tail 있을 때 - O(1)
void insertLast(int data) {
    tail.next = new Node(data);
    tail = tail.next;
}

삭제: O(n)

// 마지막 노드의 이전 노드를 찾아야 함
void deleteLast() {
    Node current = head;
    while (current.next.next != null) {  // O(n)
        current = current.next;
    }
    current.next = null;
    tail = current;
}

이중 연결리스트: O(1)

void deleteLast() {
    tail = tail.prev;     // O(1)
    tail.next = null;     // O(1)
}

4. 중간 삽입/삭제

공통: O(n)

  • 위치 탐색에 O(n) 필요
  • 배열: 요소 이동 추가
  • 연결리스트: 포인터 변경만
단, 연결리스트에서 노드 참조를 이미 가지고 있다면
→ 삽입/삭제 자체는 O(1)

5. 값 탐색

모두 O(n)

  • 정렬되지 않은 경우 처음부터 순회 필요
  • 정렬된 배열: 이진 탐색으로 O(log n) 가능

실제 성능 고려사항

캐시 효율성

배열:
┌────────────────────────────────┐
│ CPU가 arr[0] 읽을 때           │
│ → arr[0]~arr[15] 함께 캐시에   │
│ → 연속 접근 시 캐시 히트       │
└────────────────────────────────┘

연결리스트:
┌────────────────────────────────┐
│ 노드들이 메모리에 흩어져 있음   │
│ → 캐시 미스 빈번               │
│ → 실제 성능은 이론보다 나쁨    │
└────────────────────────────────┘

메모리 오버헤드

// 배열: 데이터만 저장
int[] arr = new int[100];  // 400 bytes
 
// 연결리스트: 데이터 + 포인터
class Node {
    int data;      // 4 bytes
    Node next;     // 8 bytes (64bit)
}
// 100개 노드 = 1200 bytes (3배)
 
// 이중 연결리스트
class Node {
    int data;      // 4 bytes
    Node prev;     // 8 bytes
    Node next;     // 8 bytes
}
// 100개 노드 = 2000 bytes (5배)

정리: 언제 무엇을 사용?

배열/ArrayList 선택

✓ 인덱스 접근이 잦음
✓ 데이터 크기가 예측 가능
✓ 순차 처리 (for 루프)
✓ 메모리 효율 중요

LinkedList 선택

✓ 앞쪽 삽입/삭제가 잦음
✓ 크기 예측 불가
✓ 중간 삽입/삭제가 잦고, 위치를 이미 알고 있음
✓ 양방향 순회 필요 (이중)

면접 포인트

  1. ArrayList와 LinkedList의 get(i) 차이는?

    • ArrayList: O(1) - 인덱스 계산
    • LinkedList: O(n) - 순차 탐색 (최적화로 양쪽에서)

  2. 왜 LinkedList의 중간 삽입도 O(n)인가?

    • 삽입 자체는 O(1)이지만
    • 위치를 찾는 데 O(n)이 필요

  3. 배열이 이론상 느린데 실제로 빠른 이유는?

    • CPU 캐시 효율성
    • 메모리 지역성 (Locality)
    • 브랜치 예측 가능성

  4. Java에서 어떤 상황에 LinkedList를 쓰나?

    • Queue/Deque로 사용할 때
    • 앞뒤 삽입/삭제가 주 연산일 때
    • 대부분의 경우 ArrayList가 더 나음

Backlinks