전체 목록
자료구조Easy#26

Array와 Linked List의 차이점을 시간/공간 복잡도 관점에서 설명해주세요.

#자료구조#Array#LinkedList#복잡도
힌트

임의 접근, 삽입/삭제 연산의 비용을 생각해보세요.

정답 및 해설

Array와 Linked List의 차이점을 시간/공간 복잡도 관점에서 설명해주세요.

Array(배열)와 Linked List(연결 리스트)는 가장 기본적인 선형 자료구조입니다. 두 자료구조는 메모리 저장 방식이 근본적으로 달라, 각 연산의 시간/공간 복잡도에서 명확한 차이를 보입니다. 어떤 자료구조를 선택하느냐에 따라 프로그램의 성능이 크게 달라질 수 있습니다.

Array (배열)

메모리 구조

배열은 연속된 메모리 공간에 요소들을 저장합니다. 배열을 생성할 때 운영체제로부터 연속된 메모리 블록을 할당받고, 모든 요소는 고정된 크기로 인접하여 저장됩니다.

메모리 주소: 1000  1004  1008  1012  1016
배열 요소:  [ 10 ][ 20 ][ 30 ][ 40 ][ 50 ]
인덱스:       [0]   [1]   [2]   [3]   [4]

인덱스 i의 요소 주소 = 시작 주소 + i × 요소 크기

이 단순한 공식 덕분에 임의의 인덱스에 O(1) 로 즉시 접근할 수 있습니다.

시간 복잡도

연산시간 복잡도설명
접근 (Access)O(1)인덱스로 직접 계산
탐색 (Search)O(n)순차 탐색 필요
삽입 (Insert) - 끝O(1)단순 추가
삽입 (Insert) - 중간/앞O(n)요소 이동 필요
삭제 (Delete) - 끝O(1)단순 제거
삭제 (Delete) - 중간/앞O(n)요소 이동 필요

삽입/삭제 시 요소 이동

# 인덱스 2에 99 삽입하는 경우
arr = [10, 20, 30, 40, 50]

# 삽입 전: [10, 20, 30, 40, 50]
# 인덱스 2 이후 요소들을 모두 오른쪽으로 이동
# [10, 20, _, 30, 40, 50]
# [10, 20, 99, 30, 40, 50]  <- 총 n-2회 이동 발생

arr.insert(2, 99)
print(arr)  # [10, 20, 99, 30, 40, 50]

캐시 친화성 (Cache Friendliness)

배열은 연속된 메모리 배치 덕분에 CPU 캐시를 효율적으로 활용합니다. 배열의 한 요소에 접근하면 인접한 요소들도 캐시 라인에 함께 로드되어, 순차 접근 시 캐시 히트율이 높습니다.

캐시 라인 (64 bytes): [arr[0], arr[1], arr[2], ..., arr[15]]
                        ↑ 한 번에 캐시에 로드됨

이 특성 때문에 실제 성능에서 배열이 연결 리스트보다 유리한 경우가 많습니다.

Linked List (연결 리스트)

메모리 구조

연결 리스트는 비연속적인 메모리에 노드(Node)를 분산 저장합니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성됩니다.

노드 구조:
+--------+------+
|  data  | next |
+--------+------+

메모리상 배치 (비연속):
[data:10 | ptr:→] ... [data:20 | ptr:→] ... [data:30 | ptr:null]
  주소 1000             주소 2048             주소 3512

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # 다음 노드를 가리키는 포인터

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

시간 복잡도

연산시간 복잡도설명
접근 (Access)O(n)head부터 순차 탐색
탐색 (Search)O(n)순차 탐색 필요
삽입 - 맨 앞O(1)head 포인터만 변경
삽입 - 위치 알 때O(1)포인터 조작만 필요
삽입 - 위치 모를 때O(n)탐색 후 삽입
삭제 - 맨 앞O(1)head 포인터만 변경
삭제 - 위치 알 때O(1)포인터 조작만 필요

삽입/삭제의 O(1) 원리

# 특정 노드 뒤에 삽입 - 포인터 조작만으로 O(1)
def insert_after(prev_node, data):
    new_node = Node(data)
    new_node.next = prev_node.next  # 새 노드의 next = 기존 다음 노드
    prev_node.next = new_node       # 이전 노드의 next = 새 노드
    # 요소 이동 전혀 없음!

# 특정 노드 삭제 - 포인터 조작만으로 O(1)
def delete_after(prev_node):
    if prev_node.next:
        prev_node.next = prev_node.next.next  # 다음 노드를 건너뜀

공간 복잡도 비교

배열 (int 5개):
[10][20][30][40][50]
= 5 × 4 bytes = 20 bytes

단순 연결 리스트 (int 5개, 64bit 포인터):
[10|ptr][20|ptr][30|ptr][40|ptr][50|null]
= 5 × (4 + 8) bytes = 60 bytes  ← 포인터로 인한 오버헤드

연결 리스트는 각 노드마다 포인터 공간이 추가로 필요하여 배열보다 메모리를 더 사용합니다. 이중 연결 리스트(Doubly Linked List)의 경우 노드당 포인터가 2개이므로 오버헤드가 더 커집니다.

연결 리스트의 종류

단순 연결 리스트 (Singly Linked List)

head → [1|→] → [2|→] → [3|→] → [4|null]

이중 연결 리스트 (Doubly Linked List)

head → [null|1|→] ↔ [←|2|→] ↔ [←|3|→] ↔ [←|4|null]

이전 노드로도 이동 가능. 삭제 시 이전 노드를 O(1)에 찾을 수 있어 유리합니다.

원형 연결 리스트 (Circular Linked List)

head → [1|→] → [2|→] → [3|→] → [4|→] → (다시 head로)

마지막 노드가 첫 번째 노드를 가리킵니다. 순환 처리에 유용합니다.

실제 코드 비교 (Java)

import java.util.ArrayList;
import java.util.LinkedList;

public class DataStructureComparison {
    public static void main(String[] args) {
        int SIZE = 100_000;

        // ArrayList (내부적으로 배열 사용)
        ArrayList<Integer> arrayList = new ArrayList<>();
        long start = System.nanoTime();
        for (int i = 0; i < SIZE; i++) {
            arrayList.add(0, i);  // 맨 앞에 삽입: O(n)
        }
        System.out.println("ArrayList 앞 삽입: " + (System.nanoTime() - start) + "ns");

        // LinkedList
        LinkedList<Integer> linkedList = new LinkedList<>();
        start = System.nanoTime();
        for (int i = 0; i < SIZE; i++) {
            linkedList.addFirst(i);  // 맨 앞에 삽입: O(1)
        }
        System.out.println("LinkedList 앞 삽입: " + (System.nanoTime() - start) + "ns");

        // 임의 접근 비교
        start = System.nanoTime();
        for (int i = 0; i < SIZE; i++) {
            arrayList.get(i);  // O(1)
        }
        System.out.println("ArrayList 임의 접근: " + (System.nanoTime() - start) + "ns");

        start = System.nanoTime();
        for (int i = 0; i < SIZE; i++) {
            linkedList.get(i);  // O(n) - 매우 느림
        }
        System.out.println("LinkedList 임의 접근: " + (System.nanoTime() - start) + "ns");
    }
}

선택 기준

Array를 선택해야 할 때

  • 인덱스 기반의 빠른 임의 접근이 필요한 경우
  • 데이터 크기가 고정되어 있거나 자주 변하지 않는 경우
  • 캐시 효율이 중요한 경우 (순차 탐색이 많을 때)
  • 메모리 사용을 최소화해야 하는 경우
# 좋은 예: 학생 성적 조회 (인덱스로 빠른 접근)
scores = [95, 87, 92, 78, 88]
print(scores[2])  # O(1) - 즉시 접근

Linked List를 선택해야 할 때

  • 빈번한 삽입/삭제가 필요한 경우 (특히 리스트 앞/중간)
  • 데이터 크기가 동적으로 변하는 경우
  • 메모리를 미리 예약할 필요가 없는 경우
  • 스택, 큐와 같은 자료구조 구현의 기반으로 사용할 때
# 좋은 예: 브라우저 방문 기록 (앞에서 삽입/삭제 빈번)
from collections import deque

history = deque()
history.appendleft("google.com")   # O(1)
history.appendleft("github.com")   # O(1)
history.appendleft("stackoverflow.com")  # O(1)
history.popleft()  # 뒤로가기: O(1)

성능 요약 비교표

항목ArrayLinked List
메모리 배치연속비연속
임의 접근O(1)O(n)
순차 탐색O(n)O(n)
앞 삽입/삭제O(n)O(1)
중간 삽입/삭제O(n)O(1) (위치 알 때)
끝 삽입/삭제O(1)O(n) / O(1) (tail 포인터 있을 때)
추가 메모리없음포인터 오버헤드
캐시 효율높음낮음
크기 변경어려움 (재할당)용이
적합한 용도빈번한 조회빈번한 삽입/삭제
이전 질문다음 질문