2. Data Structures and Dynamic Arrays
강의 초입 부분에 인터페이스와 자료구조의 다른점을 짚고 넘어 감.
Interface (API / ADT)
- 인터페이스(API, ADT 추상 데이터 타입)에 대한 내용
- "무엇"에 집중
Specification (어떤 명세를 가지는지)
- 인터페이스의 명세는 인터페이스가 어떤 기능을 제공하는지를 기술
- 사용자가 인터페이스를 통해 수행할 수 있는 작업들을 정의
What data can store (어떤 데이터를 저장할 수 있는지)
- 인터페이스가 다룰 수 있는 데이터의 종류를 정의
- 예를 들어, 리스트 인터페이스는 정수, 문자열 등 다양한 타입의 요소들을 저장할 수 있다는 둥.
What operations are supported (어떤 연산을 지원하는지)
- 인터페이스를 통해 수행할 수 있는 연산들을 정의합
- 예를 들어, 리스트 인터페이스는 요소 추가(add), 삭제(remove), 검색(find) 등의 연산을 지원할 수 있다는 둥.
자료 구조
- 자료 구조는 데이터를 실제로 어떻게 저장하고 관리할지를 정의
- "어떻게"에 집중
Representation (어떻게 표현할지)
- 자료 구조의 표현은 데이터를 메모리나 다른 저장 매체에 어떻게 배치할지를 정의
- 예를 들어,
- 배열: 연속된 메모리 블록에 데이터를 저장
- 링크드 리스트: 각 요소가 다음 요소에 대한 참조를 포함하는 방식으로 데이터를 저장
How to store data (어떻게 저장할지)
- 데이터를 실제로 저장하는 방법을 구체적으로 설명
- 예를 들어,
- 배열: 인덱스를 통해 요소에 접근
- 트리: 노드와 간선으로 데이터를 저장
Algorithms to support operations (어떻게 연산할지 알고리즘)
- 자료 구조가 제공하는 연산들을 어떻게 구현할지를 설명
- 예를 들어 이진 검색 트리는 삽입, 삭제, 검색 연산을 효율적으로 수행하기 위한 알고리즘을 제공
Word RAM(Random Access Machine) Model
- 자료구조들은 이 모델에
- 자세한 건 다른 페이지에 정리해둠