Chap 03. 연결 리스트(Linked List) 1 [윤성우의 열혈 자료구조]

doriskim·2022년 11월 30일
자료구조
0

윤성우의 열혈 자료구조

목록 보기
3/9

*본 내용은 [윤성우의 열혈 자료구조] 책과 강의를 보고 공부하면서 요점 정리한 내용입니다.

Chap 03-1: 추상 자료형: Abstract Data Type

🔳 추상 자료형(ADT)

✔추상 자료형(ADT)이란?

구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것

✔예시: 지갑의 추상 자료형

  • 지갑의 추상 자료형 (지갑의 기능)
    ∙ 카드의 삽입
    ∙ 카드의 추출(카드를 빼냄)
    ∙ 동전의 삽입
    ∙ 동전의 추출(동전을 빼냄)
    ∙ 지폐의 삽입
    ∙ 지폐의 추출(지폐를 빼냄)

  • 지갑을 의미하는 구조체 Wallet의 정의
    기능의 명세를 가리켜 왜 자료형이라 하는 것일까?
    자료형의 정의는 연산에 의미가 있다. (자료형 int를 생각해보자.)
    완전한 자료형의 정의로 인식되기 위해서는 해당 자료형과 관련이 있는 연산(함수)이 함께 정의되어야 한다.
    +) 프로그래밍의 기본이 되는 순서는 구조체와 함수를 더불어 정의하고 추가적인 함수를 정의해야 한다.

//자료형 Wallet의 정의
typedef struct _wallet
{
	int coin100Num;		//100원짜리 동전의 수
    int bill5000Num;	//5000원짜리 지폐의 수
}Wallet;

//자료형 Wallet의 정의의 일부
int TakeOutMoney(Wallet* pw, int coinNum, int billNum);	//돈 꺼내는 연산
void PutMoney(Wallet * pw, int coinNum, int billNum);	//돈 넣는 연산
  • Wallet의 ADT (사용설명서, 기능명세서)
    (구조체 Wallet의 정의를 ADT에 포함시키지 않아도 된다.)
    ∙ int TakeOutMoney(Wallet * pw, int coinNum, int billNum)
    첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.
    두 번째 인자로 꺼낼 동전의 수, 세 번째 인자로 꺼낼 지폐의 수를 전달한다.
    꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.
    ∙ int PutMoney(Wallet * pw, int coinNum, int billNum)
    첫 번째 인자로 전달된 주소의 지갑에 돈을 넣는다.
    두 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수를 전달한다.
    넣은 만큼 동전과 지폐의 수가 증가한다.

✔ 자료구조 학습의 옳은 순서

  1. 리스트 자료구조의 ADT를 정의한다. (기능 중심)
  2. ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 먼저 정의한다.
  3. ADT를 근거로 리스트를 구현한다.
  • 자료구조의 내부 구현을 모르고도 해당 자료구조의 활용이 가능하도록 ADT를 정의하는 것이 옳다.
  • main함수를 먼저 접하게 되면, 구현할 자료구조를 구성하는 함수들을 잘 이해할 수 있다.

Chap 03-2: 배열을 이용한 리스트의 구현

🔳 리스트

✔ 리스트의 이해

  • 리스트의 구분
    ∙ 순차 리스트: 배열을 기반으로 구현된 리스트
    ∙ 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트
    (이는 구현 방법을 기준으로 한 구분으로 순차 리스트, 연결리스트 두 리스트의 ADT(기능)는 동일하다.)

  • 리스트의 특징
    ∙ 저장 형태: 데이터를 나란히(하나의 열로) 저장한다.
    ∙ 저장 특성: 중복이 되는 데이터의 저장을 허용한다.
    위와 같은 특징을 나타내기 위해 배열과 연결리스트를 이용한다.

🔳 리스트 자료구조의 ADT

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

✔ 초기화

void ListInit(List * plist);
∙ 초기화할 리스트의 주소 값을 인자로 전달한다.
∙ 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

✔ 데이터 저장

void LInsert(List * plist, LData data);
∙ 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

✔ 첫 번째 데이터의 탐색 및 탐색 초기화

void 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);
∙ 리스트에 저장되어 있는 데이터의 수를 반환한다.

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

✔ 리스트의 초기화

int main(void)
{
	List list;			//리스트의 생성
    ....
    ListInit(&list);	//리스트의 초기화
    ....
}

✔ 리스트의 데이터 저장

int main(void)
{
	....
	LInsert(&list, 11);	//리스트에 11을 저장
   	LInsert(&list, 22);	//리스트에 22을 저장
	LInsert(&list, 33);	//리스트에 33을 저장
	...
}

✔ 리스트의 데이터 참조

리스트 처음부터 끝까지 데이터 출력

int main(void)
{
	....
    if(LFirst(&list, &data))	//첫 번째 데이터 변수 data에 저장
    {
    	printf("%d", data);
        while(LNext(&list, &data))	//두 번째 이후 데이터 변수 data에 저장
        	printf("%d ",data);
    }
    ....
}
  • LFirst(&list, &data), LNext(&list, &data)에서 반환된 TRUE(1), FALSE(0) 값을 통해 if, while문 실행
  • LFirst와 LNext를 구분하는 이유: LFirst를 통해 참조 시작의 기준점을 설정하기 위해

✔ 리스트의 데이터 삭제

int main(void)
{
	....
    if(LFirst(&list, &data)
    {
    	if(data == 22)
        	LRemove(&list);	//위의 LFirst 함수를 통해 참조한 데이터 삭제
        while(LNext(&list, &data))	//LNext가 False 반환할 때까지(끝까지)
        {
        	if(data == 22)
            LRemove(&list);	//위의 LNext 함수를 통해 참조한 데이터 삭제
        }
    }
}

※주의) LRemove 함수는 연이은 호출을 허용하지 않는다!

🔳 배열 기반 리스트

✔ 실행을 위해 필요한 파일들 (※자료실에 있음)

  • ArrayList.h: 리스트 자료구조의 헤더파일
  • ArrayList.c: 리스트 자료구조의 소스파일
  • ListMain.c: 리스트 관련 main 함수가 담긴 소스파일 --> 이 파일을 봐보자.
  • 실행 결과
    현재 데이터의 수: 5
    11 11 22 22 33
    현재 데이터의 수: 3
    11 11 33

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

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 선언, 
					// 저장 대상을 바꾸고 싶으면 int를 수정하면 됨

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;	// 아무것도 저장되어 있지 않음
    (plist->curPosition) = -1; 	// -1은 아무런 위치도 참조하지 않았음을 의미
}
  • 실제로 초기화할 대상은 구조체 변수의 멤버이다. 따라서 초기화 함수의 구성은 구조체의 정의를 기반으로 한다.
  • LFirst와 LNext를 어떻게 정의하냐에 따라 curPosition의 초기화 값(-1)이 결정된다.
    여기서 curPosition이 0이라는 것은 첫 번째 데이터 참조가 진행 됐음을 의미한다.

✔ 배열 기반 리스트의 삽입

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];		// pdata가 가리키는 공간에 데이터 저장
    return TRUE;
}
  • 그 다음 데이터 참조
int LNext(List * plist, LData * pdata)
{
	if(plist->curPosition >= (plist->numOfData)-1	// 더 이상 참조할 데이터가 없다면
    	return FALSE;
	(plist->curPostion)++;
    *pdata = plist->arr[plist->curPosition];
    return TRUE;
}
  • 값의 반환은 매개변수를 통해서! 함수의 반환은 성공여부를 알리기 위해서!
  • curPosition은 이번에 참조할 위치의 index 값으로 갱신한다. 그 결과로 어디까지 참조됐는지 알 수 있다.

✔ 배열 기반 리스트의 삭제

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;			// 삭제된 데이터의 반환
}
  • 삭제 기본 모델
  • 주의) 삭제되는 데이터는 반환의 과정을 통해서 되돌려주는 것이 옳다!
  • 참조 위치를 하나 되돌려야 하는 이유
    가장 최근에 참조가 이루어진 data가 B이므로 D가 아닌 B를 가리키게 해주어야 한다.

🔳 배열 기반 리스트에 구조체 변수 저장하기

리스트의 저장 대상을 int형 변수가 아닌 구조체 변수로 바꾸어보자.

✔ 실행을 위한 파일 구성 (5개)

  • Point.h, Point.c: 구조체 Point를 위한 파일
  • ArrayList.h, ArrayList.c: 배열 기반 리스트
  • PointListMain.c: 구조체 Point의 변수 저장
  • 실행 결과
    현재 데이터의 수: 4
    [2, 1][2, 2]
    [3, 1][3, 2]
    현재 데이터의 수: 2
    [3, 1][3, 2]

※ 헤더파일(ArrayList.h)은 변경될 수 있지만 소스파일(ArrayList.c)은 기능 개선되거나 버그 잡을 때 아니면 변경하면 안 됨

✔ 리스트에 저장할 Point 구조체 변수의 헤더파일 선언

Point.h

typedef struct _point
{
	int xpos;
	int ypos;
} Point;

// Point 변수의 xpos, ypos 값 설정
void SetPointPos(Point * ppos, int xpos, int ypos);

// Point 변수의 xpos, ypos 정보 출력 
void ShowPointPos(Point * ppos);

// 두 Point 변수의 비교
int PointComp(Point * pos1, Point * pos2);

✔ 구조체 Point 관련 소스파일

Point.c

void SetPointPos(Point * ppos, int xpos, int ypos) // 초기화
{
	ppos->xpos = xpos;
	ppos->ypos = ypos;
}

void ShowPointPos(Point * ppos) // 출력
{
	printf("[%d, %d] \n", ppos->xpos, ppos->ypos);
}

int PointComp(Point * pos1, Point * pos2) // 비교
{
	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;
}

✔ ArrayList.h의 변경 사항 두 가지

  • 구조체 변수를 저장하게 되면서 ArrayList.h에서 변경된 두 가지
  1. typedef 선언 변경
    typedef inf LData; --> typedef Point * LData;
  2. #include "Point.h" // ArrayList.h에 추가할 헤더파일 선언문

※ typedef 선언에서 보이듯이 실제로 저장을 하는 것은 Point 구조체 변수의 주소 값이다.

✔ PointListMain.c

  • 초기화 및 저장
int main(void)
{
	List list;
    Point compPos;
    Point * ppos;
    
    ListInit(&list);
    
    /*** 4개의 데이터 저장 ***/
	// 다음을 4번 반복    
    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 1);
    LInsert(&list, ppos); // 포인터 구조체의 주소값을 저장
    ......
}
  • 참조 및 조회
int main(void)
{
	......
	/*** 저장된 데이터의 출력 ***/
	printf("현재 데이터의 수: %d \n", LCount(&list));

	if(LFirst(&list, &ppos))
	{
		ShowPointPos(ppos);
		
		while(LNext(&list, &ppos))
			ShowPointPos(ppos);
	}
	printf("\n");
    ......
}
  • 삭제
int main(void)
{
	......
	/*** 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);
			}
		}
	}
    ......
}

  • LRemove()가 삭제 값을 반환해 주어야 하는 이유
    LRemove()가 삭제 값을 반환해 주기 때문에 그 반환된 값으로 free()가 가능해진다.

  • 동적할당된 메모리까지 소멸되나? NO!
    리스트 자료구조의 책임은 삭제까지 담당하는 것이 아님.
    주소값이 동적할당된 경우도 있지만 아닌 경우도 있음. 이걸 리스트 자료구조가 판단하는 것은 무리이므로 우리가 free() 해주어야 함.
    삭제는 단지 주소가 가리키는 값과 주소 사이의 연결 관계를 끊는 것일 뿐이다.

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

  • 배열 기반 리스트의 단점
    ∙ 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.
    ∙ 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

  • 배열 기반 리스트의 장점
    ∙ 데이터 참조가 쉽다. 인텍스 값 기준으로 어디든 한 번에 참조 가능!

profile
doriskim
이전 포스트

Chap 02. 재귀 (Recursion) [윤성우의 열혈 자료구조]

다음 포스트

Chap 04. 연결 리스트(Linked List) 2 [윤성우의 열혈 자료구조]

0개의 댓글

관련 채용 정보