자료구조 리스트

Contents

1. 시작하며...
2. 추상 자료형
3. 리스트
4. 리스트의 ADT
5. 마치며...

시작하며...

구르미의 "Computer Science 정복하기 - 자료구조"의 세 번째 장입니다. 이 장의 대략적인 내용은 다음과 같습니다.

 

• 추상 자료형이 무엇인가
• 리스트란 무엇인가
• 리스트 ADT 정의

 

이 장의 소스코드는 다음을 참고해주세요.

 

url: https://github.com/gurumee92/datastructure

branch: ch03

code directory: src/ch03

 

자 시작합시다!

추상 자료형

추상 자료형 (Abstract Data Type)이란 간단하게 자료구조에 대한 기능의 명세라고 볼 수 있습니다. 우리가 흔히 보는 은행의 계좌를 예를 들어보겠습니다. 우리는 계좌를 통해 무엇을 할 수 있을까요? 저는 크게 다음의 일을 할 수 있다고 생각합니다.

 

• 입금
• 출금
• 잔고 확인

뭐.. 일반적으로 계좌의 주인인지 여부를 판단하거나 그런 기능들이 있겠지만 편의 상 빼도록 하겠습니다. 그럼 계좌의 ADT는 어떻게 쓸 수 있을까요? 제가 정의한 계좌의 추상 자료형 Account는 다음과 같습니다.

 

ADT: Account

 

void Deposit(Account * account, int money);

    - 계좌 account에 money를 저장합니다.

 

int Withdraw(Account * account, int money);

    - 계좌 account에서 money만큼 뺍니다.

    - 만약 잔고보다 많은 양이면, 할 수 없다는 -1을 반환합니다.

 

int GetBalance(Account * account);

    - 계좌 account에서 남은 돈을 확인합니다.

 

이 ADT를 토대로 만든 Account에 대한 소스 코드 account.h, account.c, main.c에서 확인할 수 있습니다.

리스트

자료구조 리스트는 배열과 유사합니다. 배열처럼 데이터를 나란히 저장하며, 중복된 데이터의 저장을 막지 않습니다. 그렇다면 왜 리스트가 만들어졌을까요? 배열은 충분히 좋은 자료구조입니다. 인덱스를 통해서 조회, 추가, 삭제에 대한 연산이 가능하지요. 하지만, 프로젝트가 커지고 복잡해질수록 배열로는 한계가 있습니다. 제일 큰 한계는 다음과 같습니다.

 

배열은 길이가 정해져 있어야 합니다. 저장해야 할 데이터가 길이보다 큰 경우, 데이터들을 저장할 수 없습니다.

 

이것의 한계를 극복하기 위해 나타난 것이 리스트입니다. 리스트는 다음의 2가지로 분류할 수 있습니다.

 

• 동적 배열 기반의 순차 리스트
• 노드 기반의 연결 리스트

동적 배열 기반의 순차 리스트의 경우, 기존의 배열의 한계를 넘어 메모리가 허락하는 한 데이터를 저장할 수 있습니다. 배열과 같이 빠른 인덱스 연산이 큰 장점입니다.

 

반면 노드 기반의 연결 리스트의 경우,노드라는 자기 참조 데이터 타입을 이용하여, 리스트를 만듭니다. 동적 메모리 할당을 이용하지만, 연결 리스트의 경우는 인덱스 연산을 지원하지 않습니다. 대신 순차 리스트보다, 삽입/삭제 면에서 더 좋은 성능을 가지고 있습니다.

리스트의 ADT

다음은 제가 정의한 리스트의 ADT입니다.

 

ADT: List

 

void LInit(List * pList);

- 리스트를 초기화 합니다.

- 리스트 생성 시 제일 먼저 호출됩니다.

 

void LDestroy(List * pList);

- 리스트를 제거합니다.

- 할당된 메모리를 모두 회수합니다.

 

LData LGet(List * pList, int index);

- 해당 인덱스의 원소를 가져옵니다.

- 인덱스의 원소가 없을 경우 에러를 반환합니다.

 

void LSet(List * pList, int index, LData data);

- 해당 인덱스의 원소를 data로 수정합니다.

- 인덱스의 원소가 없을 경우 에러를 반환합니다.

 

int LSize(List * pList);

- 리스트의 크기를 반환합니다.

 

void LInsertHeader(List * pList, LData data);

- 리스트 머리 부분에 data를 삽입합니다.

 

void LInsertIndex(List * pList, int index, LData data);

- 리스트 index 위치에 data를 삽입합니다.

- 만약 리스트 크기보다 크면 에러를 반환합니다.

 

void LInsertTail(List * pList, LData data);

- 리스트 꼬리 부분에 data를 삽입합니다.

 

LData LRemoveHeader(List * pList);

- 리스트 머리 부분에 위치한 data를 삭제합니다.

 

LData LRemoveIndex(List * pList, int index);

- 리스트 index에 위치한 data를 삭제합니다.

- 만약 리스트 크기보다 크면 에러를 반환합니다.

 

LData LRemoveTail(List * pList);

- 리스트 꼬리 부분에 위치한 data를 삭제합니다.

 

마치며...

이번 장에서는 추상 자료형이 무엇인지, 자료구조 리스트가 무엇인지, 리스트의 ADT는 어떻게 되는지 정의하였습니다. 다음 4장부터 6장까지는 정의한 ADT에 맞춰서 3가지 구현체 배열 리스트, 연결 리스트, 이중 연결 리스트를 알아보고 구현보도록 하겠습니다.