배열과 연결리스트는 둘 다 데이터를 순서대로 담는 자료구조지만, 내부에서 데이터를 놓는 방식이 완전히 다르다. 배열은 데이터를 연속된 메모리에 붙여서 저장하고, 연결리스트는 각 노드가 다음 노드를 가리키는 방식으로 흩어진 데이터를 이어 붙인다.
이 차이 하나 때문에 접근, 삽입, 삭제의 성격이 갈린다. 배열은 인덱스를 알면 바로 접근할 수 있지만 중간에 끼워 넣거나 앞에서 지우려면 많은 요소를 밀어야 한다. 연결리스트는 노드의 연결만 바꾸면 삽입과 삭제가 빠르지만, 원하는 위치를 찾기 위해 처음부터 따라가야 한다.
이 묶음에서 볼 글
- 배열의 메모리 구조: 배열이 왜 인덱스 접근에 강한지, 캐시 효율이 왜 좋은지 정리한다.
- 정적 배열 vs 동적 배열:
ArrayList나vector가 내부적으로 어떻게 커지는지 본다. - 단일 연결리스트:
next만 가진 연결 구조와 기본 연산을 정리한다. - 이중 연결리스트:
prev까지 두었을 때 삭제와 양방향 이동이 어떻게 달라지는지 본다. - 시간복잡도 비교: 연산별 비용을 표로 훑고, 실제 성능에서 캐시가 왜 중요한지 정리한다.
- 선택 기준: 면접이나 설계 상황에서 어떤 자료구조를 고를지 판단한다.
핵심 감각
면접에서 배열과 연결리스트를 비교하라고 하면 시간복잡도 표만 말하기 쉽다. 하지만 실제로는 “어떤 연산을 빠르게 만들고 싶은가”가 먼저다. 랜덤 접근과 순차 순회가 많으면 배열이나 동적 배열이 유리하다. 앞쪽 삽입/삭제나 특정 노드의 순서 변경이 많고, 그 노드 참조를 이미 알고 있다면 연결리스트가 후보가 된다.
또 하나 중요한 점은 실제 성능이다. 연결리스트는 이론상 삽입/삭제가 좋아 보이지만, 노드가 메모리에 흩어져 있어 캐시 효율이 떨어진다. 그래서 Java의 LinkedList가 항상 ArrayList보다 빠른 것은 아니다. 오히려 대부분의 일반적인 리스트 작업에서는 ArrayList가 더 자주 선택된다.
답변 뼈대
배열은 연속 메모리에 데이터를 저장하므로 인덱스 접근이 O(1)이고 캐시 효율이 좋다. 대신 앞이나 중간 삽입/삭제는 요소 이동 때문에 O(n)이 된다. 연결리스트는 노드가 포인터로 이어져 있어 노드 참조를 알고 있으면 삽입/삭제 자체는 O(1)이지만, 특정 위치를 찾는 과정은 O(n)이다. 그래서 랜덤 접근과 순차 처리가 많으면 배열/동적 배열을, 앞뒤 삽입/삭제나 순서 재배치가 핵심이면 연결리스트 계열을 고려한다.