1.2.3 비교
그림 1-4는 연속된 자료 구조와 연결된 자료 구조의 중요한 차이점을 요약해서 보여줍니다.
그림 1-5는 관련된 배열과 연결 리스트의 성능을 다양한 관점에서 비교한 결과입니다.
구현할 작업의 요구 조건 및 사용 빈도에 따라 배열과 연결 리스트 중에서 하나를 선택하거나, 또는 두 개를 조합하여 응용 프로그램을 개발해야 합니다.
|
연속된 자료 구조 |
연결된 자료 구조 |
|
모든 데이터가 메모리에 연속적으로 저장됩니다. |
데이터는 노드에 저장되고, 노드는 메모리 곳곳에 흩어져 있을 수 있습니다. |
|
임의 원소에 즉각적으로 접근할 수 있습니다. |
임의 원소에 접근하는 것은 선형 시간 복잡도를 가지며 느린 편입니다. |
|
데이터가 연속적으로 저장되어 있고, 캐시 지역성 효과로 인해 모든 데이터를 순회하는 것이 매우 빠릅니다. |
캐시 지역성 효과가 없으므로 모든 데이터를 순회하는 것이 느린 편입니다. |
|
데이터 저장을 위해 정확하게 데이터 크기만큼의 메모리를 사용합니다. |
각 노드에서 포인터 저장을 위해 여분의 메모리를 사용합니다. |
▲ 그림 1-4 연속된 자료 구조와 연결된 자료 구조의 비교