배열과 연결 리스트 2

배열과 연결 리스트에서 본 배열(array)과 연결 리스트(linked list)를 실제로 쓸 때 알아야 할 내용을 이어서 다룬다. 크기가 모자라면 스스로 자라는 배열의 동작과 두 구조의 연산 비용을 표로 정리한다. 이어서 이론상 비용보다 실제 성능을 더 크게 가르는 요인이 메모리가 연속인지라는 점과, Java에서 무엇을 기본으로 고르는지를 본다.

동적 배열: 크기가 자라는 배열

동적 배열(dynamic array)은 고정 크기 배열의 단점을 메운다. 실제로 잡아 둔 칸 수(용량)와 들어 있는 원소 수(크기)를 따로 관리하다가, 용량이 가득 차면 더 큰 배열을 새로 잡고 기존 원소를 전부 옮겨 담는다. Java의 ArrayList와 Python의 list가 이 방식이다.

옮기는 순간의 추가는 O(n)이다. 빅오 표기법(Big-O notation)으로 적은 O(n)은 원소 수 n에 비례해 시간이 늘어난다는 뜻이고, O(1)은 원소 수와 상관없이 시간이 일정하다는 뜻이다. 하지만 용량을 일정 비율로 키우면 옮기는 일이 점점 드물어진다. 교과서 모델처럼 두 배로 키우면 옮기는 양이 1, 2, 4, …처럼 늘어나고, 이 합은 마지막 크기의 두 배를 넘지 않는다. 그래서 n번 추가하는 동안 옮기는 총량이 2n보다 작아서, 전체를 횟수로 나눈 한 번당 비용은 O(1)이다. 이렇게 드문 비싼 작업을 전체 횟수에 나눠 보는 방법을 분할 상환 분석(amortized analysis)이라 한다. Java의 공개 표준 구현인 OpenJDK의 ArrayList는 두 배가 아니라 약 1.5배씩 늘리지만, 1보다 큰 일정 비율이면 분할 상환 O(1)이라는 결론은 같다. 넣을 개수를 미리 알면 new ArrayList<>(n)처럼 처음부터 용량을 잡아 두거나 ensureCapacity로 한 번에 늘려 두어, 중간에 여러 번 옮기는 일을 줄일 수 있다.

연산 비용 비교

배열은 시작 주소에 "칸 크기 × 번호"를 더하는 계산 한 번으로 i번째 칸을 찾지만, 연결 리스트는 첫 노드(node)부터 포인터(pointer)를 i번 따라가야 한다. 표의 꼬리 포인터는 마지막 노드를 따로 가리켜 두는 포인터로, 있으면 끝까지 따라가지 않고 바로 뒤에 붙인다.

연산	배열·동적 배열	연결 리스트
i번째 읽기	O(1)	O(n)
맨 앞에 넣기·빼기	O(n)	O(1)
맨 뒤에 넣기	분할 상환 O(1)	O(1), 꼬리 포인터가 있을 때
위치를 아는 중간 삽입·삭제	O(n)	O(1)
값으로 찾기	O(n)	O(n)
추가 메모리	남는 용량	노드마다 포인터

실제 성능은 캐시가 가른다

표만 보면 삽입이 잦으면 연결 리스트가 이길 것 같지만, 실제로는 배열이 더 빠른 경우가 많다. 이유는 캐시 메모리(cache memory)다. CPU는 메모리에서 값 하나를 읽을 때 이웃 주소까지 한 묶음으로 가져와 CPU 가까운 캐시 메모리에 둔다. 이 묶음 단위를 캐시 라인(cache line)이라 한다. 가까운 곳에 있는 데이터를 이어서 쓰는 경향을 지역성(locality)이라 하고, 배열은 이 성질과 잘 맞는다.

배열을 앞에서부터 읽으면 다음 원소가 이미 같은 묶음에 딸려 와 있다. 그래서 캐시 메모리에서 바로 찾는 캐시 히트(cache hit)가 연달아 난다. CPU가 다음에 읽을 주소를 쉽게 예측해 미리 가져올 수도 있다. 연결 리스트는 노드가 흩어져 있어, 다음 노드를 읽을 때마다 캐시 메모리에 없어 느린 메모리까지 가야 하는 캐시 미스(cache miss)가 날 수 있다. 게다가 다음 노드의 주소는 지금 노드를 읽어야 알 수 있으니 미리 가져오기도 어렵다. 배열의 중간 삽입이 원소를 n개 옮기더라도, 연속 메모리를 한꺼번에 옮기는 일은 매우 빨라서 연결 리스트에서 위치를 찾아 포인터를 따라가는 시간보다 짧은 경우가 흔하다.

언제 무엇을 쓰나

List<Integer> a = new ArrayList<>(), l = new LinkedList<>();
a.get(500_000);   // O(1): 주소 계산 한 번
l.get(500_000);   // O(n): 가까운 끝에서부터 노드를 따라간다
a.add(0, 7);      // O(n): 뒤 원소를 전부 한 칸씩 민다
l.add(0, 7);      // O(1): 첫 노드 연결만 바꾼다

Java에서는 대부분 ArrayList가 기본 선택이다. 인덱스 접근이 빠르고, 캐시 메모리를 잘 쓰며, 노드마다 객체를 따로 만들지 않아 메모리도 적게 쓴다. LinkedList는 이중 연결 리스트(doubly linked list)라 양 끝 넣기·빼기가 O(1)이지만, 큐(queue)로 쓸 때는 배열 기반인 ArrayDeque가 LinkedList보다 보통 더 빠르다고 공식 문서에 적혀 있다. 연결 리스트가 확실히 유리한 경우는 반복자(iterator)로 훑으면서 그 자리에 넣고 빼는 일이 많을 때처럼, 위치를 이미 쥐고 있는 상황이다.

면접 포인트

• "동적 배열 추가의 복잡도는?" → 분할 상환 O(1). 확장 순간은 O(n).
• "그럼 왜 실무에서 ArrayList를 주로 쓰나요?" → 캐시(cache) 지역성, 메모리 효율. 양 끝 작업도 ArrayDeque가 보통 낫다.
• "연결 리스트가 확실히 유리한 때는?" → 반복자로 훑으며 그 자리에서 넣고 빼는 일이 많을 때처럼 위치를 이미 쥐고 있을 때.