CH4. 연결 리스트 (Linked list) 2-2

4-2 단순 연결 리스트의 ADT와 구현

• ADT는 배열기반/연결기반(동적할당)에 상관없이 동이일하게 작동해야 함
  • 배열 기반 연결 리스트는 나란히 구성되어 Index 값을 이용해 특정 위치 Data에 쉽게 접근 가능
• 이를 위해 Chapter3의 배열 기반 ADT를 그대로 구현
  • 배열/연결 기반 ADT가 원칙적으로 서로 다를 순 없지만, 필요 기능이나 효율 측면에서 유연하게 달라질 수 있음
• 단순 연결 리스트는 노드들이 한쪽으로 단순하게 연결됨을 의미
  • 강의에서 단순 연결리스트는 연결리스트라고 통칭

정렬 기능 추가된 연결 리스트의 ADT

• Chapter 3의 ADT와 기능적으로 동일하지만 구현방법이 다름
• 또한 배열 기반 연결 리스트의 특징을 따르게 하고자 정렬 함수가 추가됨

• 정렬 기능 함수의 void 함수 포이터는 후술

새 노드의 추가 위치에 따른 장점과 단점

• 각각의 장점과 단점이 존재하지만, 새 노드를 연결 리스트의 머리에 추가하게 하고, 추가 과정에서 정렬 알고리즘을 적용하여 올바른 위치에 정렬하도록 하는것이 좋음
  • 포인터 변수의 감소는 코드의 가독성이 좋아짐

• tail 포인터 변수의 관리를 생략하기 위해 머리 부분에 추가하는것을 원칙으로 함
  • 정렬을 이용하여 머리, 꼬리 뿐만이 아니라 중간에도 올바른 위치에 새로운 노드를 삽입 할 수 있음

SetSortRule 함수 선언에 대한 이해

• void SetSortRule(List *plist, int (*comp)(LData d1, LData d2));
  • 의미: *comp가 저장할 수 있는 함수의 주솟값의 함수는 반환형이 int형이여야 하고, 매개변수 선언이 (LData d1, LData d2)와 일치해야 함
  • Ldata = int이므로 바꿔서 보면 이해하기 수월
    • void SetSortRule(List *plist, int (*comp)(int d1, int d2));와 동일

• WhoIsPrecede함수는 위 조건을 만족시키는 함수 중 하나의 예시
• WhoIsPrecede는 입력된 두 수 d1과 d2를 비교하여 정렬해주는 알고리즘
  • d1 < d2: 오름차순 조건
  • d1 > d2: 내림차순 조건
• 정렬의 기준 -> d1이 d2보다 Head에 가까웠다면(수가 작다면) 0, 아니면 1 반환
  • 배열 기반의 연결 리스트는 이를 기반으로 구현되므로 오름차순 정렬조건을 사용
• 만약 다른 정렬 기준으로 연결 리스트를 정렬하고 싶다면 입력, 반환 조건을 만족하는 다른 함수를 구현하면 됨
• 정렬 함수를 이용해 새 node가 적절한 위치에 연결되도록 할 수 있음
  • 정해진 규칙(내림차순/오름차순 등)에 의해 정의된 기준에 근거하여 node가 연결 됨

CH4. 연결 리스트 (Linked list) 2-1

• 제목은2이지만, 실제로는 첫 번째로 다루는 연결 리스트의 이야기가 됨

4-1 연결 리스트의 개념적인 이해

• 연결 리스트 공부를 할 때 그림 그려가며 이해하는것이 중요!
• 이해에 선행조건? -> 동적할당에 대한 이해가 되어야 함
  • malloc, free 함수가 호출되는 이유를 알고 있어야 함
• 배열의 가장 큰 장점? -> 데이터의 순차 접근이 가능한 자료구조형태임
  • 선언만 하면 index 값을 이용한 순차 접근이 가능해짐
• 배열의 단점 -> 기본적으로 크기(길이)가 결정되어야 함
  • 필요할 때마다 만든다 = 동적할당
• 배열은 순차접근이 가능하나, malloc으로 동적할당만 해놓으면 순차접근이 불가하고 관리가 안됨!
  • 연결 리스트는 방향성을 두고 malloc으로 동적할당 된 리스트를 연결하는 작업!
• 연결리스트를 이용해 malloc으로 동적할당 된 메모리를 연결해 리스트로 관리가 가능
• 새로운 리스트가 메모리에 동적할당 되더라도, 이를 머리나 꼬리 부분에 새로 붙여서 늘릴 수 있게 하는것이 연결리스트
• 경우에는 Head나 Tail에 대한 정보만 갖고 있을 수 있음
  • 필요에 따라 모두 갖고 있을 수도, Head만 갖고 있을 수 있음

Linked가 무엇을 연결하겠다는 뜻인가?

• 연결 방법? -> node에 대한 구조체를 정의해야 함
  • 노드 자체가 구조체 변수가 되어야 함
  • 노드가 해야 할 일
    • 1. 노드에 데이터를 담을 수 있어야 함
    • 1. 연결이 가능해야 함
  • struct _node * next;에서 *next 는 구조체 _node 를 가리키는 구조체 포인터 변수

typedef struct _node
{
	int data; // 1번 역할
	struct _node * next; // 2번 역할
} Node;

• main 함수에 node에 해당하는 변수 선언
  • Node n1, n2;
  • n1과 n2는 각각 새로 생성된 노드를 의미
    • n1.data는 데이터를, n1.next는 누군가를 가리키기 위한 변수공간 (n2도 동일)
  • n1.next = &n2; 로 n2의 주솟값을 n1.next에 저장(연결)
    • __이를 이용해 n1의 포인터가 n2를 가리키게 됨
  • *(n1.next)로 n2를 가리킬 수 있음(순차적 접근)
• 이를 이용해
  • 1. 연결을 어떻게 하는지
  • 1. 순차적 접근에 대한 것을 배울 수 있음
• “LinkedRead.c”의 분석: 초기화
  • head: 연결 리스트의 머리 부분을 가리키기 위한 포인터 변수
  • tail: 연결 리스트의 꼬리 부분을 가리키기 위한 포인터 변수
  • cur: 순차적 접근에 사용되는 포인터 변수(순차적 조회 시에만 필요)

// NULL 포인터 초기화
Node * head = NULL; // 첫 번째 노드를 가리킴(필수요소)
Node * tail = NULL; // 내가 어디까지 갔는지(순차접근)에 대한 정보를 담음
Node * cur = NULL; // 마지막 노드를 가리키지만 없을 수 있음(필수요소가 아님)

Node * newNode = NULL;
int readData;

• “LinkedRead.c”의 분석: 삽입

/**** 데이터를 입력 받는 과정 ****/
while(1)
{
	printf("자연수 입력: ");
	scanf("%d", &readData); // 데이터를 입력하기위한 값을 입력받음
	if(readData < 1)  // 1보다 작은 경우 더 이상 노드를 추가하지 않고 빠져나감
		break;

	/*** 노드의 추가과정(연결과정) ***/
	newNode = (Node*)malloc(sizeof(Node));
	newNode->data = readData;
	newNode->next = NULL;

	if(head == NULL)
		head = newNode;
	else
		tail->next = newNode; // tail이 가리키는 노드 멤버의 next
	tail = newNode;
}

• “LinkedRead.c”의 분석: 데이터 조회

if(head == NULL) 
{
  printf("저장된 자연수가 존재하지 않습니다. \n");
}
else 
{
  cur = head; 
  printf("%d  ", cur->data);   // 첫 번째 데이터 출력

  while(cur->next != NULL)    // 두 번째 이후의 데이터 출력
  {
    cur = cur->next;
    printf("%d  ", cur->data);
  }
}

• “LinkedRead.c”의 분석: 데이터 삭제

if(head == NULL) 
{
  return 0;    // 해제할 노드가 존재하지 않는다.
}
else 
{
  Node * delNode = head;
  Node * delNextNode = head->next;

  printf("%d을(를) 삭제합니다. \n", head->data);
  free(delNode);    // 첫 번째 노드의 삭제

  while(delNextNode != NULL)    // 두 번째 이후의 노드 삭제 위한 반복문
  {
    delNode = delNextNode;
    delNextNode = delNextNode->next;

    printf("%d을(를) 삭제합니다. \n", delNode->data);
    free(delNode);    // 두 번째 이후의 노드 삭제
  }
}

CH3. 연결 리스트 (Linked list) 1-2

3-2 배열을 이용한 리스트의 구현

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

• “ArrayList.h”

#pragma warning(disable:4996)
#ifndef __ARRAY_LIST_H__ // 헤더 파일 중복선언 방지
#define __ARRAY_LIST_H__

#define TRUE	1
#define FALSE	0

/*** ArrayList의 정의 ****/
#define LIST_LEN	100
typedef int LData; // 실제로 저장할 데이터의 자료형을 결정하기 위한 typedef 선언

typedef struct __ArrayList // 배열기반 리스트를 정의한 구조체
{
	LData arr[LIST_LEN]; // 리스트의 저장소인 배열
	int numOfData;       // 저장된 데이터의 수
	int curPosition;     // 데이터를 참조하는 위치를 기록
} ArrayList; // 배열 기반 리스트를 의미하는 구조체


/*** ArrayList와 관련된 연산들 ****/
typedef ArrayList List; // 리스트의 변경을 용이하게 하기 위한 typedef 선언

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

배열 기반 리스트의 초기화

void ListInit(List * plist) // 구조체 변수가 선언되고 그 주솟값이 인자로 전달
{
	(plist->numOfData) = 0; // 해당 주소가 가리키는 구조체의 numOfData 멤버를 0으로 초기화
	(plist->curPosition) = -1; // LF/LN 함수에서 사용하며, -1은 아무런 위치도 참조하지 않았음을 의미
}

• (plist->curPosition) = -1;에서 -1은 아무런 위치도 참조하지 않았음을 의미
• (plist->curPosition)가 0일 때 첫 번째 데이터의 참조가 진행되었음을 의미
  • LFirst 함수를 참조하고 나면 0이 됨(첫 번째 인덱스 참조했다는 의미)

배열 기반 리스트의 삽입

typedef struct __ArrayList
{
	LData arr[LIST_LEN]; // 실제로 데이터가 저장되는 위치
	int numOfData; // 0으로 초기화된 상태
	int curPosition; // -1로 초기화된 상태
} ArrayList;

• int numOfData는 저장된 데이터가 없으므로 0
  • 실제 다음 데이터가 0번째 인덱스에 저장 되어야 한다는 것을 의미
  • 이를 이용해 실제 다음 데이터가 저장될 인덱스를 이 값을 이용해 얻어 올 수 있음

void LInsert(List * plist, LData data)
{
	if(plist->numOfData > LIST_LEN) // 더 이상 저장할 공간이 없는 경우
	{
		puts("저장이 불가능합니다.");
		return;
	}

	plist->arr[plist->numOfData] = data;  // 데이터 저장
	(plist->numOfData)++; // 저장된 데이터의 수 증가(다음 데이터가 저장될 인덱스 값을 의미함)
}

배열 기반 리스트의 조회

• LFirst 함수와 LNext 함수의 가장 큰 차이점은 (plist->curPosition)의 정의 및 사용
  • LFirst는 (plist->curPosition)를 0으로 초기화하고 0번째 인덱스의 값을 참조
  • LNext는 (plist->curPosition) 값에 해당하는 인덱스의 값을 참조하고 (plist->curPosition)의 크기를 1 증가

int LFirst(List * plist, LData * pdata) // 초기화 및 첫 번째 데이터 참조
{
	if(plist->numOfData == 0) // 저장된 데이터가 하나도 없다면 False 반환
		return FALSE;

	(plist->curPosition) = 0; // 참조 위치 초기화(첫 번째 데이터 참조)
	*pdata = plist->arr[0]; // pdata가 가리키는 공간에 데이터 저장
	return TRUE;
}

int LNext(List * plist, LData * pdata)  // 그 다음 데이터 참조
{
	if(plist->curPosition >= (plist->numOfData)-1)  // 더 이상 참조할 데이터가 없는경우
		return FALSE;

	(plist->curPosition)++; // 현재 위치 1 증가
	*pdata = plist->arr[plist->curPosition];  // 값의 반환은 매개변수로, 함수의 반환은 성공여부 반환
	return TRUE;
}

배열 기반 리스트의 삭제

• 배열의 삭제 원칙
  • {A, B, C, D, E, F, G, …} 에서 C를 삭제
    • C를 제거하고 뒤의 데이터를 하나씩 앞칸으로 이동시킴
    • {A, B, , D, E, F, G, …} -> {A, B, D, E, F, G, H, …}
  • 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; // 삭제 데이터 반환
}

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

• 자료형의 저장 대상을 바꿔보는게 핵심 내용
• Point 라는 내용의 구조체를 정의 및 ADT를 “Point.h”에 정의

typedef struct_point
{
  int xpos;
  int ypos;
} Point;

void SetPointPos(Point *ppos, int xpos, int ypos); // Point 변수의 xpos, ypos 설정
{
  ppos->xpos = xpos;
  ppos->ypos = ypos;
}
void ShowPointPos(Point *ppos); // Point 변수의 xpos, ypos 정보 출력
{
  printf("[%d, %d]\n", ppos->xpos, ppos->ypos);
}
int PointComp(Point *pos1, Point *pos2);  // 두 Point 변수 비교
{
  if(pos1->xpos == pos2->xpos && pos1->ypos == pos2->ypos)
    return 0;
  else if(pos1->xpos == pos2->xpos)
    return 1;
  else if(pos1->ypos == pos2->ypos)
    return 2;
  else
    return -1;
}

• 위처럼 정의된 Point 구조체의 주솟값을 저장 해 보기
  • “ArrayList.h” 에서 변경사항 두가지
  • typedef int LData; 를 typedef Point *LData;로
  • #include "Point.h"추가
• 리스트 구조체 선언 및 초기화, 저장
  • 동적할당 이용
  • ppos 변수에 malloc으로 할당된 주소값을 임시 저장 후 list에 저장(LInsert)

List list;
Point compPos;
Point * ppos;

ListInit(&list);

/*** 4개의 데이터 저장 ***/
ppos = (Point*)malloc(sizeof(Point)); //Point 구조체 변수를 동적할당
SetPointPos(ppos, 2, 1);
LInsert(&list, ppos);  // 리스트에 주소값 저장
...

• 저장된 데이터 참조 및 조회

printf("현재 데이터의 수: %d \n", LCount(&list));

if(LFirst(&list, &ppos))
{
  ShowPointPos(ppos);

  while(LNext(&list, &ppos))
    ShowPointPos(ppos);
}
printf("\n");

• 저장된 데이터 삭제
  • xpos가 2인 모든 데이터 삭제
  • LRemove 함수가 주솟값을 반환하기에 동적 할당 메모리의 해제가 가능
  • 리스트 자료구조에 주솟값을 저장 = 주솟값을 실질적인 데이터로 판단

compPos.xpos=2; // 기준이 될 Point 구조체 멤버의 변수 설정
compPos.ypos=0;

if(LFirst(&list, &ppos))
{
  if(PointComp(ppos, &compPos)==1) // 만약 ppos가 가리키는 동적할당된 구조체의 멤버변수와 compPos의 xpos와 같다면
  {
    ppos=LRemove(&list);  // 해당 구조체 변수 삭제
    free(ppos); // 동적 할당 메모리 해제
  }

  while(LNext(&list, &ppos)) 
  {
    if(PointComp(ppos, &compPos)==1)
    {
      ppos=LRemove(&list); 
      free(ppos);
    }
  }
}

배열 기반 리스트의 장점과 단점

• 배열 기반 리스트의 단점(다음 챕터에서 이를 보완하는 새로운 리스트를 배움)
  • 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
  • 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어남
• 배열 기반 리스트의 장점
  • 데이터 참조가 쉽다. 인덱스 값 기준으로 어디든 한 번에 참조 가능

ImageNet LSVRC 2012 데이터셋 다운로드 받기

Training set(138GB)

• wget http://www.image-net.org/challenges/LSVRC/2012/nnoupb/ILSVRC2012_img_train.tar
• 용량이 큰 만큼 매우 오래 걸림
  • 약 5일정도..
• nohup wget http://www.image-net.org/challenges/LSVRC/2012/nnoupb/ILSVRC2012_img_train.tar 로 백그라운드 다운로드도 가능

Validation set(6.3GB)

• wget http://www.image-net.org/challenges/LSVRC/2012/nnoupb/ILSVRC2012_img_val.tar

추가내용

• 2019년 10월 27일 기준 다운로드 링크가 짤렸으므로 아래 링크에 접속하여 토렌트로 다운로드 가능
  • https://academictorrents.com/collection/imagenet-2012 (from “daeho kim”)

압축 풀기

• 학습 데이터셋 압축 풀기
• mkdir train && mv ILSVRC2012_img_train.tar train/ && cd train
• tar -xvf ILSVRC2012_img_train.tar
• rm -f ILSVRC2012_img_train.tar (만약 원본 압축파일을 지우려면)
• find . -name "*.tar" | while read NAME ; do mkdir -p "${NAME%.tar}"; tar -xvf "${NAME}" -C "${NAME%.tar}"; rm -f "${NAME}"; done

• cd ..

• Validation 데이터셋 압축 풀기
• mkdir val && mv ILSVRC2012_img_val.tar val/ && cd val && tar -xvf ILSVRC2012_img_val.tar

• wget -qO- https://raw.githubusercontent.com/soumith/imagenetloader.torch/master/valprep.sh | bash

• 작업이 완료되면 train 폴더 안에 카테고리별로, val 폴더 안에 카테고리별로 정리되어 들어간다.

ImageNet training in Pytorch example

• https://github.com/pytorch/examples/tree/master/imagenet 참조

중요사항

• 위의 모든 과정 수행 후 해당 폴더(imagenet dataset 저장 폴더)에 가서 n숫자조합 으로 되는 파일 구성이 아닌 다른 파일이나 폴더가 존재하면 삭제한다.
  • 나중에 학습 과정에서 오류 발생
  • ex. train 폴더 내의 ILSVRC2012_img_train 폴더나 val 폴더 내의 ILSVRC2012_img_val.tar 파일

CH3. 연결 리스트 (Linked list) 1-1

3-1 추상 자료형: Abstract Data Type

• ADT와 자료구조의 관계
  • 자료구조의 일부는 아님
  • 단순히 code를 떠나 공학적 측면에서 관련되어있음

컴퓨터 공학에서의 추상 자료형 (Abstract Data Type)

• 추상 자료형은 ADT라고도 불리나 실제 의미상 약간의 차이가 있는 것처럼 느껴질 수 있음
• 이는 실제 의미에서 조금 확장된 의미로 사용되기 때문이며 실제 차이를 보이는것이 아님
  • 즉, 큰 맥락선에선 하나이며 다만 이를 나타내는 형태에서 차이가 나는 것임
• 본 책에서는 자료구조의 관점에서 ADT를 다룸

자료구조에서의 추상 자료형

• 지갑에서 동전을 넣고 빼는 등 지갑이 제공하는 기능들의 행위의 묘사
  • 동전을 넣고 빼는 자세한 과정이 생략되어 있음 (지갑을 연다던가..)
• 이처럼 구체적인 기능의 완성과정을 언급하지 않고 순수하게 기능이 무엇인지를 나열한 것 을 가리켜 추상 자료형(ADT)라고 함
• (추상)자료형 = 기능 (그 기능이 어떻게 동작하는가에 대해 나열하지 않는 것이 추상 자료형)
  • 예를 들어 지갑의 기능을 나열하면 아래와 같음
    • 카드의 삽입 추출
    • 동전의 삽입 추출
    • 지폐의 삽입 추출

• 즉, 기능을 나열 하되 그 과정을 언급하지 않음

• 기능의 명세를 가리켜 왜 자료형(data type)이라 하는것이 왜 포함되는지에 대해 알아보면?
  • int라는 자료형을 생각하면 보통 data를 생각함
    • int라는 데이터는 어떻게 생겼나?
    • int의 기능적 측면으로 본다면 선언, 연산, 초기화 할 때 연산자 를 사용함
    • 하지만 데이터적 관점에서는 자세히 알 수 없음
  • 보통 자료형을 이야기 할 때는 그 기능을 중시 여김
    • 자료형이라 하는것은 연산에 훨씬 더 그 의미가 있음
  • 구조체의 정의 또한 자료형의 정의이나, 기능을 제공하나?
• C에서 코딩이라는 것은?
  • 구조체를 정의하고, 더불어 함수도 같이 정의한다(구조체 정의) 그러고 나서 함수를 정의한다.
  • 구조체를 정의하고(Data) 그와 관련된 연산을 정의
• 예시를 들기 위해 구조체를 이용하여 지갑을 정의

typedef struct_wallet
{
  int coin100Num;
  int bill5000Num;
} Wallet;

• 위처럼 c를 기반으로 구조체를 정의하는 것은 구조체를 기반으로 지갑을 의미하는 Wallet 자료형을 정의하는것
• 하지만 컴퓨터공학 측면에서 위의 구조체 정의만으로 Wallet이라는 자료형의 정의가 완성되는 것이 아님
  • Wallet을 기반으로 하는 연산의 종류를 결정하는 것도 자료형 정의의 일부로 보아야 함
  • 이러한 연산의 종류가 결정되었을 때 자료형의 정의가 완성됨
• 지갑에 대한 예시를 이어 들면 아래와 같음
  • Wallet을 기반으로 제공할 수 있는 기능 관련 연산

int TakeOutMoney(Wallet *pw, int coinNum, int billNum); //돈을 꺼내는 연산
void PutMoney(Wallet *pw, int coinNum, int billNum); // 돈을 넣는 연산

• 이렇듯 C언어에서는 구조체에서 필요로 하는 연산을 함수를 이용해 정의
• 만약 Wallet 구조체가 필요로 하는 연산이 위의 두 종류가 다라면, 이로써 Wallet에 대한 자료형의 정의가 완성됨

• 즉, ‘자료형’의 정의에 ‘기능, 연산’과 관련된 내용을 명시할 수 있음

• 구조체를 정의 할 때, 해당 구조체의 연산을 담당하는 함수를 정의하는것이 중요!
  • 구조체를 정의 하고, 그 연산을 담당하는 함수를 정의하는것이 포함되는것이 구조체 정의
• 예를 들어 int 변수를 선언 할 때, 그에 맞게 연산자가 다 정의된 것이라 여기는것과 동일
  • int 변수에 대해 +,-,* 등등.. 모든 연산자가 int 구조체에 알맞게 동작하는 함수가 정의되어 있는 꼴
• 따라서 자료형의 정의보다, 자료형의 연산을 담당하는 함수의 정의가 더 중요함

구조체 Wallet의 추상 자료형 정의

• 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것을 가리켜 ‘추상 자료형’ 또는 ADT라고 한다.

• Wallet의 ADT(기능 명세서)
  • int TakeOutMoney(Wallet *pw, int coinNum, int billNum);
    • 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼냄
    • 두 번째 인자로 꺼낼 동전의 수, 세 번째 인자로 꺼낼 지폐의 수를 전달
    • 꺼내고자 하는 돈의 총액이 반횐되며 그만큼의 돈은 차감됨
  • void PutMoney(Wallet *pw, int coinNum, int billNum);
    • 첫 번째 인자로 전달된 주소의 지갑에 돈을 넣음
    • 두 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수를 전달
    • 넣은 동전과 지폐의 수 만큼 증가
• 하지만 ADT에 구지 필요없는 기능을 포함시키는것은 바람직하지 않음
  • Wallet 구조체에 동전 및 지폐의 갯수를 반환하는 ADT가 필요한가?
    • 필요 없음. 그냥 구조체의 멤버에 직접 접근하면 됨
• 한 번에 완벽하게 정의 할 필요가 없음(할 수도 없음). 필요하면 나중에 추가해도 되는 구조.
• 구조체 Wallet의 정의를 ADT에 포함 시키지 않아도 됨 (웬만해선 포함시키지 않음)

자료구조의 학습에 ADT의 정의를 포함

• 학습순서
  • 1. 리스트 자료구조의 ADT를 정의
       • 기능을 명시한다는 의미
       • 공부 할 때 기능 중심적으로.
  • 1. ADT를 근거로 리스트 자료구조를 활용하는 main 함수 정의
       • ADT가 잘 정의되었다면, ADT 리스트의 내부 구조를 몰라도 main에서 잘 쓸 수 있기 때문
       • 즉, ADT를 잘 정의 할 수 있도록 하는 연습하기 위함임
  • 1. ADT를 근거로 리스트를 구현
• 2번과 3번의 순서가 바뀌엇다고 생각 할 수 있지만 ADT의 본질을 이해하는데 방해가 되므로 위의 순서를 따름

3-2 배열을 이용한 리스트의 구현

리스트의 이해

• 리스트 자료구조는 구현방법에 따라 크게 두 가지로 나뉨
  • 순차 리스트: 배열을 기반으로 구현된 리스트 (이번 챕터에서)
  • 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트 (다음 챕터에서)
• 이는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에 ADT가 동일하다고 해서 문제가 되지 않음
  • 리스트 자료구조의 기본 기능은 똑같음
  • 다만 그 기능을 제공함에 있어서 특성, 성능 등의 차이가 나타남
• 리스트의 ADT 정의를 위해 리스트 자료구조의 가장 기본적이고 중요현 특성은 다음과 같음
  • 저장 형태: 리스트 자료구조는 데이터를 나란히 저장한다
  • 저장 특성: 중복된 데이터의 저장을 막지 않는다
• 위의 특징이 리스트 ADT를 정의하는데 있어서 고려해야 할 유일한 요소
• 위의 특성을 갖도록 하다 보니 순차/연결 리스트 형태로 구현방법이 나뉘게 됨

리스트 자료구조의 ADT

• 리스트라는 자료구조가 어떠한 특성을 갖는지, 어떠한 식으로 활용할 수 있는지 알 수 있음
  • 구현 방법, 기능의 과정에 대해서는 ADT에 반영되지 않음
  • 기존의 방법에도 기본 특성을 지키는 한에서 새로운 기능을 추가/제거 할 수 있음
• 데이터가 나란히 저장된다는 특성을 기반으로 제공해야 할 기능들을 정의
• 리스트 자료구조의 ADT (Operations)
  • void ListInit(List *plist);
    • 초기화할 리스트의 주소 값을 인자로 전달
    • 리스트 생성 후 제일 먼저 호출되어야 하는 함수
    • C라는 언어 특성 상 변수 선언 후 초기화가 이루어져야 하므로 필요
  • void LInsert(List *plist, LData data);
    • 매개변수 data에 전달된 값을 *plist 주소의 리스트에 저장
    • 데이터를 저장하는 역할
  • int LFirst(List *plist, LData *pdata);
    • 저장된 데이터들 중 첫 번째 데이터를 반환받아 저장할 때 사용
    • 첫 번째 데이터가 pdata가 가리키는 메모리에 저장됨
    • 데이터의 참조를 위한 초기화가 진행
    • 참조 성공시 TRUE, 실패시 FALSE 반환
  • int LNext(List *plist, LData *pdata);
    • LFirst 이후에 두 번째 인자 이후를 얻을 때 호출하며 사용법은 LFirst와 동일
      • 구지 구분짓는 이유는 조회를 처음부터 다시 시작하는 경우등에서 필요하므로(일반적인 패턴)
    • 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장
    • 순차적인 참조를 위해 반복 호출 가능
    • 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 함
    • 참조 성공시 TRUE, 실패시 FALSE 반환
  • LData LRemove(List *plist);
    • LFirst 또는 LNext 함수의 마지막(바로 이전) 반환(참조)된 데이터를 삭제
    • 삭제된 데이터는 반환
    • 마지막 반환 데이터를 삭제하므로 연이는 반복 호출 불허
  • int LCount(List *plist);
    • 리스트에 현재 저장되어 있는 데이터의 수를 반환
• LData는 리스트에 저장할 데이터의 자료형에 제한을 두지 않기 위한 typedef 선언의 결과

리스트의 ADT를 기반으로 정의된 main 함수

• 리스트의 ADT가 정의되었다는 가정 하에 리스트의 활용 예를 main 함수를 이용해 살펴봄
  • 실제로 list가 구현 된 라이브러리가 있다 가정 하고, 그 라이브러리를 기준으로 작성 된 main함수를 살핌
• main 함수를 이해 하면 ADT기능을 갖는 함수 각각의 구조를 이해하고 리스트 자체의 이해가 가능해짐
  • 함수 내의 LInsert 등의 함수들이 어떻게 구현되어있나보다, 어떻게 쓰이냐에 더 집중해서 학습
  • ArrayList.h까지는 열어보고 확인해도 좋지만, ListMain.c를 참고하여 ArrayList.c는 직접 구현해보는편이 좋음
• 리스트의 초기화

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

• 초기화된 리스트에 데이터 저장
  • 리스트는 데이터를 나란히, 순서대로 저장함(순서는 무관)

LInsert(&list, 11);  LInsert(&list, 11);
LInsert(&list, 22);  LInsert(&list, 22);
LInsert(&list, 33);

• 리스트의 데이터 참조 과정
  • LFirst를 처음에 호출 하여 첫 번째 데이터 값을 변수 data에 저장
  • 리스트에 저장된 숫자 처음부터 끝까지 모두 출력(참조)하는 과정
  • LFirst 다음으로 LNext 함수를 호출하는 이유
    • 모든 데이터를 한 번만 참조하고 끝내는 것이면 LNext로만 가능하지만, 데이터의 참조는 자주 일어나고 앞에서부터 참조가 진행되어야 하므로 처음부터 참조를 진행하는 의미를 갖는 LFirst를 별도로 지정함
    • LFirst는 처음 시작을 알리는 용도
  • 데이터 참조 일련의 과정
    • LFirst -> LNext -> LNext -> …

if(LFirst(&list, &data))    // 첫 번째 데이터 조회
{
  printf("%d ", data);

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

• 리스트의 데이터 삭제 방법
  • LRemove 함수는 연이은 호출을 혀용하지 않음
    • 심지어 동작 메커니즘이 불필요한 형태임
  • 기본적으로 리스트 자료구조는 하나씩 가져다가 판단을 하는 형태임
    • 즉, LFirst나 LNext 함수로 각각 값을 가져다가 하나씩 비교하고 삭제하는 형태
    • 삭제가 그냥 하는게 아니라 일련의 참조 과정이 포함되어 삭제가 가능한 형태
  • 일반적으로 아래와 같은 스타일로 리스트 자료구조가 동작하게 됨

if(LFirst(&list, &data)) // 첫 번째 데이터를 가져와서 data에 저장
{
  if(data == 22) // 만약 가져온 데이터가 22면
    LRemove(&list); // 해당 데이터 삭제

  while(LNext(&list, &data)) // 두 번째 데이터부터 가져와서 data 저장
  {
    if(data == 22) // 만약 가져온 데이터가 22면
      LRemove(&list); // 해당 데이터 삭제
  }
}