연결 리스트와 배열의 장단점

배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있습니다.

하지만 이런 유동적인 구조는 그 대가가 따릅니다. 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능합니다. 

 

연결 리스트에 값을 추가하거나 검색하는 경우를 생각해 봅시다.

이를 위해서는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야 합니다.

따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이 됩니다.

배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요 되는 것에 비해서 다소 불리합니다.

 

https://www.boostcourse.org/cs112/lecture/119040?isDesc=false