[자료구조] 배열을 기반으로 구현한 List에서 "삭제" 구현

배열을 기반으로 구현한 List에서 "삭제"를 담당하는 LRemove 함수를 정의할 때 

인덱스와 데이터의 개수 때문에 자주 헷갈리는 부분을 정리하려고 한다.

위와 같이, C라는 데이터를 삭제하는 함수를 구현한다고 해보자.

이때 C라는 데이터가 삭제되고 나면, 뒤에 저장된 나머지 데이터들은 한칸씩 앞으로 이동시켜서 그 빈공간을 메꿔야 할 것이다.

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

위 코드에서 헷갈리는 부분은 for문의 구현이다.

i가 어디서부터 참조를 시작해서, 몇번 반복해야하는지 직접 구현하려하면 조금 헷갈려서 정리하려고 한다.

 

1. 참조 시작

참조 시작은 내가 지금 삭제할 위치에서부터 시작한다.

예를 들어 C라는 데이터가 현재 index = 2를 가지고 있고 rpos(현재 위치)가 index = 2를 가리키고 있다면,

for문을 시작할때 지금 위치인 rpos에서부터 시작하면된더. 비교적 간단하게 정리할 수 있다.

 

2. 몇번 반복?

몇번을 반복할지는, 내가 앞으로 당길 데이터의 개수가 몇개인지를 확인해야한다.

이렇게 생각하면 쉬울 것 같지만, for문을 구현해보면 다음과 같은데

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

이를 보면 rpos에서 시작해서 num-1 전까지 반복?? 이게 내가 앞으로 당길 데이터의 개수인가??

왜 num까지 반복하지 않지?? 직접 와닿지가 않는다.

이게 헷갈리는 이유는 기본적으로 배열의 인덱스가 0부터 시작한다는 것에 있다.

 

i  = num -2까지 반복되는 이유는 천천히 생각해보면 다음과 같다.

for문의 맨 마지막 실행은 i = num-2 일때인데, 이 실행은 다음과 같은 결과를 낳는다

plist->arr[num-2] = plist->arr[num-1]

즉 arr[num-1]의 값을 arr[num-2]에 넣으라는 것인데 현재 num(전체 데이터의 개수)는 8이므로,

다시 말하면 arr[7](arr의 맨 마지막 값)의 값을 arr[6]에 넣으라는 것이다.

 

"arr의 맨 마지막 값을 앞으로 당겼으니, 이제 더이상 for문을 돌려도 되지 않겠구나.

그럼 for문은 i = num-2까지만 돌면 되겠네!

그래서 for(i=rpos; i<num-1; i++) 으로 반복횟수를 구현하면 되겠구나"

 

항상 코드를 구현할 때 이렇게 복잡하게 생각해서 구현할 수는 없으므로, 간단하게 기준을 세워야한다.

데이터의 개수를 기준으로 생각할 것인지, 인덱스를 기준으로 생각할 것인지를 정해야하는데

여러 시행착오를 겪은결과 인덱스를 기준으로 생각하는 것이 더 쉽다.

그리고 그 기준이 되는 인덱스는 배열에서 제일 마지막 요소의 인덱스가 무엇인가?를 찾으면 끝이다.

어떤 배열에서 데이터의 총 개수가 n개라고 하면, 그 배열의 가장 마지막 인덱스는 n-1이다.

C언어에서는 배열의 인덱스가 0부터 시작하므로, 총 데이터의 개수와 인덱스가 1이 차이나는 점을 잘 기억하자.

위 코드에서는 for문에서 배열의 맨 마지막 index는 num-1일 것이므로

plist->arr[i] = plist->arr[i+1]에서 arr[i+1]이 arr[num-1]과 같아야한다.

따라서, 맨 마지막에 실행되어야할 i는 num-2가 되는 것을 알 수 있다.

그래서, for문은 i = rpos에서 i = num-2까지 반복되어야하고 따라서 for문의 코드 구현은 다음과 같다.

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