1. Linked List #1 Array based list

3-1 Abstract Data Type

1) ADT 정의

ADT란 무엇일까? 정의 그대로 추상 자료형이라는 것을 의미한다.

 

ADT는 함수 내부 구조가 아니라, 어떤 input을 넣고 어떤 output이 나오며, 전체적인 목적에 의해 어떤 기능을 담당하고 있는지 그 목차를 설명해주는 문서이다.

 

참고로 신기하게 구조체의 정의는 안들어가있다

 

전에 Ts 할 때 Call signiture라는 것을 했던 적이 있다. return 값의 자료형과, parameter의 자료형만 명시하는 형식을 의미한다. ADT도 이런 Call signiture를 적은 이후에 기능을 나열하는 형태다.

int TakeOutMoney(Wallet *pw, int coinNum, int billNum)

- 첫 번째 인자로 전달된 주소는 돈을 꺼내는 대상이다
- 두 번째 인자는 꺼낼 동전의 수, 세 번째 인자는 꺼낼 지폐의 수다
- 꺼내고자 하는 돈의 총액이 반환되고, 돈은 차감된다

2) ADT 활용한 자료구조 학습 순서

필자는 3단계로 나누어 자료구조 학습 방법을 제안한다.

1. 리스트 자료구조의 ADT 정의

2. ADT 근거로 리스트 자료구조 활용하는 main함수 정의

3. ADT 근거로 리스트 구현

ADT 자체도 내부 구조가 아닌, 활용 방법과 기능에 초점이 맞춰져 있다. 따라서 자료구조를 공부할 때는 그 자료구조를 구현하는 방법도 중요하지만, 활용하는 방법에 조금 더 초점이 맞춰져 있다는 것을 알 수 있다.

 

3-2  Arr 를 활용한 리스트 구현

1) 리스트의 종류

• 순차 리스트 : 배열을 중심으로 구현
• 연결 리스트 : 동적 할당을 기반으로 구현 → 이걸 훨씬 많이 쓴다

2) 리스트 자료구조의 특성

1. 데이터를 나란히 저장한다
2. 중복 데이터 저장을 막지 않는다.

이 말을 달리 해석하면, 다른 자료구조들은 데이터를 한 줄, 나란히가 아니라 층층히 구성할 수도 있고, 자료구조 자체적으로 중복 데이터 저장을 막아놓는 종류들도 존재한다는 것을 알 수 있다.

3) Linked List ADT, 기본 기능

리스트 자료구조의 ADT와 사용방법에 대해 간단히 적어보겠다

void ListInit(List* plist)
- 기능 : 초기화 - param : 초기화 할 리스트의 주소
- 호출 위치 : 리스트 생성 후 가장 먼저 호출

void LInsert(List* plist, LData data);
기능 : 삽입
-  param 1 : 데이터를 저장할 대상이 되는 리스트
-  param 2 : 저장할 데이터

int LFirst(List* plist, LData* data)
기능 : 조회
-  param 1 : 데이터를 참조할 대상이 되는 리스트
-  param 2 : 참조한 데이터를 저장할 변수의 주소

int LNext(List* plist, LData* data)
-  기능 : 조회
-  호출 위치 : LFirst 다음에만 호출 가능
-  특징 : 반복 호출 가능

int LRemove(List* plist)
-  기능 : 삭제
-  특징 : LNext, LFirst의 호출을 통해 참조한 데이터 삭제

int LCount(List* plist)
-  기능 : plist 안에 있는 요소의 개수 세기

 

사실 자료구조의 구현도 여기 적어야 할까 고민했는데, 일단 내가 첫 번째로 공부하고 있는 만큼 구현보다는 활용에 초점을 맞추어 정리해보려고 한다