[엘리스 AI트랙] 03-05-01 ~ 자료구조

1. 자료구조

• 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공한 것
• 각각 장단점이 있으며 구현하고자 하는 프로그램의 성능을 고려하여 알맞은 자료구조를 선택해야함

 

2. 추상적 자료형

• 어떤 자료와 그 자료에 대한 연산(동작)들의 수학적인 정의
• 이 정의를 구현하는 방법은 명시되어 있지 않음
• 추상적 자료형을 구체적으로 구현한 결과가 자료구조

3. 리스트 (추상적 자료형)

• 순서가 존재하며, 일렬로 나열된 값들이 들어있음

(1) 배열 (구현)

• 인덱스 가지고 있음
• 특정 위치의 자료 탐색 유리

(2) 연결 리스트(구현)

• 일렬로 저장된 값들이 노드의 형태로 저장되어 있음
• 자료의 삽입, 삭제에 유리

(3) 해시 테이블

• 충돌 해결 방법: 오픈 어드레싱
  • 충돌이 발생했을 때 자료를 저장하기 위해 빈 공간을 탐색하는 방식
  • 모든 원소가 자신의 해시 값과 일치하는 인덱스에 저장된다는 보장은 없