배열과 연결 리스트의 차이

이 글은 면접을 위한 CS 전공지식노트 책 및 강의를 참고하여 정리한 것이다.

배열은 연속된 메모리 공간에 데이터가 쌓인다.

연결리스트는 연속 되지 않은 메모리 공간에 데이터가 쌓인다.(독립적인 공간에 데이터가 저장)

차이를 한 눈에 볼 수 있는 표를 보자면

	배열	연결리스트
메모리 공간	연속적	연속X
삽입, 삭제(맨 끝, 맨 앞 제외)	O(n)	O(1)
n번째 요소 참조	O(1)	O(n)
탐색	O(n)	O(n)

이를 봤을 때, 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 참조를 많이 하는 것은 배열로 하는 것이 좋다.

연결 리스트는 순차적 접근을 하고, 배열은 랜덤 접근을 하기 때문에, n번째 요소 참조의 시간 복잡도가 위와 같다.