자료구조의 세계에 첫 발을 내디딜 때 가장 먼저 배우는 두 가지 기본 구조가 있습니다. 바로 배열(Array)과 연결 리스트(Linked List)입니다. 두 자료구조 모두 데이터를 순서대로 나열한다는 점에서는 비슷해 보이지만, 컴퓨터 내부에서 메모리를 사용하는 방식은 완전히 정반대입니다. "어떤 상황에서 배열을 써야 하고, 언제 연결 리스트를 써야 할까?" 이 질문에 명확히 답할 수 있다면 여러분은 이미 데이터 최적화의 기본을 갖춘 것입니다. 오늘은 이 두 라이벌의 내부 구조를 해부하고 장단점을 완벽하게 비교해 드리겠습니다.
1. 배열 (Array): 질서 정연한 군대
배열은 가장 기본적이고 친숙한 자료구조입니다. 배열의 핵심 키워드는 '연속성'입니다. 메모리 상에 데이터를 빈틈없이 순서대로 차곡차곡 채워 넣는 구조입니다.
1-1. 강력한 장점: 임의 접근(Random Access)
배열의 가장 큰 무기는 인덱스(Index)를 통한 조회 속도입니다. 배열은 데이터가 메모리에 연속적으로 붙어 있기 때문에, 시작 주소만 알면 간단한 수학 계산으로 $n$번째 데이터의 위치를 즉시 알아낼 수 있습니다.
- 조회 속도: O(1) - 첫 번째 데이터를 찾으나 100만 번째 데이터를 찾으나 걸리는 시간은 똑같습니다.
- 캐시 지역성(Cache Locality): 데이터가 붙어 있기 때문에 CPU가 캐시 메모리를 효율적으로 사용할 수 있어 실제 체감 성능이 매우 빠릅니다.
1-2. 치명적 단점: 유연성 부족
하지만 이 '연속성'이 단점이 되기도 합니다. 중간에 데이터를 끼워 넣거나 빼는 것이 매우 번거롭습니다.
- 삽입/삭제 속도: O(n) - 배열의 중간에 데이터를 넣으려면, 그 뒤에 있는 모든 데이터를 한 칸씩 뒤로 밀어야 합니다. 반대로 삭제하면 빈 공간을 채우기 위해 당겨와야 합니다. 데이터가 많을수록 이 작업은 매우 느려집니다.
- 크기 고정: 일반적인 정적 배열은 처음에 크기를 선언해야 합니다. 크기를 넘어서면 더 큰 배열을 만들고 데이터를 전부 이사(Copy)시켜야 하는 비용이 듭니다.
2. 연결 리스트 (Linked List): 자유로운 보물찾기
연결 리스트는 배열의 단점을 해결하기 위해 고안되었습니다. 데이터들이 메모리 여기저기에 흩어져 저장되며, 각 데이터(노드)가 "다음 데이터는 저기에 있어요"라고 가리키는 포인터(Pointer)를 가지고 연결된 구조입니다. 마치 보물찾기 쪽지를 따라가는 것과 같습니다.
2-1. 유연한 장점: 삽입과 삭제의 자유
연결 리스트는 물리적으로 데이터를 이동시킬 필요가 없습니다. 데이터를 추가하거나 삭제할 때, 단순히 화살표(포인터)의 방향만 바꿔주면 끝납니다.
- 삽입/삭제 유연성: 데이터가 어디에 있든 연결 고리만 수정하면 되므로 배열처럼 데이터를 밀거나 당길 필요가 없습니다. (단, 삽입할 위치를 찾아가는 시간은 별개입니다.)
- 동적 크기: 메모리가 허용하는 한 데이터를 무한정 추가할 수 있습니다. 초기 크기를 고민할 필요가 없습니다.
2-2. 구조적 단점: 느린 검색 속도
하지만 자유에는 대가가 따릅니다. 연결 리스트에는 인덱스가 없습니다. 5번째 데이터를 찾으려면 반드시 첫 번째, 두 번째, 세 번째... 순서대로 쪽지를 따라가며 방문해야 합니다.
- 조회 속도: O(n) - 찾으려는 데이터가 뒤쪽에 있을수록 시간이 오래 걸립니다. 건너뛰기가 불가능합니다.
- 추가 메모리: 실제 데이터 외에도 다음 주소를 저장하기 위한 공간(포인터)이 추가로 필요합니다.
3. 한눈에 보는 비교와 선택 가이드
개발자는 상황에 따라 적절한 도구를 꺼내 써야 합니다. 다음은 실무적인 선택 기준입니다.
| 특징 | 배열 (Array) | 연결 리스트 (Linked List) |
|---|---|---|
| 데이터 접근 (Read) | 매우 빠름 O(1) | 느림 O(n) |
| 데이터 삽입/삭제 | 느림 O(n) | 상대적으로 빠름 |
| 메모리 구조 | 연속적 할당 | 비연속적 (흩어짐) |
3-1. 배열을 선택하세요 (Array)
- 데이터의 개수가 어느 정도 정해져 있을 때
- 데이터를 자주 수정하지 않고, 주로 조회(검색)하는 기능이 많을 때 (예: 주식 차트 데이터, 게시판 목록 조회)
- 빠른 반복문 처리가 필요할 때
3-2. 연결 리스트를 선택하세요 (Linked List)
- 데이터가 몇 개나 들어올지 예측할 수 없을 때
- 중간에 데이터를 추가하거나 삭제하는 작업이 빈번할 때 (예: 음악 플레이어의 재생 목록 관리, 이미지 뷰어의 히스토리)
1. 배열은 인덱스를 통한 빠른 조회(O(1))가 강점이지만, 크기가 고정적이고 삽입/삭제가 느립니다.
2. 연결 리스트는 유연한 크기와 삽입/삭제가 강점이지만, 조회가 느리고(O(n)) 추가 메모리를 씁니다.
3. 데이터의 변경 빈도와 검색 빈도를 고려하여 최적의 자료구조를 선택해야 시스템 성능을 높일 수 있습니다.