[자료구조] 배열로 만든 리스트

배열로 만든 리스트

• 구현이 간단하다.
• 삽입, 삭제 시 오버헤드 문제 발생
• 항목의 개수가 제한적

 

구조체 구현

#define MAX_SIZE 10
using namespace std;
typedef int element;

typedef struct {
	int length; // 저장된 개수
	element list[MAX_SIZE];
}ArrayListType;

 

초기화 함수

void init(ArrayListType* L)
{
	L->length = 0;
}

 

is_empty 함수

bool is_empty(ArrayListType* L)
{
	if (L->length == 0)
		return true;
	return false;
}

 

is_full 함수

bool is_full(ArrayListType* L)
{
	if (L->length == MAX_SIZE)
		return true;
	return false;
}

 

Add 함수

void Add(ArrayListType* L, int pos, element item)
{
	if (!is_full(L) && pos <= L->length
		&& pos >= 0)
	{
		for (int i = L->length - 1; i >= pos; i--) // 한칸씩 오른쪽으로 옮기는 과정
			L->list[i + 1] = L->list[i];

		L->list[pos] = item; // 내가 원하는 위치에 삽입
		L->length++;
	}

}

리스트가 꽉 차지 않았고, 삽입할 위치가 현재 리스트에 포함된 요소 개수보다 작거나 같아야 합니다.

pos가 length보다 작을 경우 중간에 삽입하는 경우이며

pos가 length랑 같을 경우 리스트 맨 끝에 삽입을 해주는 경우이다.

원하는 위치에 삽입을 하기 위해 그 위치부터 오른쪽 끝까지의 원소들을 한 칸씩 오른쪽으로 옮겨주어야 한다.

 

Delete 함수 

element Delete(ArrayListType* L, int pos)
{
	if (pos < 0 || pos >= L->length)
	{
		cout << "범위 에러";
		return -1;
	}

	element item = L->list[pos];
	for (int i = pos; i < L->length - 1; i++) // 삭제위치의 오른쪽 원소들 왼쪽으로 한칸씩 이동
		L->list[i] = L->list[i + 1];
	L->length--;
	return item;
}

범위 에러의 경우 pos가 음수이거나

삭제할 인덱스(위치)가 현재 원소의 개수보다 클 경우 원소가 존재도 안하는 경우니 에러이다.

pos 위치에 원소를 삭제한 경우, 그 위치의 공백이 생기니

오른쪽의 원소들을 다들 왼쪽으로 한칸씩 땡겨 앉으면 된다.

 

전체 코드

#include <iostream>
#define MAX_SIZE 10
using namespace std;
typedef int element;

typedef struct {
	int length; // 저장된 개수
	element list[MAX_SIZE];
}ArrayListType;

void init(ArrayListType* L)
{
	L->length = 0;
}

bool is_empty(ArrayListType* L)
{
	if (L->length == 0)
		return true;
	return false;
}

bool is_full(ArrayListType* L)
{
	if (L->length == MAX_SIZE)
		return true;
	return false;
}

void Add(ArrayListType* L, int pos, element item)
{
	if (!is_full(L) && pos <= L->length
		&& pos >= 0)
	{
		for (int i = L->length - 1; i >= pos; i--)
			L->list[i + 1] = L->list[i];

		L->list[pos] = item;
		L->length++;
	}

}

element Delete(ArrayListType* L, int pos)
{
	if (pos < 0 || pos >= L->length)
	{
		cout << "범위 에러";
		return -1;
	}

	element item = L->list[pos];
	for (int i = pos; i < L->length - 1; i++)
		L->list[i] = L->list[i + 1];
	L->length--;
	return item;
}

int main(void)
{
	ArrayListType arrlist;
	init(&arrlist);
}