열혈 자료구조 - 3-2. 배열을 이용한 리스트의 구현(2)

배열 기반 리스트 구현

- 배열 기반 구현을 위한 선언

    -> 저장하고 싶은 자료형을 바꾸고 싶으면 LData의 typedef 자료형을 바꾸면 됨

    -> curPosition은 LFirst, LNext 같이 배열에 저장된 데이터를 순차적으로 참조할 때 사용되는 변수

#define TRUE  1
#define FALSE 0
#deinf LIST_LEN 100

typdef int LData;	// 자료를 저장할 대상의 자료형 

typedef struct __ArrayList {
    LData arr[LIST_LEN];
    int numofData;			// 데이터의 수
    int curPosition;		// 데이터의 참조 위치
} ArrayList;

typedef ArrayLIst List;

- 초기화

    -> curPosition은 구현자마다 -1 또는 0으로 설정할 수 있고 이 curPosition을 사용하는 함수들을 각각 값에 맞게 구현하면 됨

void ListInit(List * plist)
{
	(plist->numOfData) = 0;			// 데이터의 수를 초기화
	(plist->curPosition) = -1;		// -1은 아무런 위치도 참조하지 않음을 의미
}

- 삽입

void LInsert(List * plist, LData data)
{
	if(plist->numOfData > LIST_LEN) 
	{
		puts("저장이 불가능합니다.");
		return;
	} // 배열이 꽉 찼다는 의미

	plist->arr[plist->numOfData] = data;
	(plist->numOfData)++;		// 데이터의 수 증가
}

- 조회

    -> LFirst에서 arr의 인덱스를 0으로 한 이유는 첫번째 위치의 값을 반환한다는 것을 명시적으로 보여주기 위함

int LFirst(List * plist, LData * pdata)
{
	if(plist->numOfData == 0)		// 데이터 갯수가 0이면 FALSE 반환
		return FALSE;

	(plist->curPosition) = 0;		// 데이터의 참조 위치를 첫번째로 설정
	*pdata = plist->arr[0];			// 리스트의 0번째 인덱스 값을 pdata에 대입
	return TRUE;
}

int LNext(List * plist, LData * pdata)
{
	if(plist->curPosition >= (plist->numOfData)-1)		// 더 참조할 대상이 없을 경우 FALSE 반환
		return FALSE;

	(plist->curPosition)++;			// 데이터의 참조 위치를 증가
	*pdata = plist->arr[plist->curPosition];	// 리스트의 참조 위치의 인덱스 값을 pdata에 대입
	return TRUE;
}

- 삭제

    -> 삭제되는 데이터를 반환하고 삭제 후 빈 공간을 앞으로 땡겨서 채움

    -> curPosition을 감소시키는 이유는 LNext 실행 시 curPosition을 증가 시킨 후 그 위치의 값을 반환하는데 curPosition을 감소시키지 않으면 삭제 시켰던 위치에 있는 데이터는 참조가 되지 않음

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;
}

- 데이터의 개수

int LCount(List * plist)
{
	return plist->numOfData;
}

 

배열 기반 리스트의 장단점

- 장점

    -> 인덱스 값만을 기준으로 하기 때문에 데이터 참조가 쉬움

- 단점

    -> 배열의 길이가 초기에 결정되어야 함

    -> 삭제의 과정에서 데이터의 이동이 빈번히 일어남

- 배열 자체의 일반적인 장단점이라고도 할 수 있음