자료 구조(data structure)는 데이터를 조직하고 저장하며 필요한 연산을 수행하는 방법이다. 같은 데이터를 보관하더라도 자주 수행하는 연산이 무엇인지에 따라 적합한 구조가 달라진다. 배열·연결 리스트·해시 테이블·트리·힙은 서로 다른 접근과 갱신 비용을 가진 대표적인 예다.
인터페이스와 구현
추상 자료형은 제공할 연산과 그 의미를 설명한다. 큐의 경우 먼저 넣은 항목이 먼저 나오는 규칙을 정하고 삽입과 제거 연산을 제공한다. 그 규칙을 배열 기반으로 구현할지 연결된 노드로 구현할지는 별도의 선택이다.
인터페이스가 같으면 코드를 사용하는 쪽은 같은 의미의 연산을 요청할 수 있지만 구현에 따라 시간과 메모리 비용은 달라진다. 따라서 “목록이다”라는 말만으로 임의 위치 접근이나 중간 삽입이 얼마나 빠른지 결정할 수는 없다.
주요 구조의 특징
배열은 위치를 통해 원소에 접근하기 좋다. 연결 리스트는 노드 사이의 연결로 순서를 표현하므로 이미 알고 있는 노드 근처의 연결 변경과 특정 위치까지 찾아가는 비용을 구분해야 한다. 해시 기반 구조는 키를 이용한 조회를 지원하지만 해시 함수와 충돌 처리 방식이 비용에 영향을 준다.
트리는 계층과 순서 관계를 표현하는 데 쓰이며, 균형 유지 여부에 따라 탐색 경로 길이가 달라질 수 있다. 힙은 우선순위가 높은 원소를 반복해서 꺼내는 용도에 적합하지만 모든 원소가 완전히 정렬된 배열과 같지는 않다. 구조의 이름보다 필요한 연산과 보장 조건을 먼저 확인한다.
예시: 스택으로 최근 작업 되돌리기
Python 3의 리스트를 이용해 간단한 후입선출 스택을 표현할 수 있다. 아래 코드는 작업 이름 두 개를 뒤에 추가한 뒤 pop으로 마지막 항목을 꺼낸다. 출력은 색상 변경과 ['문자 입력']이다. 가장 최근 작업이 먼저 제거되는 순서를 확인할 수 있다.
실제 편집기의 실행 취소 기능은 작업 이름만 저장해서는 부족하다. 원래 상태나 되돌릴 수 있는 변경 정보를 함께 기록해야 한다. 여기서는 스택의 순서 규칙만 보여 준다. 빈 스택에서 제거할 때의 처리 역시 실제 프로그램에서는 정해야 한다.
history = []
history.append("문자 입력")
history.append("색상 변경")
print(history.pop())
print(history)예시: 키로 값을 찾는 사전
두 번째 예제는 사용자 이름을 키로 점수를 찾는 Python 딕셔너리를 사용한다. mina의 점수는 82이며, 존재하지 않는 이름에는 get의 기본값인 None이 반환된다. 이름으로 찾는 요구를 위치 번호로 찾는 목록과 다르게 표현한 것이다.
같은 키에 다시 값을 넣으면 별도의 중복 항목이 늘어나는 것이 아니라 기존 키의 값이 바뀐다. 모든 기록을 시간순으로 보관해야 한다면 이 사전만으로는 요구를 충족하지 못한다. 키별 현재 상태와 변경 이력은 다른 자료 모델이다.
scores = {"mina": 82, "jun": 95}
print(scores["mina"])
print(scores.get("unknown"))선택 사례: 작업 대기열
작업을 도착한 순서대로 처리한다면 큐의 선입선출 의미가 자연스럽다. 최근 작업부터 되돌리려면 스택이 맞고, 가장 긴급한 작업부터 선택하려면 우선순위 큐가 필요하다. 같은 작업 목록이라도 제거 순서의 요구가 다르므로 서로 대체할 수 없다.
처리 도중 임의의 작업을 취소해야 한다면 그 작업을 찾는 방법까지 고려한다. 단순한 큐만으로 충분한지, 작업 식별자를 찾기 위한 추가 자료 구조가 필요한지 검토한다. 자료 구조를 여러 개 함께 쓰면 조회는 편해질 수 있지만 갱신 시 일관성을 유지할 책임도 늘어난다.
성능을 읽는 방법
시간 복잡도는 입력 크기에 따른 작업량의 증가를 설명한다. 평균, 최악, 분할 상환 비용은 서로 다른 보장이므로 표현을 구별한다. 예를 들어 동적 배열의 끝 삽입은 보통 여유 공간에 쓰지만 재할당이 필요한 순간에는 기존 원소를 옮기는 비용이 생길 수 있다.
이론상 비용이 같아도 메모리 배치와 캐시, 객체 할당 방식에 따라 실제 성능이 달라진다. 작은 자료에서는 단순한 구현이 유리할 수 있고, 큰 자료에서는 메모리 사용량과 접근 패턴이 중요해진다. 연산 빈도와 실제 입력을 기준으로 측정한다.
주의할 점
자료 구조가 저장하는 값이 원본 객체의 참조인지 독립적인 복사인지 확인한다. 여러 위치에서 같은 객체를 참조하면 한쪽의 변경이 다른 쪽에 보일 수 있다. 동시에 접근하는 환경에서는 동기화나 변경 책임도 설계해야 한다.
일반적인 구조의 설명과 특정 언어 라이브러리의 보장을 섞지 않는다. 순서 유지, 허용 키, 반복 중 변경, 실패 시 예외 등은 사용하는 구현의 문서를 따라야 한다. 자료 구조를 바꿀 때는 속도뿐 아니라 결과의 의미도 유지되는지 검증한다.