3. 연결리스트 1 (ADT + 배열기반 연결리스트)

1. 추상 자료형: Abstract Data Type

 

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

 

ex) 지갑의 추상 자료형
∙  카드 넣기 ∙ 카드 빼기 ∙ 동전 넣기 ∙ 동전 빼기 ∙ 지폐 넣기 ∙ 지폐 빼기

▶ 자료형 Wallet의 정의

typedef struct _wallet 
{
    int coin100Num;      // 100원짜리 동전의 수 
    int bill5000Num;      // 5,000원짜리 지폐의 수 
} Wallet;

※ 완전한 자료형의 정의로 인식되기 위해서는 해당 자료형과 관련이 있는 연산이 함께 정의되어야 한다

 

▶ 자료형 Wallet 정의의 일부

int TakeOutMoney(Wallet * pw, int coinNum, int billNum);    // 돈 꺼내는 연산
void PutMoney(Wallet * pw, int coinNum, int billNum);        // 돈 넣는 연산

 

▶ Wallet 기반의 main

int main(void) 
{ 
   Wallet myWallet;        // 지갑 하나 장만 했음! 
   PutMoney(&myWallet, 5, 10);       // 돈을 넣는다. 
   ret = TakeOutMoney(&myWallet, 2, 5);    // 돈을 꺼낸다. 
}

 

 

▶ 자료구조 학습의 옳은 순서

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

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

3. ADT를 근거로 리스트를 구현한다.

 

---

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

 

 

---

 

▶  배열 기반 리스트

typedef  struct __ArratList
{
  Data arr[size];
  int numOfData;
  int curPosition
} ArrayList;

 

 

//초기화
void ListInit(List* pList)
{
	pList->numOfData = 0;
	pList->curPosition = -1;
}

//삽입
void ListInsert(List* pList, LData data)
{
	if (pList->numOfData >= Listsize)
	{
		cout << "저장공간 없음" << endl;
		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];
	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)
{
	int rpos = pList->curPosition;
	int num = pList->numOfData;
	int i;
	LData rdata = pList->arr[rpos];

	for (i = rpos; i < num - 1; i++)
	{
		pList->arr[i] = pList->arr[i + 1];
	}

	pList->numOfData--;
	pList->curPosition--;

	return rdata;
}

 

배열리스트 삭제

 

---

▶  배열 기반 리스트의 장점 

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

 

▶  배열 기반 리스트의 단점 

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