[연결리스트] #2. 리스트와 ADT

추상 자료형(abstract data type, ADT)

추상자료형: 자료들과 그 자료들에 대한 연산들을 명기한 것이다. 

• 저장된 데이터
• 데이터에 대한 작업들
• 작업 중 발생 가능한 에러 상황들

추상적 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료 구조와 다르다.

추상적 자료 구조	각 연산의 시간 복잡도를 명기함
추상적 자료형	각 연산의 시간 복잡도를 명기하지 않음

 

추상적 자료형은 인터페이스와 구현을 분리하여 추상화 계층을 둔 것이다.
잘 알려진 추상 자료형에는 복소수, 리스트, 스택, 큐, 맵, 우선순위 큐, 집합 등이 있다.

리스트 ADT:  연속적인 임의 개체 모델링원소에 대한 접근 도구

직접 응용	- 스택, 큐, 집합 등을 표현하기 위한 도구 - 소규모 데이터베이스
간접응용	더 복잡한 데이터 구조를 구축하기 위한 재료로 사용

예외

예외: 어떤 ADT 작업을 실행하고자 할 때 발생할 수 있는 오류 상황.

 

리스트 ADT에서 발령 가능한 예외들

• invalidRankException()
•  fullListException()
• emptyListException()

단일연결리스트

단일연결리스트: 연속 노드로 구성된 구체적인 데이터구조

단일연결리스트

각 노드의 저장 내용

• 원소
• 다음 노드를 가리키는 링크

리스트

이중연결리스트

이중연결리스트: 리스트 ADT를 자연스럽게 구현가능

이중연결리스트

각 노드의 필드

• 원소
• 이전 노드를 가리키는 링크
• 다음 노드를 가리키는 링크