3. 연결 리스트 1

3-1. 추상자료형

 

* 자료구조에서의 추상자료형

구체적인 기능의 완성과정은 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것이다.

 

* 구조체 Wallet의 추상자료형 정의

Operation:

• int TakeOutMoney(Wallet* pw, int coinNum, int billNum)
  • 첫번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.
  • 두번째 인자로 꺼낼 동전의 수, 세번째 인자로 꺼낼 지폐의 수를 전달한다.
  • 꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.

• void PutMoney(Wallet* pw, int coinNum, int billNum)
  • 첫번째 인자로 전달된 주소의 지갑에 돈을 넣는다.
  • 두번째 인자로 넣을 동전의 수, 세번째 인자로 넣을 지폐의 수를 전달한다.
  • 넣은만큼 동전과 지폐의 수가 증가한다.

 

(2) 배열을 이용한 리스트의 구현

 

* 리스트의 이해

리스트라는 자료구조는 구현방법에 따라서 크게 두 가지로 나뉜다.

• 순차 리스트: 배열을 기반으로 구현된 리스트
• 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트

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

 

* 배열 기반 리스트의 ADT

Operation:

• void ListInit(List* plist)
  • 초기화할 리스트의 주소 값을 인자로 전달한다.
  • 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

• void LInsert(List* plist, LData data)
  • 리스트에 데이터를 저장한다. 매개번수 data에 전달된 값을 저장한다.
• int LFirst(List* plist, LData* pdata)
  • 첫번째 데이터가 pdata가 가리키는 메모리에 저장된다.
  • 데이터의 참조를 위한 초기화가 진행된다.
  • 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환
• int LNext(List* plist, LData* pdata)
  • 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다.
  • 순차적인 참조를 위해서 반복 호출이 가능하다.
  • 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.
  • 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환
• LData LRemove(List* plist)
  • LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.
  • 삭제된 데이터는 반환된다.
  • 마지막 반환 데이터를 삭제하므로 연이은 반복 호출은 허용하지 않는다.
• int LCount(List* plist)
  • 리스트에 저장되어 있는 데이터의 수를 반환한다.

 

* 배열 기반 리스트의 구현

#define TRUE 1 // 참을 표현하기 위한 매크로 정의
#define FALSE 0 // 거짓을 표현하기 위한 매크로 정의
#define LIST_LEN 100

typedef int LData; // LData에 대한 typedef 선언
typedef struct __ArrayList { // 배열기반 리스트를 정의한 구조체
	LData arr[LIST_LEN]; // 리스트의 저장소인 배열
	int numOfData; // 저장된 데이터의 수
	int curPosition; // 데이터 참조위치 기록
} ArrayList;
typedef	ArrayList List;

void ListInit(List* plist) { // 초기화
	plist->numOfData = 0; // 리스트에 저장된 데이터의 수는 0
	plist->curPosition = -1; // 현재 아무 위치도 가리키지 않음
}

void LInsert(List* plist, LData data) { // 데이터 저장
	if (plist->numOfData >= LIST_LEN) { // 더 이상 저장할 공간이 없다면
		printf("저장이 불가능합니다.");
		return;
	}
	plist->arr[plist->numOfData] = data; // 데이터 저장
	plist->numOfData++; // 저장된 데이터 수 증가
}

int LFirst(List* plist, LData* pdata) { // 첫 데이터 참조
	if (plist->numOfData == 0) // 저장된 데이터가 하나도 없다면
		return FALSE;
	plist->curPosition = 0; // 첫 번째 데이터의 참조
	*pdata = plist->arr[0]; // pdata가 가리키는 공간에 데이터 저장
	return TRUE;
}

int LNext(List* plist, LData* pdata) { // 두 번째 이후 데이터 참조
	if (plist->curPosition >= plist->numOfData - 1) // 더 이상 참조할 데이터가 없다면
		return FALSE;
	plist->curPosition++; // 다음 데이터 참조
	*pdata = plist->arr[plist->curPosition];
	return TRUE;
}

LData LRemove(List* plist) { // 참조한 데이터 삭제
	LData rdata = plist->arr[plist->curPosition]; // 삭제할 데이터를 임시로 저장
	// 삭제를 위한 데이터의 이동을 진행하는 반복문
    for (int i = plist->curPosition; i < plist->numOfData - 1; i++)
		plist->arr[i] = plist->arr[i + 1];
	plist->numOfData--; // 데이터의 수 감소
	plist->curPosition--; // 참조한 데이터가 삭제됐으므로 참조 위치를 하나 되돌린다.
	return rdata; // 삭제된 데이터의 반환
}

int LCount(List* plist) { // 저장된 데이터의 수 반환
	return plist->numOfData;
}

 

* 배열 기반 리스트의 장단점

배열 기반 리스트의 단점

• 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
• 삭제의 과정에서 데이터의 이동이 매우 빈번히 일어난다.

배열 기반 리스트의 장점

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