이번에는 리스트ADT를 알아볼겁니다.
우선 ADT를 먼저 알아야합니다.
추상자료형(ADT)이란 데이터구조의 추상형을 말한다고 하는데....조금 더 쉽게 말하자면 어떤 자료형이 있으면 그 자료형에 대한 연산을 명세한 것을 ADT라고 부르는 것입니다.
따라서 다음을 명세한다고 정리할 수 있겠습니다
1. 저장된 데이터
2. 데이터에 대한 작업들
3. 작업 중 발생 가능한 에러 상황들
예를 들어서 주식거래 시스템 ADT를 짠다고 하면
1. 데이터 : buy/sell 주문들
2. 지원하는 작업들
buy, sell, cancel 등이 있을 수 있다.
3. 에러 상황들 : 존재하지 않는 주식에 대한 buy/sell 주문, 존재하지 않는 주문에 대한 cancel
정말 쉽게 얘기하자면
그리고 실제로 C언어를 공부하다보면 int, char, 포인터 이런 여러 자료형이 있잖아요? int 자료형 끼리는 +.-.*,/,% 이런 연산이 가능하고 포인터에서는 ++, -- 이러한 연산이 가능한 것 처럼
우리가 자료형을 만든다면 이 자료형의 주제에 대한 연산도 있어야 한다는 겁니다.
자료구조에는 여러가지 ADT가 있는데 그 중 대표적으로 리스트ADT가 있습니다.
리스트ADT는 원소들의 순서집단을 저장하기 위한 "기초적인" 데이터구조입니다. 그래서 이 리스트를 활용해서 여러가지 자료구조를 또 만들 수 있어요
그리고 기본적인 메쏘드도 여러가지를 가지는데
초기화, 삽입, 제거, 순회, get 그리고 에러상황들에 대한 예외들(부적합한 순위, 리스트 full, 비어있는 list)가 있습니다.
이러한 리스트를 응용할 수 있는데 직접응용과 간접응용으로 나뉩니다.
직접응용
1. 스택 큐 집합 등을 표현하기 위한 도구
2. 소규모 데이터베이스 구축
간접응용
1. 복잡한 데이터구조 구축 재료
그러면 이제 직접 리스트ADT를 구현하기 위해서 우리는 배열, 연결리스트를 사용할 수 있습니다.
그중에서 저는 헤더와 트레일러 노드가 있는 이중연결리스트를 구현해보도록 하겠습니다.
연결리스트를 이용한 구현->이중연결리스트
마지막으로 배열과 연결리스트의 성능을 비교하고 끝내도록 하겠습니다~
성능요약
| 작업 | 배열 | 연결리스트 |
| size, isEmpty | 1 | 1 |
| get, set | 1 | n |
| add, remove | n | n |
| addFirst, removeFirst | n | 1 |
| addLast, removeLast | 1 | 1 |
