Chapter 03. 연결 리스트 (Linked List) 1

 

---

1. 추상 자료형: Abstract Data Type

추상 자료형 간단하게 ADT 를 의미한다.
ADT의 주된 정의는 아래와 같다.

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

 

전등의 추상 자료형을 정의해 본다면,
ADT of Lamp

- Data : Power, LeftButton, RightButton (전원, 왼쪽 버튼, 오른쪽 버튼)

-operation

                   : PowerOn()                    전원을 키다.

                   : PowerOff()                     전원을 끄다.

                   : LeftButtonClick()            왼쪽 버튼 클릭

                   :RightButtonClick()           오른쪽 버튼 클릭

 

더 나아간다면, 추상자료형은 사용설명서와 같이 함수의 기능을 명세해주는 것이다.

ADT의 개념을 도입해서 자료구조를 정의한다면, 아래의 3가지 수칙은 지키는 것이 좋다고 한다.

1. 리스트 자료구조의  ADT를 정의한다. (기능을 명세한다.)
2. ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의한다.
(ADT를 잘 정의했다면, 구현하지 않아도 main 함수를 정의할 수 있다.) 
3. ADT를 근거로 리스트를 구현한다.

 

---

2. 리스트 자료구조의 ADT 1

 아래는 정의된 ADT를 설명한다. 설명한 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);
- 리스트에 저장되어 있는 데이터의 수를 반환한다.

 

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

ADT를 이용해 Main 함수를 작성한다.

 

 2.2 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 선언

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


/*** ArrayList와 관련된 연산들 ****/
typedef ArrayList List;         // 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

위와 같이 헤더파일은 생성된다.

여기서 중요한 것은 arr[ ] 을 담고있는 ArrayList를 선언하여, 연결리스트를 만들어주어야한다.(구조체를 생각해야한다.)

 

 2.3 ListInit 구현

배열 기반 리스트의 초기화를 담당한다.

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

초기화할 2가지 대상은 numOfData 와 curPosition이다.

numOfData = 0 으로 만들어주는 것은 초기화를 진행하므로, 0개를 의미한다.
curPosition는 -1로 어떤 위치도 참조하지 않았음을 의미한다.

 

 2.4 LInsert 구현

배열 기반 리스트의 삽입을 담당한다.

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

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

numOfData의 값이 리스트 범위를 초과하면 저장이 불가한 것을 보여준다.

plist는 arr[numOfData] 에 data 값을 저장시킨다. 그리고 증가했으니, numOfData를 ++로 증가시킨다.

 

 2.5 LFirst 구현

배열 기반 리스트의 조회

int LFirst(List * plist, LData * pdata)
{
	if(plist->numOfData == 0)
		return FALSE;

	(plist->curPosition) = 0;
	*pdata = plist->arr[0];
	return TRUE;
}

numOfData == 0 일때, 저장된 데이터가 없으므로 FALSE를 return 한다.

else 인 경우, curPosition을 0으로 만들어 첫 번째 데이터의 참조를 의미하도록 선언한다.

마찬가지로 *data = plist->arr[0] 도 첫 번째 arr[0] 을 참조하는 것을 직관적으로 보여주기 위해 사용한다.

 

 2.6 LNext 구현

배열 기반 리스트의 조회

int LNext(List * plist, LData * pdata)
{
	if(plist->curPosition >= (plist->numOfData)-1)
		return FALSE;

	(plist->curPosition)++;
	*pdata = plist->arr[plist->curPosition];
	return TRUE;
}

여기서는 (plist->curPosition)++ 를 선언하여 arr[] 이 다음 데이터를 받게끔 한다.

 

 2.7 LRemove 구현

배열 기반 리스트의 삭제

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;          	     // 삭제된 데이터의 반환
}

rpos 로 삭제할 데이터의 인덱스 값을 참조한다.
rdata = arr[rpos] 로 지정한 것은 삭제할 데이터를 임시로 저장하는 것이다.

curPosition도 마찬가지로 감소해야한다.
curPosition은 가장 최근에 참조가 이루어진 데이터의 인덱스 값을 저장하기 때문에, 해당 인덱스가 지워진다면,
감소를 시켜 이전 인덱스를 가리키록 설정해야한다.

삭제되는 데이터는 반환의 과정을 통해서 되돌려주는 것이 옳으므로 return rdata를 해야한다. 

 

여기서 return rdata를 하는 이유는 malloc 함수를 사용해 동적할당을 적용하므로 부터 시작한다.

동적할당을 하고 난후 remove를 한다고 하면 메모리 공간의 삭제까지 진행이 되는 것은 아니다
그렇기 때문에, 위처럼 return을 하는 rdata를 동적할당에서는 free( ) 함수의 호출까지 진행해야 한다.