C로 만드는 자료구조-배열 리스트

배열 리스트(Array List)란?

배열 리스트는 c 언어에서 사용되는 배열을 통해 구현한 리스트를 말한다. 배열을 구성하는 원소,자료 들이 순서대로 연속하여 메모리에 저장된다. 즉 배열 리스트에서 논리적 순서와 물리적 순서는 같다고 할 수 있다.

 위 그림에서 (1)에서 정수형 원소 1,2,3,4가 차례대로 저장되었음을 알 수 있고 (2)를 통해 실제 메모리상에서도 4개의 원소가 차례대로 저장되어 있으므로 논리적인 순서와 물리적인 순서가 같음을 알 수 있다. 또한 (2)를 통해 저장할 수 있는 원소는 최대 6개이고 현재 4개가 저장되어 있음을 알 수 있다.

배열 리스트의 원소 추가

배열 리스트의 기본적인 연산중 하나인 원소 추가 연산을 구현을 어떻게 해야할지 생각을 해보자.
그냥 리스트의 맨 뒤에 원소를 추가하고 싶다면 그냥 추가하면 되지만 만약 리스트의 중간자리에 원소를 추가하게 된다면 추가하려는 위치 뒤에 있는 자료들은  한칸 씩 뒤로 이동시킨 후에 새로운 원소를 추가해야 한다.
그림을 통해 알아보자

 위 그림과 같이 인덱스 2에 새로운 원소 5를 추가하기 위해 기존 원소들을  한칸씩 이동시켜 인덱스 2를 빈공간으로 만들어 준뒤 새로운 원소5를 추가해주었다. 기존 원소들을 이동할 때는 가장 오른쪽 원소부터 시작해서 왼쪽으로 차례대로 이동시켜준다. 만약 왼쪽부터 시작한다면 원소가 겹치는 경우가 발생하기 때문이다.

배열 리스트에서 원소 제거

 배열 리스트에서 중간에 있는 원소를 제거하면 중간에 발생한 공백을 지우기 위해서 뒤에 있는 원소들이 한칸씩 앞으로 이동해야한다. 그림을 통해 알아보자

 위 그림과 같이 인덱스 2에 있는 원소 2를 제거하면 빈자리를 채우기 위해 인덱스 2 뒤에 있는 원소들이 앞으로 한칸씩 이동시켜주면된다. 이때 원소 추가때와는 반대로 왼쪽부터 오른쪽으로 차례대로 이동시킨다.

배열 리스트 구현

소스 파일 구성은 다음과 같다.

파일 이름	내용
arraylist.h	구조체 및 함수 선언
arraylist.cpp	함수 구현
ArrayListMain.cpp	main 함수 실행

1.arraylist.h

#pragma once
#include "stdafx.h"
#include<iostream>
#include<string>
#define TRUE 1
#define FALSE 0
using namespace std;

typedef struct ArrayListNode {
	int data;
};

typedef struct ArrayList {
	int maxLength;
	int currentLength;
	ArrayListNode *pElement;
};
ArrayList* createArrayList(int _max);
int isArrayListFull(ArrayList *pList);
int addElement(ArrayList* pList,int position, ArrayListNode element);
int removeElement(ArrayList* pList, int position);
ArrayListNode* getElement(ArrayList* pList, int position);
void displayArrayList(ArrayList* pList);
void deleteArrayList(ArrayList* pList);
int getArrayListLength(ArrayList* pList);

- ArrayListNode는 배열 리스트에 저장될 원소를 나타내고 원소 값 data를 포함하고 있다. 원소 저장을 위해 별도의 구조체를 따로 만드는 이유는 다양한 자료형을 사용할 수 있게해 범용성을 높이기 위함이다.
- ArrayList는 리스트의 최대 길이(저장가능한 원소 개수) maxLength, 현재 저장된 원소의 길이(현재 저장된 원소의 개수) currentLength, 실제로 데이터들을 저장하는 배열인 pElement로 구성되어 있다. 
추가적으로 #define을 이용해 TURE은 1,FALSE는 0값으로 정의 해주었다.

함수들은 함수 구현 부분에서 자세히 설명하겠다.

2.arraylist.cpp

- createArrayList()

ArrayList* createArrayList(int max) {
	ArrayList *pReturn = NULL;

	if (max > 0) {
		pReturn = new ArrayList;
		pReturn->maxLength = max;
		pReturn->currentLength = 0;
		pReturn->pElement = NULL;
	}
	else {
		cout << "오류, 최대 원소 개수는 0이상 이어야 합니다" << endl;
		pReturn->pElement = NULL;
	}

	pReturn->pElement = new ArrayListNode[max];
	return pReturn;
}

 먼저 최대 저장 가능 원소 개수가 0보다 큰지 확인 후 0보다 크다면 ArrayList에대한 메모리를 할당 후 마지막으로 원소를 저장하는 배열 pElement에도 max만큼 메모리를 할당 해준다.

-addElement()

int addElement(ArrayList* pList,int position, ArrayListNode element) {
	int ret = FALSE;
	if (pList != NULL) {
		if (isArrayListFull(pList) != TRUE) {
			if (position >= 0 && position <= pList->currentLength) {
				for (int i = pList->currentLength - 1; i >= position; i--)
					pList->pElement[i + 1] = pList->pElement[i];
				pList->pElement[position] = element;
				pList->currentLength++;
				ret = TRUE;
			}
			else {
				cout << "오류, 위치 인덱스 --" << position << "범위초과" << endl;
			}

		}
		else {
			cout << "오류, 리스트 용량 초과--" << position << "/" << pList->maxLength << endl;
		}
	}
	return ret;
}

 먼저 pList값이 NULL값이 아닌지를 체크하고 배열에 공간이 남아 있는지(line 4),새로운 원소를 추가할 자리가 적합한지를 순서대로 체크해준다(line 5), 그후 for 반복문을 이용하여 가장 오른쪽에 있는 원소부터 새로 추가할 자리까지 왼쪽으로 차례대로 원소를 뒤로 이동시켜준다(line 6~7). 원소를 다 이동 시킨후 원소를 추가하고 성공하면 TRUE를 반환한다.

-removeElement()

int removeElement(ArrayList* pList,int position) {
	int ret = FALSE;
	if (pList != NULL) {
		if (position >= 0 && position < pList->currentLength) {
			for (int i = position; i < pList->currentLength - 1; i++)
				pList->pElement[i] = pList->pElement[i + 1];
			pList->currentLength--;
			ret = TRUE;
		}
		else {
			cout << "오류, 위치 인덱스--" << position << "범위 초과" << endl;
		}
	}
	return ret;
}

 addElement()와 마찬가지로 먼저 pList값이 NULL값이 아닌지를 체크하고 배열에 공간이 남아 있는지(line 3),제거하고 싶은 원소의 자리가 제거하기 적합한지를 순서대로 체크해준다(line 4), 그 후 for문을 이용해 제거할 인덱스 다음 자리부터 오른쪽으로 차례대로 앞으로 한칸씩 이동시킨다. 성공후 TRUE를 반환한다.

-나머지 함수들

void deleteArrayList(ArrayList* pList) {
	if (pList != NULL) {
		delete[] pList->pElement;
		delete pList;
	}
}

int isArrayListFull(ArrayList *pList) {
	int ret = FALSE;
	if (pList != NULL) {
		if (pList->maxLength== pList->currentLength)
			ret = TRUE;
	}
	return ret;
}

void displayArrayList(ArrayList* pList) {
	if (pList != NULL) {
		cout << "최대 원소 개수: " << pList->maxLength << endl;
		cout << "현재 원소 개수: " << pList->currentLength << endl;
		for (int i = 0; i < pList->currentLength; i++)
			cout << "[" << getElement(pList,i)->data << "]" << "\t";
	}
	else {
		cout << "ArryList is NULL" << endl;
	}
    cout<<endl;
}

int getArrayListLength(ArrayList* pList) {
	int ret = 0;
	if (pList != NULL) {
		ret = pList->currentLength;
	}
	return ret;
}

ArrayListNode* getElement(ArrayList* pList,int position) {
	ArrayListNode* pReturn = NULL;
	if (pList != NULL) {
		if (position >= 0 && position < pList->currentLength) {
			pReturn = &(pList->pElement[position]);
		}
		else {
			cout << "오류, 위치 인덱스--" << position << "범위 초과" << endl;
		}
	}
	return pReturn;
}

- deleteArrayList()는 리스트를 제거하는 함수이다. delete를 이용해 메모리를 해제 해준다.
-IsArrayListFull()은 리스트 저장 공간이 꽉 찼는지 아닌지 판단해주는 함수이다. 공간이 있으면 FALSE 공간이 없으면 TRUE를 반환한다.
- displayArrayList() 는 현재 리스트의 상태를 출력한다.
-getArrayListLength()는 현재 저장된 원소의 개수를 반환 한다.
-getElement()는 입력받은 위치 인덱스에 존재하는 원소를 반환한다.

3.ArrayListMain.cpp

#include "stdafx.h"
#include<iostream>
#include"arraylist.h"
int main() {
	int arrayCount = 0;
	ArrayList *pList = NULL;
	ArrayListNode node;


	pList = createArrayList(6);
	if (pList != NULL) {
		node.data = 1;
		addElement(pList, 0, node);

		node.data = 2;
		addElement(pList, 1, node);
		
		node.data = 3;
		addElement(pList, 2, node);
		
		node.data = 4;
		addElement(pList, 3, node);
		
		displayArrayList(pList);
		removeElement(pList, 1);
		displayArrayList(pList);

		ArrayListNode* pNode=NULL;
		pNode = getElement(pList, 1);

		deleteArrayList(pList);

	}

}

실행결과

※배열 리스트의 한계 

 만약 원소의 개수가 엄청나게 많고 그 중간 인덱스에 원소를 추가/제거 한다고 생각을 해보자 원소 하나를 추가/제거하기 위해서 엄청나게 많은 연산이 필요할 것이다. 만약 1000,000개의 원소를 가지고 있는 리스트에서 첫 번째 원소를 제거한다면 999,999번 원소를 이동 시켜야 한다. 따라서 리스트에 저장된 원소의 개수가 많고 원소를 추가/제거 하는 일이 빈번 하다면 상당히 비효율적이다.