1. 배열을 이용한 리스트의 구현
이미 자료구조를 한 차레 공부한 사람도 있을 것이다.
그렇다면 그분들에게 다음과 같이 질문하고 싶다.
"리스트는 연결 리스트를 의미하나요?"위와 같은 질문을 하면 보통 Yes라는 답을 듣는다.
하지만 이는 정답이 아니다.
리스트라는 자료구조는 구현방법에 따라서 다음과 같이 크게 두 가지로 나뉘기 때문이다.
- 순차 리스트: 배열을 기반으로 구현된 리스트
- 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트하지만 이는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에 이 둘의 ADT가 동일하다고 해서 문제될 것은 없다.
물론 각각의 특성적 차이 때문에 ADT에 차이를 두기도 한다.
"ADT가 같을 수도 있고 다를 수도 있다?"
"그럼 각종 자료구조들의 ADT는 표준이 아닌 거에요?"그렇다! 표준이 아니다.
때문에 정의하는 사람이나 회사에 따라서, 다시 말해서 필요에 따라서 ADT에도 차이가 난다.
물론 필요에 따라서 확장도 가능하다.
하지만 그렇다고 해서 해당 자료구조의 기본 특성을 무시하는 형태로 ADT가 정의되는 것은 아니다.
자! 그럼 리스트의 ADT 정의를 위해서 리스트 자료구조의 가장 기본적이고도 중요한 특성을 소개하겠다.
"리스트 자료구조는 데이터를 나란히 저장합니다."
"그리고 중복된 데이터의 저장을 막지 않습니다."자료구조 중에서는 중복된 데이터의 저장을 허용하지 않는 경우도 있다.
하지만 리스트는 이를 허용한다.
이것이 리스트 ADT를 정의하는데 있어서 고려해야 할 유일한 요소이다.
리스트의 특성을 소개하였으니 이를 가지고 ADT를 정의해 보자.
다시 말해서 리스트 자료구조가 제공해야 할 기능들을 나열해 보자는 것이다.
"일단 데이터를 나란히 저장해야 하니까..."이는 잘못된 접근방식이다!
데이터를 어떻게 나란히 저장할지를 고민하는 게 아니라, 나란히 저장된다는 특성을 기반으로 제공해야 할 기능들을 정의해야 하는 것이다.
2. 리스트 자료구조의 ADT
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);
- 리스트에 저장되어 있는 데이터의 수를 반환한다.위에서 보이듯이, 이후에 구현할 자료구조들과의 이름충돌을 막기 위해서 리스트를 의미하는 L을 접두사로 하여 함수의 이름을 정의하였다.
그리고 LData는 리스트에 저장할 데이터의 자료형에 제한을 두지 않기 위한 typedef 선언의 결과이니, 이에 대해서는 잠시 후 헤더파일에서 확인을 하자.
사실 위의 정보만 가지고는 리스트의 활용방법을 정확히 이해하기 힘들다.
이를 위해서는 헤더파일과 이의 함수들을 호출하는 main 함수를 보아야 한다.
그러나 위의 정보만 가지고도 리스트 자료구조가 제공하는 기능을 어느 정도 예측할 수 있어야 한다.
리스트의 ADT를 정의하였으니, 이를 기반으로 main 함수를 만들 차례이다.
아래에서 제시하는 main 함수를 기반으로 리스트 ADT에서 소개하는 함수들의 기능을 완전히 이해하기로 하자.
어떤 라이브러리에 포함되어 있는 리스트의 사용방법을 파악하는 상황이라고 생각하기 바란다.
그 어떤 라이브러리가 C의 표준함수라고 가정해도 괜찮다.
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)); // 5
if(LFirst(&list, &data)) // 첫 번째 데이터 조회
{
printf("%d ", data); // 11
while(LNext(&list, &data)) // 두 번째 이후의 데이터 조회
printf("%d ", data); // 11 22 22 33
}
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)); // 3
if(LFirst(&list, &data))
{
printf("%d ", data); // 11
while(LNext(&list, &data))
printf("%d ", data); // 11 22
}
printf("\n\n");
return 0;
}위의 실행결과를 직접 확인하기 위해서는 ArrayList.h와 ArraList.c를 컴파일 해야 하니, 아직 소개하지 않은 파일들은 밑에서 찾아서 코드를 복사한 뒤 실행결과를 확인하기 바란다.
우선 위의 main 함수에서 제일 먼저 등장하는 리스트의 생성 및 초기화 관련 다음 두 문장을 보자.
List list; // 리스트의 생성
...
ListInit(&list); // 리스트의 초기화
...위에 보면 List를 기반으로 변수 list를 선언하고 있는데, 앞으로 이것을 리스트라 지칭하겠다.
그리고 모든 자료구조는 내부적으로 다양한 정보를 담게 된다.
그저 데이터만 담는 게 아니라 그 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담기기 마련이다.
따라서 이와 관련된 변수들의 초기화가 선행되어야 하며 이를 담당하는 함수가 ListInit이다.
이어서 핵심이라고 볼 수 있는 데이터의 저장방법을 살펴보자.
저장방법은 매우 간단하고 직관적이다.
LInsert(&list, 11); // 리스트에 11저장
LInsert(&list, 11); // 리스트에 11저장
LInsert(&list, 22); // 리스트에 22저장
LInsert(&list, 22); // 리스트에 22저장
LInsert(&list, 33); // 리스트에 33저장LInsert 함수를 호출하면서 리스트의 주소 값을 첫 번째 인자로, 그리고 리스트에 담을 데이터를 두 번째 인자로 전달하고 있다.
이번에는 특히 주의 깊게 보고 또 이해해야 하는 '데이터의 참조방식'을 살펴보겠다.
참고로 본래 데이터의 저장보다 참조가 더 복잡하기 마련이다.
아래의 코드에서는 저장된 순서대로 데이터를 참조하여 출력을 진행하되, 마지막 데이터까지 참조하여 출력을 진행하고 있다.
if(LFirst(&list, &data)) // 첫 번째 데이터를 변수 data에 저장
{
printf("%d ", data);
while(LNext(&list, &data)) // 두 번째 이후의 데이터 조회
printf("%d ", data);
}앞서 리스트 ADT에서는 다음과 같이 언급을 하였다.
"순서대로 참조하려면 먼저 LFirst를 호출해서 첫 번째 데이터를 얻으세요."
"그리고 두 번째 이후의 데이터는 LNext를 호출해서 얻으시면 됩니다.""그리고 Lfirst 함수와 LNext 함수는 더 이상 참조할 데이터가 없으면 FASLE를 반환한다."LNext 함수의 호출을 통해서 다음 번 데이터를 얻는다는 사실은 어렵지 않게 이해할 수 있다.
그런데 굳이 LFirst 함수의 호출을 요구하는 이유는 무엇일까?
LFirst 함수를 호출하도록 ADT를 디자인한 이유는 무엇일까?
이에 대한 해답은 'LNext 함수를 호출할 때마다 다음에 저장된 데이터를 얻을 수 있다!'라는 사실에서 찾을 수 있다.
이것이 가능한 이유는 리스트 내에서 '데이터의 참조위치'를 기록하기 때문이다.
따라서 처음부터 참조를 새롭게 시작하기 위해서는 바로 이 정보를 초기화해야 한다.
그리고 이를 목적으로 LFirst 함수의 호출을 요구하는 것이다.
때문에 리스트에 저장된 모든 데이터를 참조하려면 함수의 호출순서를 다음과 같이 구성해야 한다.
LFirst -> LNext -> LNext -> LNext -> ...이제 마지막으로 삭제 관련 코드를 설명하겠다.
이는 바로 위에서 설명한 탐색 관련 코드와 관련이 깊다.
삭제를 위해서는 탐색이 선행되어야 하기 때문이다.
if(LFirst(&list, &data))
{
if(data==22)
LRemove(&list);
while(LNext(&list, &data))
{
if(data==22)
LRemove(&list);
}
}위의 코드에서는 리스트에 저장된 숫자 22를 찾아서 이를 모두 삭제하고 있다.
그럼 LRemove 함수가 호출되는 시점을 관찰해 보자!
- 함수 LFirst가 호출된 이후
- 함수 LNext가 호출된 이후즉 LRemove 함수가 호출되면, 바로 직전에 LFirst 또는 LNext 함수의 호출을 통해서 참조된 데이터가 삭제된다.
혹시 이와 관련해서 다음과 같이 묻고 싶은가?
"그게 어떻게 가능한 건가요?"다시 한번 말하지만, 우리는 지금 리스트 관련 함수들의 사용방법을 이야기하고 있다.
내부 구현에 대한 이야기는 잠시 뒤로 미루자.
이제 리스트 자체의 구현에 대해서 이야기할 차례이다.
그런데 이에 앞서 짚고 넘어가고 싶은 것이 하나 있다.
"앞서 보인 main 함수에 리스트의 구현과 관련된 어떠한 코드도 등장하지 않았습니다."말 그대로 우리는 리스트 자료구조를 그냥 가져다 썼다!
그리고 이는 우리가 리스트의 ADT를 나름 잘 정의했다는 뜻도 된다.
이렇듯 어떠한 자료구조이건 간에 '자료구조의 구현'과 '구현된 자료구조의 활용'은 완전히 구분되도록 ADT를 정의해야 함을 기억하자.
이제 리스트를 구현해보자.
앞서 한차례 정리했듯이, 리스트의 구현방법은 크게 두 가지로 나뉘는데, 먼저 그 중 하나인 배열을 이용하는 방법을 보이고자 한다.
그리고 그 첫 번째 순서로 배열 기반의 리스트 구현을 위해 정의된 헤더파일을 소개하겠다.
ArrayList.h
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1 // '참'을 표현하기 위한 매크로 정의
#define FALSE 0 // '거짓'을 표현하기 위한 매크로 정의
/*** ArrayList의 정의 ****/
#define LIST_LEN 100
typedef int LData; // LData에 대한 typedef 선언
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에는 데이터의 저장공간이 배열로 선언되었고 저장된 데이터의 수를 기록하기 위한 멤버도 존재한다.
그리고 참조의 위치를 기록하기 위한, 다시 말해서 LFirst와 LNext, 그리고 LRemove 함수를 위한 멤버도 존재한다.
그리고 리스트에 다양한 종류의 데이터를 저장할 수 있게 하기 위한 typedef 선언도 다음과 같이 존재한다.
typedef int LData; // 리스트에 int형 데이터의 저장을 위한 선언우리는 리스트의 구현을 완료한 다음에, 위의 typedef 선언을 변경하여 구조체 정보를 저장하는 리스트도, 구조체 변수의 주소 값을 저장하는 리스트도 생성해 볼 것이다.
그럼 이어서 다음 typedef 선언에 주목하자.
typedef ArrayList List;이렇듯 ArrayList에 List라는 이름을 별도로 부여한 것이 당장에는 큰 의미가 없어 보인다.
하지만 ArrayList라는 이름에도 typedef 선언을 해 놓으면, 다음과 같이 List에 다른 이름을 부여하는 것만으로도 사용하는 리스트의 종류를 바꿀 수 있다.
그래서 앞서 보인 main 함수에서도 ArrayList가 아닌 List라는 이름을 이용하여 예제를 작성한 것이다.
때문에 main 함수를 변경하지 않고도 main 함수 내에서 사용하는 리스트를 다른 것으로 대체할 수 있는데, 이와 관련된 예는 다음 챕터에서 보이기로 하겠다.
자! 이제 남은 것은 위의 헤더파일에 선언된 함수들을 정의하는 것이다.
그 첫 번재 순서로 다음 두 함수를 완성해 보자.
void ListInit(List * plist); // 초기화
void LInsert(List * plist, LData data); // 데이터 저장그럼 먼저, 초기화를 담당하는 ListInit부터 채워보겠다.
이를 채우기 위해서는 앞서 정의한 구조체 ArrayList를 보면서 초기화할 대상이 무엇인지 파악해야 한다.
void ListInit(List * plist)
{
(plist->numOfData) = 0; // 리스트에 저장된 데이터의 수는 0!
(plist->curPosition) = -1; // 현재 아무 위치도 가리키지 않음!
}짐작했겠지만 ArrayList의 멤버 curPosition에는 배열의 인덱스 값이 저장된다.
그리고 이 변수에 저장된 값을 통해서 LFirst 함수와 LNext 함수가 참조해야 할 배열의 위치를 알게 할 생각이다.
그래서 curPosition은 0이 아닌 -1로 초기화한 것이며, 여기에는 아직 데이터의 참조가 진행되지 않았다는 의미가 담겨있다.
그럼 이어서 LInsert 함수를 소개하겠다.
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); // 첫 데이터 참조
int LNext(List * plist, LData * pdata); // 두 번째 이후 데이터 참조먼저 LFirst 함수부터 채워보자.
int LFirst(List * plist, LData * pdata)
{
if(plist->numOfData==0)
return FALSE;
(plist->curPosition)=0;
*pdata = plist->arr[0];
return TRUE;
}이어서 LNext 함수의 정의를 보이겠다.
그리고 나서 이 둘의 차이점을 이야기하겠다.
int LNext(List * plist, LData * pdata)
{
if(plist->curPosition >= (plist>numOfData)-1) // 더 이상 참조할 데이터가 없다면
return FALSE;
(plist->curPosition)++;
*pdata = plist->arr[plist->curPosition]l
return TRUE;
}위의 두 함수의 실질적인 차이점은 다음 한 문장에 있다.
- LFirst 함수의 중간에 삽입된 문장: (plist->curPosition) = 0;
- LNext 함수의 중간에 삽입된 문장: (plist->curPosition)++;이렇듯 LFirst 함수는 curPosition에 저장된 값을 0으로 재설정함으로써 데이터의 참조가 앞에서부터 다시 진행되도록 하는 역할을 한다.
반면 LNext 함수는 이 값을 증가시켜서 순서대로 데이터를 참조할 수 있도록 한다.
그래서 이 두함수는 모두 필요하다.
이제 마지막으로, 저장된 데이터의 삭제를 담당하는 다음 함수를 완성해보자.
LDats LRemove(List * plist); // 최근 조회가 이뤄진 데이터를 삭제한다.이 함수의 정의를 위해서, 이 함수가 호출된 사례를 다시 한 번 관찰하기로 하자.
if(LFirst(&list, &data))
{
if(data=22)
LRemove(&list); // 앞서 LFirst 함수가 참조한 데이터 삭제!
while(LNext(&list, &data))
{
if(data==22)
LRemove(&list); // 앞서 LNext 함수가 참조한 데티어 삭제!
}
}이렇듯 LFirst 함수나 LNext 함수의 호출을 통해서 바로 직전에 참조가 이뤄진 데이터를 삭제하는 것이 LRemove 함수이니 다음과 같은 형태로 삭제가 진행되어야 한다.
"LRemove 함수가 호출되면 리스트의 멤버 curPosition을 확인해서, 조회가 이뤄진 데이터의 위치를 확인한 다음 그 데이터를 삭제한다.이에 한가지 더해서 다음 사실을 기억하고 이를 반영해야 한다.
"앞에서부터 데이터를 채우는 것이 원칙이니 중간에 데이터가 삭제되면, 뒤에 저장된 데이터들을 한 칸씩 앞으로 이동시켜서 그 빈 공간을 메워야 한다."이는 다음 그림에서 보이는 바와 같은 방식으로 삭제가 진행되어야 함을 뜻한다.
다음 그림에서는 문자 C의 삭제 과정 및 그 결과를 보이고 있다.
이제 위에서 언급한 두 가지 특성을 반영한 LRemove 함수를 소개하겠다.
주목해서 볼 것은 삭제할 데이터의 위치를 참조하는 방식과 삭제를 위한 데이터의 이동과정이다.
LData LRemove(List * plist)
{
int rpos = plist->curPosition; // 삭제할 데이터의 인덱스 값
int num = plist->numOfData;
int i;
LData rdata = plist->arr[rpos] // 삭제할 데이터를 임시로 저장
// 삭제를 위한 데이터의 이동을 진행하는 반복문
for(i=rops; i<num-1; i++) // arr[i+1]에서 i+1에 있는 요소에 접근하기 때문데 num-1
plist->arr[i] = plist->arr[i+1];
(plist->numOfData)--;
(plist->curPosition)--;
return rdata;
}위의 함수에서 다음 문장이 삽입된 이유를 확인하고 넘어가자.
(plist->curPorsition)--; // 참조위치를 하나 앞으로(배열 기준 왼쪽으로) 옮긴다.이렇듯 참조위치를 옮기는 이유를 알겠는가?
curPosition은 최근에 참조가 이뤄진 데이터의 인덱스 정보를 담고 있어야 한다.
그런데 삭제로 인해 비는 공간을 메우려 데이터를 한 칸씩 앞으로 이동시키면, 다음 표에서 보이듯이 curPosition은 아직 참조가 이뤄지지 않은, 뒤에서 한 칸 앞으로 이동한 데이터를 가리키게 된다.
따라서 다음 표에서 보이듯이 curPosition을 한 칸 앞(왼쪽)으로 이동시켜야 한다.
이제 비로소 curPosition은 삭제된 C를 제외한, 가장 최근에 참조가 이뤄진 B를 가리키게 되었다.
따라서 이후에 LNext 함수가 호출되면, 참조가 이뤄지지 않은 D를 참조할 수 있게 되었다.
이제 별도의 설명이 필요 없는 LCount 함수를 포함해서 지금까지 정의한 모든 함수를 하나의 소스파일로 묶겠다.
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;
}이로써 ArrayList.h와 ArrayList.c를 완성하였다.
이렇듯 우리가 만든 리스트를 사용하기 위해서는 헤더파일 ArrayList.h를 포함하고, 이 헤더파일에 선언된 함수의 기능을 숙지하면 된다.
실제 리스트가 어떻게 구현되어 있는지는 확인할 필요가 없다.
