[열혈자료구조] 3강. 연결 리스트(Linked List) 1 - (1)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

추상 자료형(Abstract Data Type, ADT)

추상 자료형 = 각 기능의 구현 등 세부적인 내용은 나타내지 않고, 기능 그 자체만 나열한 것

 

예를 들어, 지갑을 정의하는 추상 자료형에 대해 생각해 보자. 지갑에는 100원짜리 동전과 5000원짜리 지폐가 들어갈 수 있다. 각 화폐의 개수를 변수로 하는 구조체를 이용하여 지갑을 정의하자.

typedef struct _wallet
{
    int num_coin_100;
    int num_bill_5000;
    
}Wallet;

또한, wallet이라는 자료형에 관련된 연산을 결정하는 것도 자료형을 정의하는 데 필요하다.

int TakeOutMoney(Wallet * pw, int coinNum, int billNum);
void PutMoney(Wallet * pw, int coinNum, int billNum);

 

C언어에서는 구조체에서 필요로 하는 연산을 함수를 이용해 정의한다. 이러한 기능과 연산들이 모여서 wallet이라는 자료형을 정의한다. 그렇다면 wallet은 자료구조인가? 만약 이 자료구조를 정의하는 데 위에 적은 것이 필요한 연산의 전부라면, wallet이라는 자료형을 완성할 수 있고, 이전 포스팅(https://cascade.tistory.com/65)에서 언급한 자료구조 정의에 따라 자료구조라고 할 수 있을 것이다. 

 

이때 wallet의 ADT를 정의하기 위해서는 wallet의 "기능"을 잘 명시하면 된다. 즉 위에서 정의한 wallet의 돈을 넣고 빼는 기능인

• TakeOutMoney
• PutMoney

가 들어가면 되고, wallet 자체가 어떻게 구성되어 있는지는 포함되지 않아도 된다(기능이 아니므로!!). 이는 C언어에서 입력, 출력 코드는 자유롭게 사용하지만 이러한 입출력이 저장되는 FILE 구조체의 내부 모습은 알 필요가 없는 것과 같은 맥락이다.

 

리스트의 ADT

리스트는 구현 방법에 따라 아래 두 가지로 나뉜다.

• 순차 리스트
• 연결 리스트

이들을 구현할 때, 정의하는 사람에 따라 ADT가 같을 수도 있고 다를 수도 있다. 즉, ADT에 표준이 있는 것은 아니다. 하지만 아래의 기본적인 특징은 정의에 반드시 포함되어야 한다.

리스트는 데이터를 나란히 저장하며 같은 데이터를 중복하여 저장할 수 있다.

 

리스트의 ADT에서 중요한 것은, "데이터를 어떻게 나란히 저장할지"를 고민하는 것이 아니라, 데이터가 나란히 저장되었다고 "치고" 기능을 정의하는 것이다. 리스트 자료구조를 다루는 데는 아래가 필요하다.

1. 리스트의 생성: 리스트의 주소 값을 인자로 전달하고 초기화한다.
void ListInit(List *plist);
2. 데이터의 저장: 리스트에 데이터를 저장한다.
void LInsert(List *plist, LData data);
3. 첫 번째 데이터 참조: 새로운 메모리를 잡고 리스트의 첫 데이터를 옮긴다. 성공 시 1, 실패 시 0를 반환한다.
int LFirst(List *plist, LData *pdata);
4. 다음 데이터 참조: 참조된 데이터의 다음 데이터가 순서대로 pdata에 저장된다. 성공 시 1, 실패 시 0을 반환한다.
int LNext(List *plist, LData *pdata):
5. 마지막 반환 데이터 삭제: LFirst 혹은 LNext 함수가 마지막으로 반환한 데이터를 삭제한다.
LData LRemove(List *plist);
6. 리스트 크기: 리스트에 저장된 데이터 수를 반환한다.
int LCount(List *plist);

 

LData는 리스트에 들어갈 데이터의 자료형이다. 또한 ListInit 함수는 Call by Reference의 방식으로 리스트 주소 값을 인자로 받는다. LNext 함수는 반복 호출이 가능하며, 새로운 참조는 반드시 LFirst로 해야 한다. 이를 아래와 같이 구현하자.

 

#include <stdio.h>
#include "ArrayList.h"

int main(void){
    //Array의 생성
    List list;
    int data;
    ListInit(&list);
    
    //데이터 저장
    LInsert(&list, 1);
    LInsert(&list, 2);
    LInsert(&list, 3);
    LInsert(&list, 5);
    LInsert(&list, 8);

    //저장된 데이터 전체 출력
    printf("current number of data:%d\n", LCount(&list));

    if(LFirst(&list, &data)){
        printf("%d ", data);
        while(LNext(&list, &data)){
            printf("%d ", data);
        }
    }
    
    //숫자 2를 탐색 후 삭제
    if(LFirst(&list, &data)){
        if(data == 2) LRemove(&list);
        while(LNext(&list, &data)){
            if(data == 2) LRemove(&list);
        }
    }

    //삭제 후 남은 데이터 전체 출력
    printf("current number of data:%d\n", LCount(&list));
    if(LFirst(&list, &data)){
        printf("%d ", data);
        while(LNext(&list, &data)) printf("%d ", data);
    }
    
    return 0;
}

 

헤더파일 "ArrayList.h" 는 윤성우의 열혈자료구조 블로그(https://blog.naver.com/oedu/223011150597)에서 다운로드 받을 수 있다. 작성한 코드와 ArrayList.h, ArrayList.c를 포함하여 3개를 한꺼번에 컴파일하고 실행하면 아래와 같이 출력된다.

 

Array의 2를 삭제하는 과정에서 LRemove 함수가 언제 호출되는지 살펴보자. LFirst 혹은 LNext가 데이터를 참조한 후 이를 삭제하는 것으로 구현이 되어있는데, 이는 LRemove가 LFirst 혹은 LNext가 마지막으로 반환한 데이터를 삭제한 것으로 정의되었기 때문이다.

 

실제로 이 코드를 작성하면서 ArrayList.c, ArrayList.h 같은 파일들은 한 번도 안 열어보았다. 오직 함수의 정의 내용만 보고 구현을 완성할 수 있는데, 이것이 바로 추상 자료형의 개념이다. printf, scanf 같은 함수들도 구현 내용을 알고 쓰는 것이 아니라 어떤 걸 넣으면 어떤 동작을 한다는 것만 알면 쓸 수 있는 것이다.

---

리스트의 구현

main 함수에서는 리스트의 각 함수에 대한 정의를 알 피료 없이 그냥 가져다 썼다. 즉 다음을 기억하는 것이 가장 중요하다.

"자료구조의 구현" 과 "구현된 자료구조의 활용"을 완전히 구분하자

 

이제 헤더파일(ArrayList.h)와 ArrayList.c 를 분석하여 리스트 자료구조가 어떻게 구현되었는지 살펴보자. 먼저 헤더파일 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

 

위 헤더파일을 보면, 리스트를 (1) 배열로 정의하는 방식과 (2) 연결 리스트(Linked List)로 정의하는 방식 중 배열로 정의하는 방식을 사용하고 있음을 알 수 있다. 리스트에 들어가는 자료를 LData (int)로 정의했고, ArrayList를 LData 자료형을 최대 100개까지 받을 수 있도록 했다. 재미있는 점은, 이 리스트의 정의를 배열에서 연결 리스트로 바꾸어도 main함수에서는 같은 코드를 그대로 사용할 수 있다.

 

ListInit

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

 

리스트르 초기화하는 코드이다. ListInit 함수는 구조체 포인터 plist가 가리키는 numOfData를 0으로 하여 배열에 원소가 없음을 나타내고, 현재 위치(curPosition)을 -1로 설정한다.

 

LInsert

void LInsert(List * plist, LData data)
{
	if(plist->numOfData > LIST_LEN) 
	{
		puts("cannot save.");
		return;
	}

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

 

LInsert는 리스트에 새로운 LData 타입의 원소를 추가하는 함수로, 데이터 수가 LIST_LEN(100)보다 많으면 저장하지 못하도록 하며, 그렇지 않을 경우 numOfData를 1 늘리고 data를 numOfData를 인덱스로 하는 리스트의 위치에 삽입한다.

 

LFirst, LNext

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

 

LFirst는 리스트가 비어 있으면 FALSE를 리턴하고, 그렇지 않으면 curPostition을 0으로 변경한 뒤 해당 값을 복사하여 pdata라는 새로운 메모리에 저장한다. 반면, LNext는 curPostion을 특정 값으로 재설정하는 것이 아닌 1 증가시키는 연산으로 순서대로 참조할 수 있도록 하였다.

 

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

 

LRemove 함수가 호출되면, curPosition을 확인하여 가장 마지막으로 LFirst 혹은 LNext에 의해 조회된 데이터를 확인한다. 그리고 그 그 데이터를 삭제한다. 삭제한 데이터 뒤의 값들은 명령문을 이용하여 한 칸씩 앞으로 당겨진다. 이때 새로운 curPosition은 1 감소하는데, 이는 삭제할 데이터 바로 앞에 있었던 값을 가리킨다. curPosition을 그냥 두면 삭제할 데이터 다음의 값을 가리키게 되는데, 이는 아직 참조되지 않았기 때문이다.