배열과 연결 리스트의 차이점을 설명해주세요.

배열은 연속된 메모리 공간에 데이터를 저장하고, 연결 리스트는 각 노드가 값과 다음 노드의 참조를 저장합니다. 이 구조 차이 때문에 조회, 삽입, 삭제, 캐시 효율에서 서로 다른 특성을 가집니다.

핵심 개념

• 배열은 인덱스로 O(1) 임의 접근이 가능하지만 중간 삽입/삭제는 뒤 요소 이동이 필요합니다.
• 연결 리스트는 노드 참조를 알고 있으면 삽입/삭제가 O(1)이지만 특정 위치 탐색은 O(n)입니다.
• 배열은 메모리 지역성이 좋아 실제 성능이 좋은 경우가 많습니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

배열: [10][20][30][40]
- arr[2] 접근: 바로 계산 가능
- 앞에 삽입: 모든 요소를 뒤로 이동

연결 리스트: 10 -> 20 -> 30 -> 40
- 세 번째 요소 접근: 앞에서부터 순회
- 20 뒤에 삽입: 포인터만 변경

const arr = [10, 20, 30];
arr.splice(1, 0, 15); // 중간 삽입, 뒤 요소 이동 발생

실무에서 주의할 점

• 이론상 연결 리스트 삽입이 빠르더라도 실제로는 포인터 추적과 캐시 미스로 배열보다 느릴 수 있습니다.
• JavaScript의 Array는 동적 배열에 가까우며 언어 런타임 최적화 영향을 받습니다.
• 연결 리스트는 메모리 오버헤드와 구현 복잡도가 큽니다.

실무 적용 가이드

• 대부분의 애플리케이션 데이터는 배열로 시작해도 충분합니다.
• 잦은 양끝 삽입/삭제는 deque 구조를 검토합니다.
• 연결 리스트는 LRU cache 내부, 메모리 allocator, 특정 알고리즘처럼 포인터 조작 이점이 명확할 때 사용합니다.

함께 연결해서 보면 좋은 키워드

Array, Linked List, Data Structure, Cache Locality

정리

배열은 연속된 메모리 공간에 데이터를 저장하고, 연결 리스트는 각 노드가 값과 다음 노드의 참조를 저장합니다입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.