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

리스트의 이해

리스트는 크게 두 가지, 1. 순차 리스트와 2. 연결 리스트로 나눌 수 있다.

1. 순차 리스트는 '배열'을 기반으로 구현된 리스트를 말하며,

2. 연결 리스트는 '메모리의 동적 할당'을 기반으로 구현된 리스트로

이 두가지는 '구현 방법'을 기준으로 구분지었다는 것을 알 수 있다.

다만 이 구현 방법이 '어떻게 구현을 하느냐' 가 달라지는 것이지 그에 따라 제공되는 기능이 달라지는 것은 아님을 알고 가야 한다.

 

이러한 리스트는 두가지 특징을 가지고 있는데

1. 저장 형태는 '데이터를 나란히(하나의 열로) 저장한다는 것과

2, 중복되는 데이터의 저장을 허용하는 특성이 있어

이 특징들을 유지하려다 보니 배열과 연결의 형태가 갖춰지는 것이라고 이해할 수 있다.

 

리스트 자료구조의 ADT

여기서 LData는 저장 대상의 자료형을 결정할 수 있도록 typedef 로 선언된 자료형의 이름이다.

ADT는 #10에서 언급했듯이 기능에 대해서만 명세를 해놓았다.

 

하나씩 함수에 대해서 설명해보면

1. ListInit : 리스트의 초기화 역할을 담당한다. 인자로 초기화할 리스트의 주소값을 전달하는데, 이 리스트는 초기화 함수 호출 이전에 선언되어야 할 것이다.

2. LInsert : 리스트에 값을 저장시키는 함수이다. 첫번째 인자로 제공하는 리스트에 두번째 인자로 제공하는 값을 저장할 것이다.

3. LFirst : plist에 할다된 리스트에서 첫번째로 저장된 값을 반환한다. 두번째 인자인 pdata에 인덱스 0번째의 값을 전달하고, 함수 자체는 반환 성공 여부를 True/False 로 반환하여 두 가지의 값을 이용할 수 있게 된다.

 

4. LNext : 첫번째 데이터를 받을 때는 LFirst 를 사용하는데, 이후부터는 이 LNext 함수를 사용해 데이터를 반환받을 것이다. LFirst 와 LData를 구분지은 이유로는 추후에 설명할 '더미 노드'의 부재도 있지만, 여기서의 LFirst 는 '조회'의 의미 또한 가지고 있다. 예를 들어 2, 3, 4... 번째를 조회하다가 다시 첫 인자를 조회할 필요가 있을 경우에 LNext 만으로는 현재 +1 의 인덱스를 조회할 것이기 때문에 LFirst 를 통해 다시 처음으로 돌아갈 수 있도록 하는 것이다.

5. LRemove : 현재 참조하고 있는 데이터를 지우는 기능을 담당한다.이후에 사용할 수 있도록 삭제한 값을 반환한다.

6. LCount : plist 에 저장된 총 데이터의 수를 반환한다 vector.size() 를 생각하면 이해가 편할 것이다.

 

이제 코드를 보면서 활용 예시를 살펴볼건데, 그 전에 코드 전문을 첨부한다.

// ListMain.c
#include <stdio.h>
#include "ArrayList.h"

int main(void)
{
	/*** ArrayList의 생성 및 초기화 ***/
	List list;
	int data;
	ListInit(&list);

	/*** 5개의 데이터 저장 ***/
	LInsert(&list, 11);  LInsert(&list, 11);
	LInsert(&list, 22);  LInsert(&list, 22);
	LInsert(&list, 33);

	/*** 저장된 데이터의 전체 출력 ***/
	printf("현재 데이터의 수: %d \n", LCount(&list));

	if(LFirst(&list, &data))    // 첫 번째 데이터 조회
	{
		printf("%d ", data);
		
		while(LNext(&list, &data))    // 두 번째 이후의 데이터 조회
			printf("%d ", data);
	}
	printf("\n\n");

	/*** 숫자 22을 탐색하여 모두 삭제 ***/
	if(LFirst(&list, &data))
	{
		if(data == 22)
			LRemove(&list);
		
		while(LNext(&list, &data))
		{
			if(data == 22)
				LRemove(&list);
		}
	}

	/*** 삭제 후 저장된 데이터 전체 출력 ***/
	printf("현재 데이터의 수: %d \n", LCount(&list));

	if(LFirst(&list, &data))
	{
		printf("%d ", data);
		
		while(LNext(&list, &data))
			printf("%d ", data);
	}
	printf("\n\n");
	return 0;
}

//ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define TRUE	1
#define FALSE	0

/*** ArrayList의 정의 ****/
#define LIST_LEN	100
typedef int LData;

typedef struct __ArrayList
{
	LData arr[LIST_LEN];
	int numOfData;
	int curPosition;
} ArrayList;


/*** ArrayList와 관련된 연산들 ****/
typedef ArrayList List;

void ListInit(List * plist);
void LInsert(List * plist, LData data);

int LFirst(List * plist, LData * pdata);
int LNext(List * plist, LData * pdata);

LData LRemove(List * plist);
int LCount(List * plist);

#endif

여기서 ArrayList.c도 같이 첨부를 하는데 이 내용은 보지 않는 것을 추천한다.

모든 자료구조는 내부의 기능 정의가 어떻게 되어있는지 몰라도 외부에서 함수를 사용할 수 있는 방향성을 추구할 뿐만 아니라, 직접 구현해보는 것도 좋은 학습 방법의 일환이 될 것이다.

//ArrayList.c
#include <stdio.h>
#include "ArrayList.h"

void ListInit(List * plist)
{
	(plist->numOfData) = 0;
	(plist->curPosition) = -1;
}

void LInsert(List * plist, LData data)
{
	if(plist->numOfData > LIST_LEN) 
	{
		puts("저장이 불가능합니다.");
		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;
}

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

 

이제 코드를 하나씩 살펴보자.

List list; //리스트의 생성
ListInit(&list); //리스트의 초기화

리스트를 생성하고, 생성한 리스트를 초기화하는 과정이다.

여기서 이 ListInit()이 내부적으로 어떻게 정의되어 있는지 몰라도 써도 되냐? 라고 묻는다면 그렇다 라고 답한다.

호출하는 입장에서는 내부 기능이 완벽하게 구현되어 있다고 믿고 사용하는 것이다.

다시 말해서, 라이브러리에서 제공하는 기능은 그대로 사용하되, 어떻게 쓰면 된다 는 내용을 알려주면 그에 맞게 사용하면 되는 것이다.

 

LInsert(&list, 11); ...

LInsert 를 통해 데이터를 저장하는 과정이다. main 에서는 총 [11, 11, 22, 22, 33] 을 저장하였다.

알아두어야 할 점은 이 데이터들이 '나란히' 저장되었다는 것이다. 물론 내부적으로 이 순서가 [11, 11, 22, ...] 인지 [33, 22, 22, ...] 인지에 대해서는 당장은 알 수 없지만 나란히 저장된다는 것을 알고 그에 맞춰서 활용하면 된다.

 

if(LFirst(&list, &data))    // 첫 번째 데이터 조회
{
	printf("%d ", data);
		
	while(LNext(&list, &data))    // 두 번째 이후의 데이터 조회
	printf("%d ", data);
}

LFirst 와 LNext를 통해서 데이터를 참조하는 과정이다.

먼저 LFirst를 보면 이전에 생성했던 list 의 주소값을 첫번째 인자로, 첫번째 인덱스 값을 저장할 변수 data의 주소값을 두번째 인자로 전달한다.

또한 LFirst가 true/false 를 반환하는 것을 이용해 조건문으로 사용하였고 printf 를 통해 data를 출력한다.

이후부터는 LNext를 통해 데이터를 순차적으로 참조하고 있다.

 

/*** 숫자 22을 탐색하여 모두 삭제 ***/
if(LFirst(&list, &data))
{
	if(data == 22)
	LRemove(&list);
		
	while(LNext(&list, &data))
	{
		if(data == 22)
		LRemove(&list);
	}
}

데이터를 삭제하기 위해서는 어떤 데이터인지 확인하는 과정이 필요하기 때문에 반드시 데이터를 참조하는 동작이 동반된다.

그 이유로 LFirst와 LNext 이후에 LRemove 가 나타나는 것인데, 코드에는 LRemove의 인자로 list의 주소값만 들어가고 어떤 데이터를 지울 것인지에 대한 정보가 들어있지 않다.

이는 LRemove가 '가장 최근에 참조한 데이터를 삭제한다' 라는 암묵적 의미가 들어가있는 것으로 기능의 정의 과정에서 확인할 필요가 있는 동작이지만, 일반적으로는 데이터를 참조한 이후에 삭제하는 과정이 진행된다.

 

배열 기반 리스트의 헤더파일 정의

프로그래밍 실력은 사실 c/cpp 파일이 아니라 .h 헤더파일에서 파악된다고 봐도 과언이 아니다.

먼저 위에서 사용한 ArrayList의 헤더파일을 보면

//ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define TRUE	1
#define FALSE	0

/*** ArrayList의 정의 ****/
#define LIST_LEN	100
typedef int LData;

typedef struct __ArrayList
{
	LData arr[LIST_LEN];
	int numOfData;
	int curPosition;
} ArrayList;


/*** ArrayList와 관련된 연산들 ****/
typedef ArrayList List;

다음과 같이 파악할 수 있다.

여기서 LData가 보이는데 이는 typedef 로 선언해 저장할 대상의 자료형을 변경을 위한다.

배열 기반 리스트를 의미하는 구조체 ArrayList 또한 준비되어 있으며 배열의 길이를 의미할 LIST_LEN, 저장된 총 숫자를 뜻할 numOfData, 현재 참조하는 데이터를 가리킬 curPosition 을 멤버로 선언해주었다.

마지막으로 리스트의 변경을 용이하게 하기 위해 ArrayList를 typedef로 선언해주었다.

 

typedef : 형식 정의

자료형을 재정의하는 방식으로 사용한다.

 

예제코드

typedef unsigned int MyUInt;

MyUInt uiNum;
uiNum = 10u;
	printf("uiNum : %u", uiNum);// 10출력

 

ListInit 정의

구조체를 다시 확인해보면 다음과 같이 작성되어 있다.

typedef struct __ArrayList
{
	LData arr[LIST_LEN];
	int numOfData;
	int curPosition;
} ArrayList;

여기서 LIST_LEN은 #define 으로 정의해주었기에 실질적으로 초기화할 대상은 numOfData 와 curPosition 으로 두가지 멤버이다.

초기화 함수를 정의해보면

void ListInit(List *plist)
{
	(plist->numOfData) = 0;
    (plist->curPosition) = -1;
}

다음과 같이 작성할 수 있다.

numOfData의 0은 초기에 어떠한 값도 참조하지 않고 있다, 즉 리스트의 길이가 0임을 나타내고 있고,

curPosition의 -1은 사실 LFirst와 LNext를 이후에 어떻게 정의하느냐에 따라 초기화하는 값이 달라질 수 있는데 여기서는 아무런 위치도 참조하지 않고 있음을 나타낸다.

 

LInsert 정의

void LInsert(List * plist, LData data)
{
	if(plist->numOfData > LIST_LEN) 
	{
		puts("저장이 불가능합니다.");
		return;
	}

	plist->arr[plist->numOfData] = data;
	(plist->numOfData)++;
}

numOfData는 리스트의 길이를 의미하기도 하지만, 그 자체로 다음에 저장할 인덱스 값으로도 활용이 가능하다.

예를 들어 numOfData가 2일 경우 리스트의 현재 길이는 2인데, 이는 인덱스가 [0, 1] 일 것이다. 따라서 다음에 새롭게 추가할 값의 인덱스는 2가 되므로 이를 통해 리스트의 다음에 추가할 데이터의 인덱스로도 활용이 가능한 것이다.

이러한 이후로 데이터를 추가한 이후에 numOfData에 +1을 진행한다.

 

if문은 예외처리로, 현재 데이터의 길이가 최대 개수 LIST_LEN에 도달한 경우를 처리한다.

 

LFirst, LNext 정의

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

데이터를 참조하기 위한 두 가지 함수 LFirst와 LNext이다.

여기서 제일 중요한건 현재 참조 위치를 가리키는 멤버 변수 curPosition 이므로 이에 주의하면서 코드를 봐보길 바란다.

이 두가지 함수에서도 서로 다른 내용이 사실 curPosition 에 대한 내용인데, LFirst의 plist->arr[0]; 코드도 사실 plist->arr[curPosition];  으로 바꿔도 문제가 되지 않는다.

 

예외처리에 대해 살펴보자면 먼저 LFirst의 경우는 간단하다.

numOfData 가 0일 경우, 즉 리스트에 아무런 데이터가 없을 경우에 return 한다.

 

LNext의 경우는 먼저 코드에는 (plist->curPositiom >= (plist->numOfData)-1) 로 되어 있는데, 먼저 결론부터 말하자면 현재 참조하는 데이터가 가장 마지막 인덱스일 경우를 뜻한다.

한 단계씩 확인해보면 먼저 LNext 가 호출되기 이전에 참조한 위치는 curPosition 에 저장되어 있다. 이 상황에서는 이 다음에 데이터가 있는지 없는지 확인이 불가능하다. 그에 대한 판단을 numOfData를 통해 확인하는 것이다.

(plist->numOfData)-1 는 전체 데이터의 수 -1, 즉 마지막 인덱스를 의미하는데, 현재 참조하고 있는 값 curPosition 이 이 마지막 인덱스보다 크거나 같다면 자연스럽게 지금 참조하는 데이터가 마지막 데이터라는 것을 나타낸다.

이 이유로 LNext를 호출하면 다음에 참조할 데이터가 없다는 것을 말하고 false 를 return하게 된다.

 

LRemove, LCount 정의

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

LCount 는 상당히 간단한데, numOfData를 반환하여 현재 데이터의 총 개수를 알려준다.

 

개인적으로 이해하기 어려웠던 내용은 LRemove였다.

LRemove를 통해 데이터를 지우는 것은 사실 0이나 null 로 값을 날릴 수 있지만, 핵심은 데이터를 지우고 난 이후이다.

그림을 보면 B - C - D 로 연결이 되어 있는데 여기서 C를 지울 경우 B - D로 연결되기 위해 C가 있던 공간에 대한 처리가 필요하다는 것을 알 수 있다.

따라서 요점은 데이터를 지운 위치 뒤의 데이터들을 앞으로 하나씩 옮겨주어 빈 공간을 다 채우는 것이다.

이 과정이 삭제의 기본 모델이다.

 

삭제의 동작 자체는 프로그래밍을 해봤다면 한번쯤 해봤을 만한 내용이지만 여기서 신경써야 할 점은 삭제할 데이터가 curPosition 멤버와 연관이 있다는 것인데, 이 LRemove에서는 함수가 호출되었을 때 삭제할 데이터가 curPosition 인 것이다.

다시 결론부터 말하자면 데이터를 삭제한 이후 curPosition 을 한칸 당겨줘야 한다.

curPostion 이 C를 가리키고 있고 LRemove로 C를 지웠는데 curPosition 의 위치가 그대로 남아있게 된다면, 데이터가 한칸씩 당겨지게 되므로 curPosition 은 D를 가리키게 된다.

 

이 내용이 설계 의도와 달라지는 것인데 curPosition 인 '마지막으로 참조한 데이터의 위치' 를 가리키기 위해 선언된 변수이지만 D를 가리키게 될 경우 참조하지 않은 데이터를 가리키는 현상이 나타나는 것이다.

따라서 curPosition 이 C일 때 C가 지워졌다면 마지막으로 가리킨 데이터는 삭제된 위치의 이전 데이터, B가 맞으므로

(plist->curPosition)--;

다음의 코드를 통해 앞으로 한칸 옮겨주는 것이 옳다.

 

한가지 더 중요한 부분은 삭제할 데이터로 임시로 저장하는 부분인데,

LData rdata = list->arr[rpos];
...
return rdata;

이 내용이다.

나중에 이 삭제한 값을 함수를 호출한 부분에서 사용하는 등 반환하는 동작이 필요하기 때문에 임시 저장 과정이 필요하다. 이렇게 어떤 데이터를 삭제하는 로직을 작성할 때, 그 삭제한 데이터를 반환하는 것이 원칙인데 다음 항목을 보면서 그 이유를 살펴보자.

 

리스트에 구조체 변수 저장하기

_point 를 Point 로 선언한 구조체가 하나 있고, 각 기능에 맞는 함수들이 선언되어 있다.

함수 내부 정의는 다음과 같이 작성하였다.

코드를 보면 알 수 있겠지만 이 Point 구조체는 점의 좌표를 기록하기 위한 구조체이다.

이를 활용하기 위해 기존의 ArrayList.h 중 일부를 다음과 같이 변경한다.

// 변경
typedef int LData; => typedef Point *LData;

// 추가
#include "Point.h"

 

다시 한번 언급하지만 코드를 수정할 때는 .c 의 정의부 파일의 수정은 극도로 지양해야 한다.

거의 기능 변경, 수정, 디버깅 외의 경우에는 건들 일이 없어야 할 정도로 헤더 파일에서의 최소한의 변경만을 지향하는 코드 작성을 추구해야 함을 알린다.

 

PointListMain.c 예제 코드이다.

int main(void)
{
	List list;
    Point compPos;
    Point *ppos;
    
    ListInit(&list);
    
    /*** 4개의 데이터 저장 ***/
    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 1);
    LInsert(&plist, ppos);
    
    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 2);
    LInsert(&plist, ppos);
    
    ...
    
    
    /*** 저장된 데이터의 출력 ***/
    printf("현재 데이터의 수 : %d \n", LCount(&list));
    
    if(LFirst(&list, &ppos))
    {
    	ShowPointPos(ppos);
        
        while(LNext(&list, &ppos))
        	ShowPointPost(ppos);
    }
    printf("\n");
    
    ...
    
    /*** xpos 가 2인 모든 데이터를 삭제 ***/
    compPos.xpos = 2;
    compPos.ypos = 0;
    
    if(LFirst(&list, *ppos)) {
    	if(PointComp(ppos, &compPos)==1) {
        	ppos = LRemove(&list);
            free(ppos);
        }
        while(LNext(&list, &ppos)) {
        	if(PointComp(ppos, &compPos)==1) {
            	ppos = LRemove(&list);
                free(ppos);
            }
        }
    }
    ...
}

Point 구조체 변수를 동적 할당하여 그 주소값을 list에 저장하고, 활용하는 형태이다.

 

데이터 추가와 조회 과정은 지난 예시와 크게 다르지 않다.

주의깊게 봐야 할 점은 데이터의 삭제 과정 LRemove 와 free이다.

 

먼저 코드 상에서 우리는 xpos 가 2인 모든 데이터를 찾아서 삭제하기를 원했다.

xpos 에만 집중하면 되므로 ypos 에는 큰 의미부여를 하지 않고 0으로 초기화해주었고, PointComp 를 통해 xpos 가 2인 주소값 compPos 를 할당해 데이터가 찾아지면(반환값이 1) LRemove를 실행하도록 하였다.

 

여기서 중요한 것은 데이터를 지웠다고 해도 malloc 을 통해 동적 할당 된 메모리까지 소멸하지는 않는다는 것이다.

사용된 흔적이 있는 메모리는 데이터가 삭제돼 빈 공간으로 남아있을 것인데, 메모리의 효율적 관리를 위해서는 이 메모리 또한 지워주는 것이 옳다.

다만 그렇다고 이 메모리까지 지우는 것을 LRemove 를 실행하는 list 자료구조의 책임으로 둘 것인가? 는 아니라는 것이다. list 가 모든 것을 완벽하게 해내기에는 무리가 있다.

 

그 이유로, list 자료구조는 point 의 '주소값만' 저장하고 있다. 그 주소값이 우리가 요구하는 사항(xpos 가 2인 경우)에 해당하는지까지 판별해서 메모리를 해제하는 것은 구조적으로도 좋지 않을 뿐더러 너무 많은 부담감을 list 에게 넘기는 것이다.

 

따라서 단순 데이터 삭제의 LRemove 와 메모리 해제의 free 는 별개의 동작으로 이루어졀야 한다.

해서 코드 상에서 LRemove와 free 함수를 나누어 실행하고 있는데, 당연하게도 free 함수를 실행하기 위해서는 어떤 값을 해제할 지를 알아야 한다.

 

이 동작을 LRemove의 반환을 통해 ppos 로 연결하는 것이다.

위에서 LRemove 내부 정의에서 return 이 필요했던 이유가 여기에 있다.

 

이 반환을 하지 않고 단순히 삭제 동작만 수행한다면, 데이터가 삭제된 메모리는 그대로 남아있고 결과적으로는 메모리 누수까지 연결될 수 있다.