응용 프로그램에서 데이터를 처리하기에 앞서 먼저 데이터를 어떻게 저장할 것인가를 결정해야 합니다. 이 질문에 대한 답은 데이터를 이용하여 수행할 작업의 종류와 작업 빈도에 따라 달라집니다. 응용 프로그램이 제대로 동작해야 한다는 점은 기본이고, 동시에 지연 시간, 사용 메모리, 또는 기타 매개변수 측면에서 최선의 성능을 제공하도록 구현 방법을 선택해야 합니다.

어떠한 자료 구조를 선택할 것인가를 결정함에 있어 적합한 지표로, 알고리즘 복잡도 또는 시간 복잡도(time complexity)가 있습니다. 시간 복잡도는 특정 작업을 수행하는 데 걸리는 시간을 데이터 크기에 대한 수식으로 표현하는 방식입니다. 따라서 시간 복잡도는 데이터 크기가 변경되면 연산 시간이 어떻게 변하는지를 보여줍니다. 서로 다른 연산의 시간 복잡도는 그 내부에서 데이터를 어떻게 저장하여 사용하는가에 따라 달라집니다.

자료 구조는 크게 연속된 자료 구조와 연결된 자료 구조로 구분할 수 있습니다. 다음 절에서 이 두 가지 구조에 대해 자세히 살펴보겠습니다.