배열과 연결리스트

배열은 고정된 연속적인 메모리 공간에 값이 저장되어있는 자료구조이다. 배열에 값을 추가하기 위해서는 새로운 큰 메모리공간을 할당하여 기존의 배열값들을 모두 복사하고 새로운 값을 저장해야한다. 따라서 O(n)이다.

Q.이미 할당된 메모리의 크기를 조절할 때 임시 메모리를 새로 할당해줘야 하는 이유는 무엇인가요?
A. 이미 할당된 메모리 크기에 바로 새로운 값을 저장하면 이미 다른 값이 저장되어있어 값손실이 일어날 수 있다.

반면에 연결리스트는 각 값들이 메모리에 분포되어있지만 다음 메모리의 주소를 통해 다음 값으로 접근할 수 있는 자료구조이다. 따라서 값을 추가할 때 별도의 메모리 할당을 하지 않아도 된다. 그러나, 임의 접근을 할 수없고 처음부터 찾는 값을 찾을때까지 돌아야한다.(O(n)) 그렇기 때문에 이진탐색을 사용할 수없다.

연결리스트의 탐색 시간을 줄이기 위해 사용하는 자료구조가 이진탐색트리이다. 이진탐색트리는 루트의 왼쪽 서브트리의 노드들은 모두 루트보다 작고 오른쪽 서브트리의 노드들은 모두 루트보다 크다. 따라서 탐색시간이 O(log n)이다. 이진탐색트리는 연결리스트보다 값을 탐색하는 시간이 짧지만 포인터를 1개를 쓰는 연결리스트와 달리 포인터를 2개를 사용하기때문에 메모리공간을 더 사용한다.