작업에 맞춰 정하는 구조
도착 순서대로 처리하는 인쇄 작업과 이름으로 찾는 연락처 목록은 요구하는 연산이 다르다. 전자는 먼저 들어온 항목을 꺼내는 것이 중요하고, 후자는 특정 이름의 값을 찾는 일이 중요하다. 자료 구조는 이런 작업의 비용에 영향을 준다.
어떤 구조가 무조건 가장 빠르다고 말하기는 어렵다. 데이터의 개수와 변화 빈도, 사용하는 메모리, 실제 접근 패턴을 함께 보아야 한다.
배열과 연결 구조
배열은 원소를 순서대로 배치하여 위치를 이용한 접근에 적합하다. 중간에 새 항목을 넣기 위해 뒤의 원소를 옮겨야 하는 경우도 있다. 동적으로 크기를 늘리는 구현은 새 공간 할당과 복사 비용을 추가로 고려한다.
연결 리스트는 각 원소가 다음 원소 등의 연결 정보를 가진다. 이미 위치를 알고 있는 노드 주변의 연결 변경과, 그 위치를 찾기 위해 순회하는 작업의 비용은 구분해야 한다.
계층과 키를 이용한 탐색
트리는 원소 사이의 계층적 관계를 표현한다. 정렬된 탐색 트리는 키의 대소 관계를 이용해 찾을 범위를 줄일 수 있지만, 균형을 어떻게 유지하는지에 따라 효율이 달라진다.
해시 테이블은 키의 해시값을 이용해 저장 위치를 정한다. 서로 다른 키가 같은 위치 후보로 모이는 충돌을 처리해야 하며, 빠른 평균 탐색이 모든 입력에 대한 동일한 최악 시간까지 보장하는 것은 아니다.
규칙과 구현을 구분하기
스택은 나중에 넣은 것을 먼저 꺼내고 큐는 먼저 넣은 것을 먼저 꺼내는 규칙으로 설명한다. 이러한 추상적인 동작 규칙은 배열이나 연결 구조 등 서로 다른 내부 표현으로 구현할 수 있다. 외부에서 약속한 연산과 내부 배치를 나누어 이해하는 것이 중요하다.