개발자가 데이터를 다룰 때 가장 먼저 고민해야 하는 것은 "이 데이터를 어디에, 어떻게 저장할까?"입니다. 이때 가장 기본이 되는 선택지가 바로 배열(Array)과 연결 리스트(Linked List)입니다. 두 자료구조 모두 데이터를 순서대로 저장한다는 점은 같지만, 메모리를 사용하는 방식과 효율성 측면에서는 정반대의 성격을 가지고 있습니다. 마치 지정석 영화관과 보물찾기의 차이와도 같습니다. 이 두 구조의 차이를 명확히 이해하고 상황에 맞춰 골라 쓰는 능력이야말로 초보와 고수를 가르는 기준이 됩니다.
1. 배열(Array): 속도의 제왕, 유연성의 부족
배열은 가장 친숙하고 기본적인 자료구조입니다. 배열의 핵심은 '연속성'입니다. 메모리상의 공간을 미리 예약해서 빈틈없이 채워 넣는 방식입니다.
1-1. 영화관 지정석의 원리
배열을 영화관의 연속된 좌석이라고 생각해 보세요. 여러분은 친구 5명과 영화를 보러 갔습니다. 매표소에서 "연속된 5자리 주세요"라고 말합니다. 이때 여러분은 첫 번째 친구가 앉은 자리 번호(인덱스 0)만 알면, 세 번째 친구가 어디 앉았는지 굳이 확인하러 가지 않아도 알 수 있습니다. 그냥 +2만 하면 되니까요. 이것이 바로 배열의 가장 큰 장점인 빠른 접근 속도(Random Access)입니다.
1-2. 장점과 단점
- 장점 (조회 속도 O(1)): 인덱스만 알면 수식 계산 한 번으로 데이터 위치를 즉시 찾아냅니다. 데이터가 100만 개라도 1초도 안 걸립니다.
- 단점 (삽입/삭제 속도 O(n)): 만약 중간에 친구 한 명이 늦게 와서 끼어앉으려 한다면? 이미 앉아있는 모든 사람이 한 칸씩 옆으로 이동해야 합니다. 데이터 추가/삭제 시 오버헤드가 매우 큽니다. 또한, 처음에 정한 크기(좌석 수)를 바꿀 수 없습니다.
2. 연결 리스트(Linked List): 유연함의 대가, 느린 검색
연결 리스트는 배열의 단점인 '크기 고정'과 '비효율적인 삽입/삭제'를 해결하기 위해 등장했습니다. 핵심은 '연결'입니다.
2-1. 보물찾기 쪽지의 원리
연결 리스트는 보물찾기와 같습니다. 첫 번째 쪽지를 찾으면, 그 쪽지에 "다음 보물은 놀이터 미끄럼틀 아래에 있어"라고 적혀 있습니다(포인터). 미끄럼틀로 가야만 다음 위치를 알 수 있습니다. 즉, 데이터들이 메모리 여기저기에 흩어져 있고, 서로가 서로를 가리키는 끈(Link)으로 연결된 구조입니다.
2-2. 장점과 단점
- 장점 (삽입/삭제 속도 O(1)): 중간에 데이터를 넣고 싶으면, 앞뒤 데이터의 연결 끈(포인터)만 살짝 바꿔주면 됩니다. 다른 데이터들을 이동시킬 필요가 전혀 없습니다. 메모리가 허용하는 한 무제한으로 늘어날 수 있습니다.
- 단점 (조회 속도 O(n)): 5번째 데이터를 찾으려면 반드시 첫 번째부터 순서대로 쪽지를 따라가야 합니다. 건너뛰기가 불가능하여 검색 속도가 느립니다.
3. 결정적 선택 가이드: 언제 무엇을 쓸까?
무조건 더 좋은 자료구조는 없습니다. 내 서비스의 특징에 따라 선택해야 합니다.
- 배열을 선택하세요: 데이터의 개수가 정해져 있고, 변화가 거의 없으며, '검색(조회)'이 빈번한 경우. (예: 주식 차트 데이터, 게시판 목록)
- 연결 리스트를 선택하세요: 데이터가 계속 추가되거나 삭제되며, 개수를 예측할 수 없고, '삽입/삭제'가 빈번한 경우. (예: 음악 플레이어 재생목록, 이미지 뷰어 히스토리)
1. 배열은 연속된 메모리를 사용하여 조회(O(1))가 빠르지만, 삽입/삭제가 느립니다.
2. 연결 리스트는 흩어진 메모리를 연결하여 삽입/삭제가 유연하지만, 조회(O(n))가 느립니다.
3. 데이터의 변경 빈도와 검색 빈도를 고려하여 최적의 구조를 선택해야 성능 저하를 막을 수 있습니다.