추상 자료형

오늘 첫번째 자료구조인 연결리스트, 그 중에서도 배열 기반 연결리스트의 학습 내용을 요약하려고 한다. 다만, 그 전에 자료구조에서 자주 쓰이는 용어인 추상 자료형에 대한 개념을 확실히 잡고 가도록 하겠다.

추상 자료형 : Abstract Data Type 이란?
: 구체적인 기능의 완성 과정을 언급하지 않고, 순수하게 기능이 무엇인지 나열한 것

말 그대로 전체적인 코드를 구현하기 전에 어떤 기능들이 있을지 나열하는 것이다. 대표적인 예시로 지갑의 기능을 표현해보겠다.
(위 지갑의 예시도 윤성우 <열혈 자료구조> 본서의 내용을 참고했다.)

Wallet 의 ADT 
1. 	int TakeOutMoney (Wallet * pw, int coin, int bill);
2.  void PutMoney (Wallet * pw, int coin, int bill);

위 코드를 간단히 설명해보도록 하겠다. 1번은 지갑에서 돈을 넣는 행위를 표현했고, 2번은 그와 반대인 지갑에서 돈을 빼는 행위를 표현했다. 이로 봤을 때 이 함수의 내부 구현을 하지는 않았지만 우리는 지갑에서 이러한 순수한 기능들을 나열했다고 표현할 수 있다. 이 개념이 추상 자료형 'ADT' 라고 부른다.
다음 한가지 사실만 더 알고 그 다음 리스트에 대한 설명으로 넘어가 보겠다.

• 필요에 따라, 정의하는 주체에 따라 같은 자료구조를 사용하더라도 ADT 마다 차이가 있을 수는 있다.

---

리스트(Linked List)

리스트는 이번에 내가 학습해본 자료구조의 첫 번째 단계이다. 먼저 리스트 자료구조는 구현 방법에 따라서 2가지로 나뉘는 것을 다음을 보면 알 수 있다.

리스트의 구분
1. 순차 리스트 : 배열을 기반으로 구현한 리스트
2. 연결 리스트 : 메모리의 동적 할당을 기준으로 구현한 리스트

여기서 이번 블로그에서 직접 다룰 건 배열 기반 리스트이다. 2번 연결 리스트는 다음 블로그를 통해 확인하면 된다. 여러 자료구조들 중에서 리스트를 사용하는 이유가 무엇일까? 대표적으로 자료구조를 사용하는 이유는 다음과 같다.

• 리스트 자료구조는 데이터를 나란히 저장한다. 중복된 데이터의 저장을 막지 않는다.

즉, 한 배열에서 30이라는 데이터가 이미 들어있다고 가정했을 때 그 배열에 30이라는 수를 또 넣을 수 있다는 것이다. 그러면 다음 리스트의 ADT를 보도록 하겠다.
(위 자료도 윤성우 <열혈 자료구조> 책을 참고했다.)

리스트 자료구조의 ADT

Operations:

void ListInit (List * plist);
- 초기화할 리스트의 주소 값을 인자로 전달하는 함수로 리스트 생성 후 제일 먼저 실행되는 함수

void LInsert (List * plist, Ldata data);
- 리스트에 데이터를 저장

int LFirst (List * plist, LData *pdata);
- 데이터 참조를 위한 초기화로 성공 시 True(1), 실패시 False(0)을 반환

int LNext (List * plist, LData * pdata);
- 순차적인 참조를 위한 반복 호출을 한다. 앞서 있던 LFirst의 함수 호출이 있어야한다.
- 마찬가지로 성공 시 True(1), 실패시 False(0)을 반환

LData LRemove (List * plist);
- 삭제된 데이터의 반환

int LCount (List * plist);
- 리스트에 있는 데이터의 수를 반환

우리는 이 ADT를 보고 배열 기반 리스트가 있을 때 어떤 기능들을 어떻게 표현할지를 유추할 수 있을 것이다. 위 함수를 헤더 파일에 고정하여 소스코드를 작성하였지만, 이는 공유하지 않도록 하겠다. 물론, 윤성우 <열혈 자료구조> 게시판에 있기에 쉽게 검색해서 찾아볼 수 있을 것이다.

시간 복잡도

1) 데이터 탐색
배열 기반 리스트에서 데이터 탐색은 인덱스를 활용하기에 바로 탐색이 가능하다.
즉, 데이터 탐색의 시간 복잡도는 O(1)이다.

2) 데이터 추가
배열 기반이기에 모든 데이터들은 순차적으로 저장되어있다. 그렇기에 최악의 경우는 맨 앞에 데이터를 추가하면 뒷 자료들을 다 n만큼 이동시켜줘야하기 때문에 이럴 경우는 O(n)이고, 맨 마지막에 넣는 최선의 경우는 O(1)로 표현할 수 있다.

3) 데이터 삭제
'2) 데이터 추가'와 마찬가지이다.

배열 기반 연결리스트의 장, 단점

배열 기반 연결리스트의 소스코드를 작성해보면서 느끼는 자료구조의 장, 단점들이 있었다. 이를 요약하고 이번 블로그 글을 마무리하려고 한다.

배열 기반 연결리스트의 장 단점
장점)

• 배열을 기반으로 했기에 데이터의 참조가 쉽다.
• 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.

단점)

• 배열의 길이를 초기에 결정하기에, 변경을 중간에 할 수가 없다.
• 삭제의 과정에서 이동을 다 해야한다는 단점이 있다.

---

이렇게 오늘은 배열 기반 연결 리스트에 대하여 알아보았다. 내일은 연결 기반 연결리스트에 대하여 학습해보고 정리하도록 하겠다.