'선형 자료구조'의 두 가지 해법

리스트(List)라는 추상 자료형(ADT, Abstract Data Tye)으로 '순서가 있는 데이터의 집합'을 의미한다.

리스트는 개념일 뿐, 실제 구현 방법은 아니라는 것이다. "순서가 있는 데이터를 저장하라"는 명령을 받았을 때, 컴퓨터의 메모리 구조상 이를 구현하는 방법은 크게 두 가지로 나뉜다.

1. 데이터를 빈틈없이 다닥다닥 붙여서 저장하는 방식 (Array)
2. 데이터를 흩어놓되, 서로를 실로 연결하는 방식 (Linked List)

이 두 방식의 차이는 메모리를 어떻게 사용할 것인가에 대한 근본적인 철학의 차이이며, 이 차이가 모든 성능 의슈의 시작점이 된다. 이번 글에서는 이 두 자료구조의 내부를 깊이 있게 파헤쳐보자!

---

첫 번째 해법: 배열(Array) & 동적 배열

배열(Array): 연속된 메모리의 힘

배열은 가장 원시적이면서도 강력한 자료구조다. 배열의 가장 큰 특징은 물리적 주소의 연속성(Contiguous Memory)이다. 선언하는 순간, 메모리 상의 연속된 공간을 독점한다.

핵심 특징: 인덱스 접근 (Random Access)

데이터가 연속되어 있다는 것은 '수학적 계산'이 가능하다는 뜻이다. 배열의 시작 주소만 알면, 100번째 데이터의 위치는 즉시 알 수 있다.

$TargetAddress = StartAddress + (Index \times DataSize)$

이 공식 덕분에 배열은 데이터가 10개든 100만개든 상관없이, 조회 속도가 $O(1)$로 일정하다.

태생적 한계:

1. 크기가 고정됨 (Static)
   • 처음에 int arr[10]으로 선언하면, 11번째 데이터는 넣을 수 없다. 공간을 늘리려면 새로운 배열을 만들고 이사(Migration)를 가야 한다.
2. 비효율적인 삽입/삭제
   • 배열의 중간에 데이터를 넣으려면, 그 뒤에 있는 모든 데이터를 한 칸씩 뒤로 밀어야(Shift)한다. 이는 $O(n)$의 비용이 든다.

현실적 대안: 동적 배열 (Dynamic Array)

우리가 실무에서 쓰는 Java의 ArrayList, C++의 std::vector, Python의 list는 사실 고정된 배열의 단점을 보완한 동적 배열이다.

• 작동 원리:
  1. 초기에 일정 크기(예: 10)의 배열을 생성한다.
  2. 데이터가 꽉 차면, 기존 크기의 1.5배 또는 2배에 해당하는 새로운 배열을 생성한다.
  3. 기존 데이터를 새 배열로 복사(Copy)하고, 낡은 배열을 버린다.
• 이 방식은 배열의 장점(빠른 조회)을 유지하면서, 리스트의 장점(유동적 크기)을 흉내낸 것이다. 하지만 '이사(Resizing)'하는 순간에는 일시적인 성능 저하가 발생한다.

두 번째 해법: 연결 리스트(LinkedList)와 그 진화

배열이 '연속성'에 집착했다면, 연결 리스트는 '불연속성'을 택했다. 데이터는 메모리 여기저기에 흩어져 있고, 각 데이터(Node)가 다음 데이터의 주소(Reference)를 들고 있는 형태다.

Step 1. 단방향 연결 리스트 (Singly Linked List)

가장 기본적인 형태. 노드는 [Data | Nest]로 구성된다.

• 장점: 구현이 단순하고, 각 노드가 '다음 주소'만 가지므로 메모리 오버헤드가 적다.
• 치명적 단점: '뒤로' 갈 수 없다. 만약 현재 노드를 삭제하려면, 내 바로 앞의 노드(Predecessor)를 알아야 하는데, 단방향에서는 이를 알기 위해 처음(Head)부터 다시 탐색해야 한다.($O(n)$)

Step 2. 양방향 연결 리스트 (Doubly Linked List) - 실무의 핵심

단방향의 단점을 극복하기 위해 [Pref | Data | Next] 구조를 가진다.

• 특징: 앞뒤 어디로든 이동이 가능하다.
• 삭제의 효율성: 삭제할 노드만 알고 있다면, 그 노드의 Prev와 Next를 서로 연결해주면 끝이다. 즉, 삭제 연산 자체는 $O(1)$이다. (단, 삭제할 노드를 찾는 탐색 시간은 별개)
• Java의 선택: Java의 LinkedList는 바로 이 이중 연결 리스트로 구현되어 있다. 탐색과 조작의 유연성을 위해 메모리(Prev 포인터)를 조금 더 쓰는 트레이드 오프를 선택한 것이다.

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

마지막 노드(Tail)가 null을 가리키는 대신, 다시 첫 번재 노드(Head)를 가리키는 구조다.

• 활용: 끝이 없이 계속 돌아가는 구조가 필요할 때 사용한다. 예를 들어, 운영체제의 CPU 스케쥴링(Round Robin)이나, 고정된 크기의 버퍼를 재사용할 때 유용하다.

---

Array vs LinkedList 성능 분석

자료구조를 선택할 때는 단순히 "배열이냐 리스트냐"를 넘어, 언어 차원에서 제공하는 동적 배열(ArrayList)과 기본 배열(Array)의 차이까지 명확하게 구분해야 한다. 이 셋의 성능과 특징을 비교해보자.

한눈에 보는 성능 비교 (Time Complexity & Memory)

⚠️ 용어 구분: 접근 VS 검색

• 접근(Access): 3번째 데이터 내놔 (인덱스 기반) -> $O(1)$
• 검색(Search): 값이 '사과'인 데이터 어딨어? (값 기반) -> $O(n)$
• ArrayList가 빠르다는 건 접근이 빠르다는 뜻이다. 값을 찾는 건 셋 다 똑같이 처음부터 뒤져야 하므로 느리다.

상세 분석: 무엇이 다른가?

Array (기본 배열): "압도적인 속도, 융통성 제로"

• 특징: int[] arr = new int[10]; 처럼 선언 시 크기가 고정된다.
• 장점:
  • 추가적인 오버헤드가 전혀 없다.
  • Primitive Type(int double 등)을 직접 저장할 수 있어 메모리 효율이 압도적이다. (ArrayList는 박싱/언박싱 비용 발생)
• 단점: 꽉 차면 더 이상 데이터를 넣을 수 없다. 크기를 늘리려면 새 배열을 만들고 직접 이사(Copy)시켜야 한다.
• 언제 쓰는가? 데이터 개수가 확실히 정해져있거나 (예: 1년 12달), 극한의 성능이 필요한 알고리즘(DP 테이블 등)구현 시

ArrayList (동적 배열): "인덱스 접근의 제왕"

• 특징: 내부적으로 Array를 품고 있으며, 배열이 꽉 차면 자동으로 크기를 늘려주는(Resizing) 로직이 숨어있다.
• 장점:
  • Random Access(무작위 접근): get(999)를 호출하면 0번부터 세는 게 아니라, 수학 공식($Base + Index \times Size$)으로 단 한번에 위치를 찾아낸다. 데이터가 100만개여도 조회 속도는 $O(1)$이다.
  • 편의성: 배열의 빠른 조회 성능을 유지하면서 크기 제한이 없어 개발자가 가장 편하게 쓸 수 있다.
• 단점:
  • Resizing 비용: 크기가 늘어날 때 (보통 1.5배 ~ 2배) 데이터를 복사하는 과정에서 일시적인 성능 저하가 발생한다.
  • 메모리 낭비: 100개를 저장하기 ㅜ이해 미리 150개짜리 공간을 잡아두므로 (Capacity), 약간의 메모리 낭비가 있다.
• 언제 쓰는가? 조회(Read)가 빈번하고 데이터 개수가 변할 수 있는 일반적인 비즈니스 로직(90% 이상)

LinkedList(연결 리스트): "수정의 스페셜리스트"

• 특징: 노드(Node)들이 줄줄이 연결된 구조. Java에서는 Doubly Linked List다.
• 장점: 중간에 데이터를 끼워 넣거나, 삭제할 때 배열처럼 데이터를 밀어낼 필요가 없다. 참조(주소)만 바꿔주면 도니다.
• 단점:
  • Sequential Access(순차 접근): "인덱스 접근"이 불가능하다. 500번째 데이터를 보려면 첫번째 노드부터 징검다리를 500번 건너가야 한다 ($O(n)$). 이것이 ArrayList와의 결정적 차이이다.
  • 메모리 뚱뚱: 데이터뿐만 아니라 앞뒤 주소 (Prev, Next)까지 저장해야 하므로 메모리를 3~4배 더 먹는다.
• 언제 쓰는가?: 삽입/삭제가 조회보다 훨씬 빈번하거나, 큐(Queue)나 데크(Deque)처럼 앞뒤에서만 작업이 일어날 때

성능 비교요약 (결론)

• 조회속도: Array $\approx$ ArrayList $\gg$ LinkedList
• 쓰기 편의성: ArrayList $\gt$ LinkedList $\gg$ Array
• 메모리 절약: Array $\gg$ ArrayList $\gt$ LinkedList

💡 핵심 팁: ArrayList의 비밀

ArrayList의 add 연산은 기본적으로 $O(1)$ 이지만, 배열이 꽉 차서 확장(Resizing)이 되는 순간에는 $O(n)$이 걸린다. 이를 Amortized $O(1)$(분할 상환시간)이라고 부른다. 즉 가끔 느려지긴 하지만 평균적으로는 빠르다는 뜻이다. 만약 데이터 개수를 대략 안다면 new ARrayList<>(1000)처럼 초기 크기를 지정해주는 것이 Resizing을 막아 성능을 높이는 꿀팁입니다.

---

Cache Locality

이론상 리스트의 삽입이 더 빠른데, 왜 실제로는 ArrayList를 더 많이 사용할까? 정답은 하드웨어(CPU 캐시)에 있다.

캐시 지역성 (Cache Locality)

CPU는 메모리에서 데이터를 가져올 때, 딱 1개(4byte)만 가져오지 않는다. 인접한 데이터가 곧 사용될 것이라 예측하고 주변 데이터 블록(Cache Line, 보통 64byte)을 통째로 가져온다. 이를 공간 지역성(Spatical Locality)이라 한다.

• 배열 (Array): 데이터가 빈틈없이 붙어 있다. arr[0]을 읽을 때, arr[1], arr[2]...도 같이 캐시에 로드된다. 즉, 캐시 적중률(Cache Hit Rate)이 매우 높다.
• 연결 리스트 (Linked List): 데이터가 힙(heap) 메모리 이곳저곳에 흩어져 있다. 다음 노드를 찾으려 하면 캐시에 없어 메모리(RAM)까지 다시 다녀와야 한다. (Cache Miss)

데이터의 개수가 수만 개 수준으로 많지 않거나, 삽입/삭제가 극단적으로 빈번하지 않다면, 최신 하드웨어에서는 배열(ArrayList)이 연결 리스트보다 전반적으로 빠르다. 캐시 효율성 때문이다.

어떤 상황에서 무엇을 써야할까?

데이터 개수가 고정되어 있나요?
  ├─ YES → Primitive 타입인가요?
  │         ├─ YES → Array (int[], double[] 등)
  │         └─ NO  → 편의성이 중요한가요?
  │                   ├─ YES → ArrayList
  │                   └─ NO  → Array
  │
  └─ NO  → 어떤 연산이 더 빈번한가요?
            ├─ 조회 (Read) > 수정 → ArrayList
            ├─ 수정 (Insert/Delete) > 조회 → LinkedList
            └─ 조회 ≈ 수정 → ArrayList (캐시 효율 때문)

코딩 테스트 선택 가이드

상황 / 키워드	추천 자료구조	이유
"N번째 값을 출력하라", "이분 탐색", "정렬"	Array / ArrayList	인덱스 접근($O(1)$)이 필수적임.
"커서를 이동하며 글자 삭제", "원형으로 앉아서..."	LinkedList	중간 삭제/삽입이 핵심 로직임.
"데이터가 계속 들어오는데 최대 N개까지만 유지"	LinkedList (Deque)	앞뒤로 넣고 빼는 작업에 최적화됨.