[C++, 자료구조] 순차 리스트(ArrayList)와 추상 자료형

■ 추상 자료형(Abstract Data Type)

[추상 자료형(Abstract Data Type)]

리스트(List) 자료구조에 대해 설명하기 전에 먼저 추상 자료형이 뭔지 알아보자.

추상 자료형(Adstract Data Type : ADT)은 “자료형이 어떻게 구현되어 있는지는 숨기고 무엇을 할 수 있는지만 정의한 자료형”이다.

[추상 자료형 예시]

예를 들어 지갑을 생각해 보면, 우리는 단지 지갑에 지폐나 카드를 넣고 꺼내는 “기능”만 알고 있다.

하지만 실제로 지갑을 열고, 돈을 넣고, 다시 닫는 “구제척인 과정(구현 방식)”은 생각하지 않는다.

• 즉 “어떻게”가 아니라 “무엇을 할 수 있는가”에 초점을 맞춘 개념이 바로 추상 자료형(ADT)이다.

struct wallet
{
	int coin100Num;
	int bill5000Num;
}wallet;

	int TakeOutMoney(wallet* pw, int coinNum, int billNum) {...};
	void PutMoney(wallet* pw,int coinNum, int billNum){...};

[Wallet 추상 자료형 예시]

간단하게 Wallet이라는 자료형을 만들고, 구조체 Wallet의 추상 자료형(TakeOutMoney(), PutMoney())을 만들었다.

 

🤔 구조체 Wallet의 정의와 멤버 변수는 추상 자료형에 포함시켜야 할까?

int main()
{
	wallet myWallet;
	
	PutMoney(&myWallet, 10, 5);
	int ret = TakeOutMoney(&myWallet, 3, 2);
}

 

필요한 정보라면 포함시켜도 되지만, 불필요한 정보를 포함시키면 안 된다. 위의 예처럼 Wallet을 기반으로 돈을 넣고 빼는 데 있어서 Wallet의 멤버가 어떻게 구성되어 있는지는 알 필요 없다.

 

또한, 멤버 변수를 확인하기 위한 연산을 위의 추상 자료형에 추가하는 것이 옳은 방향이다.

 

■ 리스트(List)

보통 우리가 리스트 자료구조에 대해 얘기하면, 제일 먼저 떠오르는 게 연결 리스트(Linked List)이지만, 사실 리스트는 구현 방법에 따라서 2~3가지 정도로 나뉜다.

• 순차 리스트 : 배열(Array)을 기반으로 구현.
• 연결 리스트 : 메모리의 동적 할당을 기반으로 구현.
• 원형 연결 리스트 : 리스트의 끝과 시작점이 연결된 리스트.

리스트의 구현 방법은 차이가 있지만, 이들의 추상 자료형이 동일하다고 해서 문제 될 것은 없다. (물론 각각의 특성 때문에 달라질 순 있다.)

 

리스트의 특성은 “자료를 나란히 저장하고 중복을 허용한다.” 이다. 수학적으로 “중복”을 허락하지 않는 집합과는 다르기에 리스트의 추상 자료형을 정의하는 데 있어서 유일하게 고려할 요소이다.

 

■ 배열 기반 리스트 구현

리스트의 특성을 가지고 정의해야할 추상 자료형을 정리해 보자.

중요한 점은 “데이터를 어떻게 나란히 저장할까”에 대해 고민하는 것이 아니라, 나란히 저장되는 특성을 기반으로 제공해야 할 기능들을 정의해야 한다.

정의	기능
void InitList(List* pList)	초기화 할 리스트의 주소 값을 전달. 리스트 생성 후 가장 먼저 호출.
void Insert(List* pList, LData data)	리스트에 데이터를 저장.
bool First(List* pList, LData* data)	리스트의 첫 번째 데이터를 data가 가리키는 메모리에 저장.      →참조 여부에 따라 bool 값 반환.
bool Next(List* pList, LData* data)	참조된 데이터의 다음 데이터가 data가 가리키는 메모리에 저장.      →참조 여부에 따라 bool 값 반환.
LData Remove(List* pList)	LFirst, LNext의 마지막 반환 데이터를 삭제 후 반환.
int Count(List* pList)	리스트에 저장된 데이터 수 반환.

[List 추상 자료형 정의]

위에 정리한 표를 바탕으로 실제 배열 기반 리스트를 만들어보자.

 

1. ArrayList.h

#pragma once
typedef int LData;
constexpr int LEN = 100;

struct ArrayList
{
	LData arr[LEN];
	int count;
	int curPos;
};

typedef ArrayList List;

// 추상 자료형(ADT)
void InitList(List* pList);
void Insert(List* pList, LData data);

bool First(List* pList, LData* data);
bool Next(List* pList, LData* data);

LData Remove(List* pList);
int Count(List* pList);

void PrintAllValue(const List* const pList);

[ArrayList.h]

저장할 데이터를 쉽게 변경하고 순차/연결 리스트를 구분하기 위해 관련 변수를 typedef로 선언하였다.

• 만약 리스트에 float형식을 저장해야 한다면, typedef int LData를 typedef float LData로 변경해 주면 된다.

 

2. ArrayList.cpp

▶ 삽입(Insert)과 조회(First, Next)

void InitList(List* pList)
{
	pList->count = 0;
	pList->curPos = 0;
}

[배열 기반 리스트의 초기화 함수]

ArrayList의 참조 위치, 저장된 데이터 개수를 0으로 초기화한다.

• count에는 저장된 데이터 개수, curPos에는 현재 참조 위치가 저장된다.

 

void Insert(List* pList, LData data)
{
	if(pList->count >= LEN)
	{
		cout << "더 이상 저장할 수 없습니다." << endl;
		return;
	}

	pList->arr[pList->count++] = data;
}

[배열 기반 리스트의 삽입 함수]

데이터를 더 저장할 수 있는지 확인하고, 저장이 가능하다면 배열의 앞부분부터 채워나간다.

 

bool First(List* pList, LData* data)
{
	if (pList->count <= 0)
		return false;

	pList->curPos = 0;
	*data = pList->arr[0];
	return true;
}

[저장된 첫 데이터 확인]

저장된 데이터가 하나도 없다면 false를 반환한다. 반환할 데이터가 있다면 참조 위치를 배열의 첫 번째로 옮긴 뒤 첫 번째 데이터를 반환한다.

• First() 함수는 현재 참조 위치를 배열의 맨 앞으로 옮기게 만든다.

 

bool Next(List* pList, LData* data)
{
	if (pList->curPos >= pList->count - 1)
		return false;

	*data = pList->arr[++pList->curPos];
	return true;
}

[참조된 데이터의 다음 데이터 반환]

Next() 함수는 First() 함수와 달리 현재 참조 위치를 증가시켜 순차적으로 데이터를 참조할 수 있도록 도와준다.

 

▶ 데이터 삭제(Remove)

LData Remove(List* pList)
{
	if (pList->count <= 0)
	{
		cout << "삭제할 데이터가 없습니다." << endl;
		return LData();
	}

	const LData result = pList->arr[pList->curPos];

	for(int i = pList->curPos; i < pList->count - 1; ++i)
	{
		pList->arr[i] = pList->arr[i + 1];
	}

	pList->count--;
	pList->curPos--;

	return result;
}

[참조중인 데이터 삭제]

데이터를 삭제하면 중간에 빈 공간이 생기므로, 뒤에 있던 데이터를 한 칸씩 앞으로 당긴다.

• 삭제된 데이터 이후의 모든 요소를 한 칸씩 앞으로 이동한다.
• 참조 위치를 그대로 두면 아직 참조되지 않은 다음 데이터가 남기 때문에, 한 칸 왼쪽으로 이동시킨다.

 

■ 저장 타입 변경

앞서 우리가 구현할 때는 단순히 정수를 리스트에 저장했지만, 이를 구조체의 주소를 저장하도록 변경해 보자.

#pragma once

struct Point
{
	int x;
	int y;
};

void InitPoint(Point* p, int x, int y);
void PrintPoint(const Point* p);
int Compare(Point* p1, Point* p2);

[Point.h]

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

void InitPoint(Point* p, int x, int y)
{
	p->x = x;
	p->y = y;
}

void PrintPoint(const Point* p)
{
	std::cout << "좌표 : " << '(' << p->x << ", " << p->y << ')' << std::endl;
}

int Compare(Point* p1, Point* p2)
{
	// 두 값이 모두 같으면 0
	if (p1->x == p2->x && p1->y == p2->y)
		return 0;
	// x값이 같으면 1
	if (p1->x == p2->x)
		return 1;
	// y값이 같으면 2
	if (p1->y == p2->y)
		return 2;

	return -1;
}

[Point.cpp]

ArrayList.h에 #include "Point.h"를 추가하고, typedef int LData를 typedef Point LData*로 바꿔주기만 하면 된다.

이제 main에서 구조체를 리스트에 저장하고 조회해 보자.

#include<iostream>
#include "ArrayList.h"
using namespace std;

int main()
{
	List list;
	Point* pp = nullptr;
	Point comparePoint;

	InitList(&list);

	pp = new Point;
	InitPoint(pp, 2, 1);
	Insert(&list, pp);

	pp = new Point;
	InitPoint(pp, 2, 2);
	Insert(&list, pp);

	pp = new Point;
	InitPoint(pp, 3, 1);
	Insert(&list, pp);

	pp = new Point;
	InitPoint(pp, 3, 2);
	Insert(&list, pp);
	
	// 저장 데이터 출력
	cout << "현재 데이터 수 : " << Count(&list) << endl;

	if(First(&list, &pp))
	{
		PrintPoint(pp);

		while(Next(&list, &pp))
			PrintPoint(pp);
	}

	// 데이터 삭제
	comparePoint.x = 2;
	comparePoint.y = 0;

	if(First(&list, &pp))
	{
		// x가 2인 모든 데이터 삭제
		if(Compare(pp, &comparePoint) == 1)
		{
			pp = Remove(&list);
			delete pp;
		}

		while (Next(&list, &pp))
		{
			if (Compare(pp, &comparePoint) == 1)
			{
				pp = Remove(&list);
				delete pp;
			}
		}
	}

	// 삭제 후 저장 데이터 출력
	cout << "현재 데이터 수 : " << Count(&list) << endl;

	if (First(&list, &pp))
	{
		PrintPoint(pp);

		while (Next(&list, &pp))
			PrintPoint(pp);
	}

	return 0;
}

[Main.cpp]

List에 저장되는 형식을 Point* 타입으로 변경하여도 별다른 구현부의 수정 없이 정상적으로 동작하는 것을 확인할 수 있다.

 

조회 함수(First, Next)의 매개변수는 LData* data이며, LData가 Point*로 정의되어 있으므로 실제 타입은 Point**가 된다. 즉, 조회 함수는 Point*(포인터)를 가리키는 포인터를 인자로 받는다.

 

따라서, 함수 호출 시에는 Point*변수(pp)의 주소인 &pp를 인자로 전달해야 함수 내부에서 *data = … 을 통해 pp가 가리키는 대상을 변경할 수 있다.

 

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

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

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