[자료구조] ArrayList

분류:

• 선형 자료구조
• 동적 배열 기반 자료구조

특징:

• 내부적으로 배열을 사용하여 요소를 저장
• 크기가 동적으로 조절됨 (자동으로 크기가 증가하거나 감소)
• 인덱스를 통한 랜덤 접근이 가능 (O(1) 시간 복잡도)
• 요소 추가 시 평균적으로 O(1) 시간 복잡도, 최악의 경우 O(n)
• 중간에 요소를 삽입하거나 삭제할 경우 O(n) 시간 복잡도
• 메모리 상에서 연속적으로 위치
• 용량(Capacity)과 크기(Size) 개념이 분리되어 있음
• 배열의 크기를 늘릴 때 일반적으로 현재 크기의 1.5배 또는 2배로 증가

사용처:

• 요소의 개수가 가변적인 목록을 다룰 때
• 빈번한 조회 작업이 필요한 경우
• 데이터의 인덱스 기반 접근이 많은 경우
• 주로 읽기 작업이 많고, 삽입/삭제가 끝부분에서 주로 일어나는 경우
• 데이터베이스의 결과셋 처리
• GUI 컴포넌트의 아이템 관리 (예: 리스트 뷰)
• 캐시 구현
• 스택이나 큐의 기본 구조로 사용

#pragma once
template<typename T>
class ArrayList
{
private:
	T*		_data;			 // 데이터 버퍼
	int     _size;			// 사이즈
	int     _capaicty;		// 용량

public:
	// 생성자
	ArrayList() : _size(0), _capaicty(0), _data(nullptr)
	{
			
	}

	// 소멸자
	~ArrayList() 
	{
		if (_data)
			delete[] _data;
	}

public:
	// 데이터 버퍼가 가득차면 새로운 메모리를 할당 받는다.
	void Reserve(int newCapacity)
	{
		// 새로운 메모리를 할당 받는다.
		T* newData = new T[newCapacity];
		// 이전 데이터 복사
		::memcpy(newData, _data, sizeof(T)  * _capaicty);
		// 이전 메모리 할당 해제
		if (_data)
			delete[] _data;
		// 새로운 버퍼를 가리키도록 설정
		_data = newData;
		// 용량 갱신
		_capaicty = newCapacity;
	}

	// 데이터 추가
	void PushBack(const T& data)
	{
		// size + 1
		int newSize = _size + 1;
		// 만약 데이터를 추가했는데 용량을 초과한다면...?
		if (_capaicty < newSize)
		{
			// 새로운 메모리 할당
			Reserve(newSize * 1.5);
		}
		// 데이터 추가
		_data[_size] = data;
		// 사이즈 갱신
		_size = newSize;
	}

	// 데이터 삭제
	void PopBack()
	{
		if (Empty())
		{
			throw std::runtime_error("ArrayList is Empty");
		}
		// 사이즈 갱신
		_size--;
	}

	// 사이즈 확인
	int Size()
	{
		return _size;
	}

	// 배열이 비었는지 확인
	bool Empty()
	{
		return _size == 0;
	}

	// index 접근
	const T& Get(int index)
	{
		return _data[index];
	}
};

#include "pch.h"
#include "ArrayList.h"
int main() 
{
	ArrayList<int> li;

	for (int i = 0; i < 10; i++)
		li.PushBack(i);

	for (int i = 0; i < 10; i++)
		std::cout << li.Get(i) << std::endl;

	while (!li.Empty())
	{
		li.PopBack();
	}

	std::cout << "Size:" << li.Size() << std::endl;

	return 0;
}

 

실행 결과

 

구현 중요 포인트

arrayList는 동적배열로서, 배열을 선언할때 별도로 size를 할당하지않습니다. 
그 이유는 데이터가 추가될때 자동으로 capacity가 증가하기 때문입니다.
arrayList의 구현의 핵심은 데이터가 추가될때 capacity를 늘려주는 것 입니다.
해당 방식을 구현하면 이렇습니다.