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

• 우리가 더 흥미로운 데이터 구조에 도달할수록 이 모델이 정말로 필요하게 될 것이며, 점점 더 이 모델에 의존하게 될 것이다.
• 자세한 건 Word RAM Model 페이지에 정리해둠