5) 연결 리스트: 시연

장단점

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

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

연결 리스트에 값을 추가하거나 검색하는 경우, 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야 합니다.

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

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

배열이 정렬되어 있지 않은 경우의 검색 소요 시간을 연결 리스트의 검색 시간과 비교해보세요.

배열을 정렬하고 검색을 실행하는 방법도 있지만, 선형 검색 O(n) 을 사용한다면 연결리스트와 같은 시간이 걸린다.

written by CaesiumY