이번 Ch.03는 좀 다룰 내용들이 많다. 복습하면서 체화시키도록 하자.
Ch.03 Linked List 1
03-1
우선 이 교재에서 알려주는 첫 번째 자료구조를 학습하기 전에, 알아둬야할 내용을 미리 공부하자.
추상자료형(ADT)
우선, 추상자료형을 간단히 한 문장으로 정의하자면
"구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열하는 것"
을 말한다.
예로 들면, 나한테 지갑이 하나 있다고 치자. 그 지갑에 동전을 넣는 과정을 설명하면, 보통 "지갑 열고 동전 넣기" 라고 생각할 것이다. 그런데 이거를 정~말 구체적으로 어떤 어떤 과정을 거쳐서 완성되는지를 언급한다면
"지갑을 열고, 동전을 넣을 공간을 찾아서, 그 공간을 열고, 동전을 넣고, 그 뒤 동전을 넣은 공간을 닫은 다음, 지갑을 닫는다"
이렇게 긴 과정을 거칠것이다. ADT가 이런걸 말하는거다.
그러면, 이 과정의 이름이 왜 "자료형"이라고 붙을까? 내가 C언어를 공부할 때 자료형이라고 말하면 int, char, short와 같은 내용들이 자료형이였는데?
.. 예를 들어보자.
typedef struct_wallet {
int coin100num;
int bill5000num;
} Wallet;이렇게 정의 해주면, 지갑을 의미하는 Wallet 자료형을 정의해주게 된다.
그러나, 컴퓨터 공학적(?)으로 봤을 때 이 구조체를 정의한 것 만으로는 "Wallet"이라는 자료형의 정의가 완성되는 것은 아니라고 한다. 이 "Wallet"을 기반으로 하는 연산의 종류를 결정하는 것도, 자료형 정의의 일부로 보아야 한단다. 뭐 예로들면
int TakeOutMoney(Wallet *pw, int coinnum, int billnum);
void PutMoney(Wallet *pw, int coinnum, int billnum);이렇게 Wallet 구조체에서 돈을 꺼내고 / 넣는 연산을 함수로 정의했는데, 이 두 연산이 만약 "Wallet과 관련이 있는 연산의 모든 것"이라고 하면, Wallet 구조체 + TakeOutMoney 함수 + PutMoney 함수 가 다 합쳐져서 자료형의 정의가 되는 것이다.
아. 그런데 ADT를 set할때, 구조체 wallet의 정의는 굳이 필요하지 않다. 내가 만약 TakeOutMoney 함수와 PutMoney 함수를 쓰는데, 구조체 Wallet의 멤버가 어떻게 구성되어 있는지는 알 필요가 없지 않은가?
03-2
List라는, 자료구조를 학습하게 된다.
이 list는 "순차 리스트"와, "연결 리스트" 두개로 나뉜다. 이렇게 구분된건 리스트의 "구현방법" 차이에서 비롯된 거라, 이 둘 ADT가 똑같다고 문제될건 없다. 특성적 차이 때문에 ADT 차이를 두기도 한다고 한다.
방금 위에서 얘기한 내용중에 또 알아둬야 할 학습 내용이 있는데, "ADT가 똑같다고 문제될건 없다", "ADT 차이를 두기도 한다". ADT가 같을수도 다를수도 있다는 얘기인가??
그렇다. ADT는 필요에 따라서 차이가 난다고 한다. 기본 특성을 지키는 선에서.
그러면 본격적으로 list에 대해 공부해보자.
이 List Data Structure는 "데이터를 나란히 저장하고, 중복된 데이터의 저장을 막지 않는다." 이 중복된 데이터를 저장을 하는것을 막지 않는다는게, 리스트 ADT를 정의하는데 있어, 고려해야할 유일한 요소다.
"데이터를 나란히 저장해야 하니까 이렇게 저렇게 코드를 짜야지!" 라는 사고 방식을 가지면 안되고, "나란히 저장된다"는 특성을 기반으로, 제공해야 할 기능들을 우선적으로 정의해야한다.
// LData는 typedef int LData; 임.
// 리스트에 저장할 데이터의 자료형에 제한을 두지 않기 위해 선언함.
void ListInit (List *plist);
// 리스트 초기화. 변수를 처음 정의하고 초기화 하는 것과 같은 맥락
void LInsert (List *plist, LData data);
// list에 data 저장
int LFirst (List *plist, LData *pdata);
// 첫 번째 데이터 참조
int LNext (List *plist, LData *pdata);
// 두 번째 ~ 마지막 데이터들 참조
LData LRemove (List *plist);
// 데이터 삭제. 삭제된 데이터는 반환된다.
int LCount (List *plist);
// 리스트에 저장된 데이터 개수를 반환한다.
이렇게, 리스트 자료구조의 ADT들을 정의했다.
그러면 이 ADT를 기반으로 main 함수를 만들어보자.
#include <stdio.h>
#include "ArrayList.h"
int main() {
List list;
int data;
ListInit(&list); // 초기화
LInsert(&list, 11);
LInsert(&list, 22);
LInsert(&list, 33);
LInsert(&list, 33); // 데이터 저장
if (LFirst(&list,&data)) {
printf("%d ", data); // 첫번째 데이터 출력
while (LNext(&list, &data)) {
printf("%d ", data); // 두 번째 이후 데이터들 출력
}
}
printf("\n\n");
if (LFirst(&list, &data)) {
if(data == 33) LRemove(&list);
while (LNext(&list, &data)) {
if (data == 33) LRemove (&list);
} //data가 33일 경우, 삭제.
}
}우선 맨 처음 List 자료형을 사용하여 list를 선언했고, 그 선언한 list를 ListInit 을 사용해 초기화 해주었다.
그 다음 LInsert 에서 첫 번째 인자로 데이터를 저장할 주소값을 보냈고, 두 번째 인자로는 저장할 데이터를 보내며 list에 데이터를 저장한다.
이후 저장된 데이터를 확인하기 위해 출력을 하고있다.
근데 여기서 첫 번째 의문, 굳이 왜 먼저 "LFirst"를 호출 하고 그 이후로 "LNext"를 호출하는 걸까?
이 LNext가 가능한 이유는, list 내에서 "데이터의 참조위치"를 기록하기 때문이다. 그래서 참조를 새롭게 시작 하려면 참조 위치도 초기화 시켜서 처음부터 차근 차근 읽어나가야 한다. 그래서 LFirst에서 초기화시켜 처음으로 돌아간 뒤, 그 뒤로 커서를 넘겨주는(?) LNext를 반복 사용하여 모든 데이터를 참조하게 된다.
그러면, 이 main 함수가 참조하는 ArrayList.h 도 알아보겠다.
#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__
#define TRUE 1
#define FALSE 0
#define LIST_LEN 100
typedef int LData;
typedef struct __ArrayList
{
LData arr[LIST_LEN];
int numOfData;
int curPosition;
} 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위와 같다. ifndef와 endif는 어제 복습한 내용 그대로 인지하면 된다.
typedef int LData; 는 리스트에 여러 종류의 데이터를 저장할 수 있게 하기 위한 것이다. 만약 저장할 자료형이 int가 아니라 char라면, 이 명령문에서 int만 char로 바꿔주면, 프로그램 전체에 영향을 미치게 된다.
typedef ArrayList List; 는, List에 다른 이름을 부여하기만 해도 사용하는 리스트의 종류를 바꿀수 있어 편해진다.
typedef LinkedList List; 이렇게.
그러면 이제 배열을 기반으로, 함수원형만 설정된 이 List 함수들을 구현해 보겠다.
우선 ListInit. 얜 별 거 없다. 그냥 초기화 해주면 된다.
ListInit (List *plist) {
plist->numOfData = 0;
plist->curPosition = -1;
}numOfData는, 초기화시키면 저장된 데이터는 없을거니 0개다.
curPosition은 참조해야할 현재 배열의 위치인데, 지금은 참조할 데이터가 없으니까, -1로 초기화되어있다.
LInsert. 얘는 데이터를 삽입해주면 되는데, 주의해야할 부분이 하나 있다.
LInsert (List *plist, LData data) {
if (plist->numOfData >= LIST_LEN) {
printf("ERROR, Can't save data. \n");
return;
}
plist->arr[numOfData] = data;
(plist->numOfData)++;
}만약 Data의 개수가 LIST의 길이를 넘어가 버리면 저장을 못하게 막아버리고, 그게 아니라면 data를 list에 저장해준다. (plist->numOfData)++;는, 데이터를 저장하면 데이터가 하나 늘어나니까. 하나 더해준다.
그 다음은 LFirst와 LNext.
int LFirst(List *plist, List *pdata) {
if (plist->numOfData == 0) return FALSE;
(plist->curPosition) = 0;
*pdata = plist->arr[0];
return TRUE;
}
int LNext(List *plist, List *pdata) {
if (plist->curPosition >= (plist->numOfData)-1) return FALSE;
(plist->curPosition)++;
*pdata = plist->arr[plist->curPosition];
return TRUE;
}LFirst의 curPosition = 0은, 첫 데이터가 저장 되었으니 참조하는 위치도 바꿔준다.
그리고 LNext의 if (plist->curPosition >= (plist->numOfData)-1) return FALSE;
는, 만약 더 이상 참조할 데이터가 없을 때를 뜻한다.
마지막으로 LRemove.
여기선 주의해야 할 게, 데이터를 삭제하기만 하면 끝이 아니다. 중간의 데이터가 삭제 되면, 뒤에 데이터들을 한 칸씩 앞으로 이동시키며, 그 공간을 메워야한다.
이렇게 된다는 거다.
LData LRemove ( List *plist ) {
int rpos = plist->curPosition; // 삭제할 데이터 위치 값
int num = plist->numOfData;
int i;
LData rdata = plist->arr[pos]; // 삭제할 데이터를 기억
for (i=rpos; rpos<num ; i++) {
plist->arr[i] = plist->arr[i+1];
} //위에서 설명한 그림을 코드로 표현
(plist->numOfData)--;
(plist->curPosition)--;
//참조 위치를 하나 되돌린다.
//즉, 삭제된 데이터를 제외한 가장 최근에 참조가 이뤄진 데이터를 가리킨다.
return rdata; //삭제된 값을 반환
}이런식으로 배열을 기반으로 한 리스트들을 짜보았는데, 배열 기반 리스트의 장단점은
장점 : 데이터 참조가 쉽다. INDEX값을 기준으로, 어디든 한번에 참조가 가능하다.
단점 : 배열의 길이가 초기에 결정되어야 한다. / 삭제 과정에서 데이터 이동이 매우 많이 일어난다.
정도가 되겠다. 이러한 장 단점은 "연결 기반 리스트"와 비교했을 때, 이런 장 단점이 있다는 것이니, 다음 챕터를 공부하고 명확히 이해하도록 하자.
여기까지.
p.s. 내일은 부산으로 잠시 놀다 올거라 공부를 할 수 있을지 모르겠다. 복습을 할 시간이 없다면 잠시 백준이라도 풀겠음.
