배열과 리스트의 차이점에 대해서 설명해주세요.

배열은 연속된 메모리 위치에 고정적인 크기로 저장되는 자료구조 입니다. 때문에 프로그래머가 배열을 선언할때 크기를 미리 정해줘야 합니다. 때문에 인덱스 요소로 탐색에는 시간복잡도에서  O(1)을 갖습니다.

 

반면

 

리스트는 데이터와 포인터로 이루어진, 자료구조 입니다. 포인터는 다음 노드를 가리키고 있기 때문에, 배열과는 다르게 연속적인 메모리를 차지하지는 않고 동적으로 크기를 조절할 수 있습니다. 탐색에 있어서는 처음부터 순회해야 하기 때문에, 시간 복잡도 O(n)을 갖습니다.