위키득계정 ↗
기술

연결 리스트와 배열의 차이

연결 리스트와 배열의 차이기술
배열 기반
인덱스 위치 접근
연결 리스트
노드 사이의 연결을 따라 이동
조건부 이점
갱신할 위치의 참조가 있는 경우
비교 범위
검색과 갱신을 합친 비용
배열 기반 구조는 위치를 이용한 접근에, 연결 리스트는 연결 관계를 통한 순회와 알려진 위치 주변의 갱신에 서로 다른 특성을 가진다. 삽입이 빠르다는 설명에는 삽입 위치를 이미 알고 있다는 조건이 중요하다.

위치로 찾는 방식

일반적인 배열 기반 구조는 순번을 이용해 해당 원소의 저장 위치를 계산한다. 연결 리스트는 다음 노드나 이전 노드의 참조를 따라 이동한다. 그래서 몇 번째 원소를 반복해서 찾는 작업과 현재 노드 옆에서 갱신하는 작업은 다른 특성을 보인다. 어떤 접근을 자주 하는지부터 판단해야 한다.

삽입 자체와 위치 찾기

연결 리스트에서 필요한 노드와 연결 지점을 이미 알고 있다면 연결을 바꾸는 작업을 작게 만들 수 있다. 하지만 특정 순번이나 값을 찾아 거기에 삽입하려면 그 위치를 찾는 순회가 먼저 필요할 수 있다. 갱신 단계만 떼어 빠르다고 설명하면 전체 작업 비용을 놓친다. 구현에 필요한 이전 노드 정보도 확인해야 한다.

배열의 이동과 확장

배열 기반 구조의 중간 삽입은 뒤 항목의 이동을 요구할 수 있다. 동적 배열은 공간이 부족할 때 더 큰 저장 영역으로 옮기는 과정도 가질 수 있다. 끝에 추가하는 일반적인 비용과 특정 확장 순간의 비용을 구분한다. 한 연산의 최악 비용과 여러 연산에 나누어 보는 비용이 항상 같은 것은 아니다.

메모리와 실제 성능

연결 리스트에는 노드 연결을 저장하는 공간과 개별 할당 비용이 필요할 수 있다. 배열도 남겨 둔 여유 용량을 사용할 수 있다. 실제 언어에서 저장하는 것이 값인지 객체 참조인지에 따라 메모리 구조가 달라지므로 단순히 한쪽이 항상 작다고 말하지 않는다. 순회 시 메모리 접근 특성도 실측 성능에 영향을 준다.

작업별 선택

무작위 순번 접근과 반복 순회가 많다면 배열 기반 구조의 장점을 검토한다. 알려진 위치 주변의 연결을 자주 바꾸는 문제에서는 연결 리스트를 검토할 수 있다. 양 끝 처리만 필요하다면 덱처럼 다른 구조도 고려한다. 작은 성능 실험에서도 실제 입력 크기와 검색을 포함한 전체 작업을 맞추어 비교해야 한다.

관련 문서

배열 / 연결 리스트 / 알고리즘 / 스택과 큐의 선택