선택 기준

배열 vs 연결리스트 선택 기준

배열과 연결리스트를 고를 때는 먼저 데이터가 “어떻게 바뀌는지”를 봐야 한다. 몇 번째 원소를 자주 읽는지, 맨 앞이나 중간에 자주 넣고 빼는지, 순서만 유지하면 되는지, 특정 노드 참조를 들고 있는지에 따라 답이 달라진다.

대부분의 일반적인 리스트 용도에서는 배열 기반 구조가 기본 선택이 된다. Java라면 ArrayList, JavaScript라면 Array, C++이라면 vector가 여기에 가깝다. 인덱스 접근이 빠르고, 순차 순회에서 캐시 효율이 좋고, 맨 뒤 추가도 평균적으로 O(1)이기 때문이다.

배열이나 동적 배열을 고르면 좋은 경우

인덱스로 접근해야 한다면 배열이 자연스럽다. 페이지네이션된 목록, DP 테이블, 정렬된 데이터에서의 이진 탐색, 행렬 연산처럼 “몇 번째 값”을 바로 읽어야 하는 작업은 연결리스트와 잘 맞지 않는다.

순차 처리도 배열이 강한 편이다. 둘 다 전체 순회는 O(n)이지만, 배열은 메모리에 연속으로 놓여 있어 캐시 효율이 좋다. 대용량 로그를 순서대로 훑거나, 리스트를 반복문으로 자주 돌며 집계하는 경우에는 배열 기반 구조가 실제로 더 빠를 가능성이 높다.

끝에 계속 추가하는 작업도 동적 배열이 잘 처리한다. 용량이 부족할 때 가끔 큰 복사가 일어나지만, 전체적으로 보면 amortized O(1)이다. 예상 크기를 안다면 초기 용량을 잡아 재할당 비용을 더 줄일 수도 있다.

연결리스트를 고려할 만한 경우

연결리스트는 앞쪽 삽입/삭제가 많거나, 노드 참조를 이미 알고 있는 상태에서 순서를 자주 바꿀 때 의미가 있다. 예를 들어 LRU 캐시는 HashMap으로 항목을 바로 찾고, 이중 연결리스트로 사용 순서를 O(1)에 바꾼다. 여기서는 연결리스트의 장점이 분명하다.

양방향 이동이 중요한 경우도 이중 연결리스트가 자연스럽다. 브라우저 히스토리처럼 이전/다음으로 움직이는 구조, 플레이리스트처럼 현재 위치 기준으로 앞뒤를 오가는 구조가 그렇다.

다만 “삽입/삭제가 많다”는 말만으로 연결리스트를 고르면 위험하다. 삽입할 위치를 매번 찾아야 한다면 탐색 비용 O(n)이 먼저 든다. 그럴 바에는 배열에서 이동 비용을 감수하는 편이 더 빠를 수 있다. 특히 Java의 LinkedList는 노드 객체와 포인터 때문에 메모리 오버헤드가 있고 캐시 효율도 낮다.

상황별로 보면

채팅 메시지 목록처럼 새 메시지가 뒤에 붙고 스크롤로 특정 위치에 접근해야 하는 구조는 동적 배열이 좋다. 실행 취소 기능처럼 마지막 작업을 넣고 빼는 구조는 스택이나 덱으로 보면 되고, 구현체는 ArrayDeque가 더 나은 경우가 많다. LRU 캐시처럼 조회와 순서 변경을 모두 O(1)에 맞춰야 하는 구조는 HashMap과 이중 연결리스트 조합이 잘 맞는다.

면접에서 “100만 개 데이터라면 무엇을 쓰겠냐”는 질문이 나오면 데이터 개수만으로 답을 정하면 안 된다. 100만 개를 자주 순회하고 인덱스로 접근한다면 배열 기반 구조가 유리하다. 앞쪽에서 계속 넣고 빼며 인덱스 접근이 없다면 덱이나 연결리스트를 고려할 수 있다. 특정 노드를 찾아 순서를 계속 바꾸는 문제라면 이중 연결리스트가 후보가 된다.

답변 뼈대

저는 먼저 접근 패턴을 봅니다. 인덱스 접근과 순차 순회가 많으면 배열이나 ArrayList를 고릅니다. 맨 뒤 추가도 평균 O(1)이고 캐시 효율이 좋아 실제 성능이 좋기 때문입니다. 반대로 앞쪽 삽입/삭제가 많거나, 노드 참조를 알고 있는 상태에서 순서를 O(1)에 바꿔야 한다면 연결리스트를 고려합니다. 다만 연결리스트는 위치 탐색이 O(n)이고 캐시 효율이 낮기 때문에, 대부분의 일반적인 리스트 용도에서는 배열 기반 구조를 먼저 선택합니다.