[개발 실무] 자료구조 기초 - 배열과 연결 리스트는 왜 속도가 다를까?

프로그래밍을 처음 시작할 때 배열(Array)과 리스트(Linked List)는 모두 '여러 개의 데이터를 모아두는 묶음'처럼 보입니다. 초보자들은 이 둘을 단순한 문법 차이로 오해하거나, 리스트가 배열보다 무조건 발전된 형태라고 생각하는 오류를 범하곤 합니다.

하지만 실제 프로그램에서는 어떤 자료구조를 선택하느냐에 따라 극심한 속도 차이가 발생합니다. 코드의 문제가 아니라, 데이터가 저장되는 '메모리 구조' 자체가 다르기 때문입니다.

오늘은 배열과 연결 리스트의 구조적 차이점을 살펴보고, 왜 속도 차이가 발생하는지, 그리고 언제 어떤 자료구조를 사용해야 하는지 알기 쉽게 정리해 보겠습니다.

 

--------------------------------------------------------------------------------

🏢 배열(Array)의 구조 : 아파트 복도처럼 나란히

배열은 메모리 공간에 데이터가 한 줄로 연속적으로 배치되는 선형 자료구조입니다. 논리적인 저장 순서와 물리적인 저장 순서가 완벽하게 일치하는 것이 가장 큰 특징입니다.

• 비유하자면 : 아파트 복도 구조와 같습니다. 101호, 102호, 103호처럼 집들이 번호 순서대로 나란히 붙어 있습니다.
• 특징 : 메모리 블록이 일렬로 이어져 있기 때문에 105호를 찾고 싶다면 굳이 101호부터 헤아릴 필요 없이 한 번에 그 위치로 걸어갈 수 있습니다.
• 속도 공식 : 배열은 시작 주소 + (인덱스 × 데이터 크기)라는 단순한 수학적 계산만으로 특정 위치의 메모리 주소를 즉시 알아낼 수 있습니다. 따라서 데이터 접근 시간 복잡도는 O(1)로 매우 빠릅니다.

🏡 연결 리스트(Linked List)의 구조 : 도시 곳곳에 흩어진 집

배열과 달리 연결 리스트는 메모리 상에 데이터가 비연속적으로 흩어져서 저장됩니다. 대신, 각각의 데이터(노드)는 자신의 값과 함께 다음 데이터가 있는 위치(주소 값)를 가리키는 포인터를 가지고 있습니다.

• 비유하자면 : 도시 곳곳에 떨어져 있는 단독주택들과 같습니다. 각 집마다 다음 집의 주소가 적힌 쪽지를 가지고 있어, 목적지를 찾으려면 첫 번째 집부터 쪽지를 보고 순서대로 계속 따라가야만 합니다.
• 특징 : 첫 번째 노드에서 시작해 두 번째, 세 번째 노드로 화살표를 따라 이동해야 하므로 한 번에 특정 위치로 점프할 수 없습니다.
• 속도 공식 : K번째 원소를 찾기 위해서는 첫 노드부터 K번 이동해야 하므로, 탐색 시간 복잡도는 O(n)이 됩니다.

 

--------------------------------------------------------------------------------

🚀 그래서 어떤 작업에서 속도 차이가 발생할까?

구조적 차이로 인해 두 자료구조는 특정 작업에서 확연한 성능 차이를 보입니다.

1. 특정 위치의 데이터 접근 (탐색) : 배열 승리 🏆

책장에 꽂힌 책을 찾을 때, 배열은 책장 번호로 곧바로 찾아가는 방식(O(1))인 반면, 연결 리스트는 사람들에게 다음 사람의 위치를 계속 물어보며 찾아가는 방식(O(n))입니다. 게다가 배열은 데이터가 연속적으로 뭉쳐 있기 때문에 CPU가 메모리를 읽어올 때 한 번에 주변 데이터까지 미리 가져오는 캐시 지역성(Cache Locality)이 매우 우수하여 실제 처리 속도가 훨씬 빠릅니다.

2. 데이터 중간 삽입 및 삭제: 연결 리스트 승리 🏆

배열은 빈틈없이 나란히 서 있는 구조이기 때문에, 중간에 데이터를 끼워 넣으려면 삽입할 위치 뒤에 있는 모든 데이터를 한 칸씩 오른쪽으로 밀어내야 합니다. 책장의 책을 전부 옆으로 미는 것과 같아 시간 복잡도가 O(n)이 걸립니다. 반면, 연결 리스트는 데이터가 흩어져 있으므로 나머지 데이터를 이동시킬 필요가 전혀 없습니다. 중간에 끼워 넣고 이전 노드와 다음 노드가 가리키는 화살표(포인터) 방향만 쓱 바꿔주면 끝납니다. 삽입/삭제 자체에 걸리는 시간은 O(1)로 매우 빠릅니다.

 

--------------------------------------------------------------------------------

🛠️ 결론 : 배열과 리스트, 언제 무엇을 써야 할까?

망치와 드라이버가 모두 공구함의 도구지만 사용 목적이 다르듯, 자료구조 역시 상황에 맞는 올바른 선택이 필요합니다.

작업 유형배열 (Array)연결 리스트 (Linked List)

특정 위치 접근 (조회)	빠름 (O(1))	느림 (O(n))
중간 삽입/삭제	느림 (O(n))	빠름 (O(1))
메모리 캐시 효율	높음	낮음

💡 실무 적용 팁

• 배열을 선택하세요 : 데이터의 개수가 미리 정해져 있고, 인덱스를 활용한 데이터 조회나 탐색이 빈번하게 일어나는 경우.
• 연결 리스트를 선택하세요 : 데이터의 삽입과 삭제가 수시로 발생하며, 데이터의 최대 개수를 예측하기 힘든 가변적인 상황일 경우.

배열과 연결 리스트의 메모리 동작 원리를 이해하는 것은 단순한 문법 공부를 넘어, 프로그램의 병목 현상(성능 저하)을 해결하고 최적화할 수 있는 개발자의 핵심 역량입니다. 자신이 구현하고자 하는 서비스의 로직이 '탐색' 위주인지, '수정(삽입/삭제)' 위주인지 파악하여 가장 알맞은 자료구조를 선택해 보세요!