자료 구조와 알고리즘
배열과 비교했을 때 연결 리스트(각 원소가 다음 원소의 위치를 가리키는 포인터를 가진 리스트)의 특징으로 올바른 것은?
- A삽입할 위치 바로 앞의 원소를 알고 있으면 다른 원소를 옮기지 않고 포인터를 바꿔 다는 것만으로 삽입할 수 있지만, i번째 원소를 읽으려면 앞에서부터 차례로 따라가야 한다
- Bi번째 원소의 위치를 계산으로 구할 수 있으므로, 어느 원소든 일정한 시간 O(1)로 읽을 수 있다
- C원소가 메모리 위에 빈틈없이 연속해서 늘어서므로, 차례로 읽을 때 캐시나 프리페치가 잘 듣는다
정답과 해설 보기
정답: A. 삽입할 위치 바로 앞의 원소를 알고 있으면 다른 원소를 옮기지 않고 포인터를 바꿔 다는 것만으로 삽입할 수 있지만, i번째 원소를 읽으려면 앞에서부터 차례로 따라가야 한다
연결 리스트에서는 삽입이나 삭제할 위치를 알고 있으면 앞뒤의 포인터를 바꿔 쓰기만 하면 되므로 O(1)로 끝납니다. 한편 i번째 원소를 읽으려면 맨 앞에서부터 i번 포인터를 따라가야 하므로 O(n)이 걸립니다. 배열은 시작 주소와 원소의 크기로 i번째 주소를 계산할 수 있으므로 O(1)로 읽을 수 있지만, 중간에 삽입하려면 뒤쪽 원소를 밀어내는 O(n)의 수고가 듭니다. 또한 배열은 원소가 연속해서 늘어서므로 캐시나 프리페치가 잘 듣고, 메모리 위에 흩어지기 쉬운 연결 리스트는 같은 O(n)의 순회라도 훨씬 느려지는 경우가 있습니다.