[Data Structure] Chapter 03: 추상 자료형과 배열 기반 리스트

자료구조에서의 추상 자료형(ADT)을 이해하고, 배열 기반 리스트를 구현해보자.

 

 

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

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

 

 예를 들어 Wallet이라는 구조체가 있을 때, 이 구조체에 돈을 넣을 수도 있고 꺼낼 수도 있다. 이를 ADT로 변환하면 다음과 같다.

Wallet의 ADT

int TakeOutMoney(Wallet * pw, int coinNum, int billNum)
- 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.
- 두, 세 번째 인자로 꺼낼 동전의 수와 지폐의 수를 전달한다.
- 꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.

void PutMoney(Wallet * pw, int coinNum, int billNum)
- 첫 번재 인자로 전달된 주소의 지갑에 돈을 넣는다.
- 두, 세 번째 인자로 넣을 동전의 수와 지폐의 수를 전달한다.
- 넣은 만큼 동전과 지폐의 수가 증가한다.

 

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

리스트의 이해

• 순차 리스트: 배열을 기반으로 구현된 리스트
• 연결 리스트: 메모리의 동적 할당을 기반으로 구현된 리스트

 

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

• 이후 구현할 자료구조와의 이름충돌을 막기 위해 리스트를 의미하는 L을 접두사로 함수의 이름을 정의했다.
• 위의 정보만 가지고도 리스트 자료구조가 제공하는 기능을 어느 정도 예측할 수 있어야 한다.

 

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

 파일명 : 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;
}

 

아직 헤더파일과 함수를 구현하는 파일은 없지만 실행 결과는 다음과 같이 나온다고 가정하자.

현재 데이터의 수: 5
11 11 22 22 33

현재 데이터의 수: 3
11 11 33

-> printf, scanf 함수처럼 내부 구현을 몰라도 잘 활용할 수 있는 것처럼, 위에서 소개한 리스트 관련 함수들을 자유롭게 사용할 수 있어야 한다.

 

문제 03-1 구현 코드

1. 리스트를 생성 및 초기화 한 다음, 정수 1부터 9까지 리스트에 저장한다.

2. 리스트에 저장된 값을 순차적으로 참조하여 그 합을 계산하여 출력한다.

3. 리스트에 저장된 값들 중 2의 배수와 3의 배수에 해당하는 값을 모두 삭제한다.

4. 마지막으로 리스트에 저장된 데이터를 순서대로 출력한다.

 

 위 조건을 모두 만족하는 main함수를 정의해보자.

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

int main(void)
{
    List list;
    int data;
    int sum;
    ListInit(&list);

    LInsert(&list, 1); LInsert(&list, 2);
    LInsert(&list, 3); LInsert(&list, 4);
    LInsert(&list, 5); LInsert(&list, 6); 
    LInsert(&list, 7); LInsert(&list, 8); 
    LInsert(&list, 9);

    if(LFirst(&list, &data))    
    {
        sum += data;

        while(LNext(&list, &data))  
            sum += data;
    
        printf("리스트에 저장된 값들의 합: %d\n", sum);
    }

    printf("\n");

    if(LFirst(&list, &data))
    {
        if(data%2 == 0 || data%3 == 0)
            LRemove(&list);
        
        while(LNext(&list, &data))
        {
            if(data%2 == 0 || data%3 == 0)
                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;
}

 

헤더파일의 정의

 파일명 : ArrayList.h

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#define TRUE	1	//'참'을 표현하기 위한 매크로 정의
#define FALSE	0	//'거짓'을 표현하기 위한 매크로 정의

#define LIST_LEN	100
typedef int LData;	//LData에 대한 typedef 선언

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

• LData와 List를 typedef 선언함으로써, 리스트에 저장되는 데이터의 자료형과 사용하는 리스트의 종류를 바꾸기에 간편해진다.

 

헤더파일에 선언된 함수의 정의

 파일명 : ArrayList.c

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

void ListInit(List * plist)
{
	(plist -> numOfData) = 0;	//리스트에 저장된 데이터의 수는 0
	(plist -> curPosition) = -1;	//현재 아무 위치도 가리키지 않음
}

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 -> curPosition) == 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 -> curPosition++;
	*pdata = plist -> arr[plist -> curPosition];
	return TRUE; 
}

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 -> curPosition--;	//가장 최근에 참조된 데이터의 인덱스 정보를 담기 위해
	plist -> numOfData--;

	return rdata;
}

int LCount(List * plist)
{
	return plist -> numOfData;
}

• LFirst 함수는 curPosition에 저장된 값을 0으로 재설정함으로써, 데이터의 참조가 앞에서부터 다시 진행되도록 하는 역할을 하기 때문에 LNext 함수와 분리해 정의한다.

 처음에 curposition이 -1로 초기화되니까 LFirst와 LNext 기능을 하나로 합쳐서 다음과 같이 구현할 순 없나 생각해봤다.

void isEmpty(List * plist, LData * pdata)
{
   if((plist -> curPosition) == 0)         //저장된 데이터가 하나도 없다면
      return FALSE;

   return FALSE;
}

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

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

  그러나 위와 같이 함수를 구현하면 LFirst와 같이 curPosition을 제어하는 기능이 사라지기 때문에, LFirst와 LNext 함수를 나누는 것은 current position을 제어하는 함수가 존재한다에 의미가 있다.

• LRemove함수는 curPosition을 이용해 가장 최근에 반환된 인덱스의 데이터를 삭제하고, 해당 위치를 채우는 방식으로 정의한다.

 

리스트에 구조체 변수 저장

• 위에서는 리스트에 단순히 정수를 저장했지만, 리스트에는 각종 다양한 데이터를 저장할 수 있다.
• 이번에는 구조체 Point를 정의하고, 해당 구조체 변수의 주소 값을 저장해보자.

 

 파일명 : Point.h

#ifndef __POINT_H__
#define __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);

#endif

 

 파일명 : Point.c

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

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

void ShowPointPos(Point * ppos)
{
    printf("xpos: %d, ypos: %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;
}

 

구조체 Point와 관련함수들의 정의

• ArrayList.h 파일에서는 Point.h 헤더파일 선언문과, typedef int LData;가 typedef Point * LData;로 바뀌는 거 말고는 변경점이 없다.
• ArrayList.c 파일은 변경하지 않아도 된다.

 파일명 : PointListMain.c

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

int main(void)
{
    List list;
    Point compPos;
    Point * ppos;

    ListInit(&list);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 1);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 2, 2);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 3, 1);
    LInsert(&list, ppos);

    ppos = (Point*)malloc(sizeof(Point));
    SetPointPos(ppos, 3, 2);
    LInsert(&list, ppos);

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

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

        while(LNext(&list, &ppos))
            ShowPointPos(ppos);
    }

    printf("\n");

    /*** 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);
            }
        }
    }

    /***삭제 후 남은 데이터 전체 출력***/
    printf("현재 데이터의 수: %d \n", LCount(&list));

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

    return 0;
}

현재 데이터의 수: 4 
xpos: 2, ypos: 1 
xpos: 2, ypos: 2 
xpos: 3, ypos: 1 
xpos: 3, ypos: 2 

현재 데이터의 수: 2 
xpos: 3, ypos: 1 
xpos: 3, ypos: 2

• LRemove 함수가 삭제된 데이터를 반환하게 함으로써, 리스트에서 메모리의 해제까지 책임질 수 있게 되었다.

 

배열 기반 리스트의 장단점

 배열 기반 리스트의 장단점은 보통 '연결 기반 리스트'를 기준으로 비교한다.

 

배열 기반 리스트의 단점

• 배열의 길이가 초기에 결정되어야 하고, 변경이 불가능하다.
• 삭제의 과정에서 데이터의 이동(복사)가 빈번히 일어난다.

 

배열 기반 리스트의 장점

• 데이터의 참조가 쉽고, 인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.

 

---

참고자료

• 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11