자료구조...7

ArrayList 데이터 삽입 메소드 구현

기본적으로 ArrayList는 데이터를 삽입할 수 있는 공간(Capacity)이 정해져 있다. 그렇기에 기본적으로 데이터를 삽입하면 빈 공간에 데이터를 삽입하는 형태가 된다.

 

- 원본 데이터

인덱스	0	1	2	3	4
데이터	10	20	30	40

 

- 데이터 삽입 시 빈 공간 있는 경우

인덱스	0	1	2	3	4
데이터	10	20	30	40	50

 

데이터 삽입 메소드가 호출되었는데 빈 공간이 없는 경우에는 데이터를 저장할 공간을 두배로 늘리고 기존 데이터를 옮긴 후 데이터를 삽입하게 된다.

 

- 삽입 시도 시 데이터 부족한 경우

인덱스	0	1	2	3	4	5	6	7	8	9
데이터	10	20	30	40	50	new!	new!	new!	new!	new!

인덱스	0	1	2	3	4	5	6	7	8	9
데이터	10	20	30	40	50	60	new!	new!	new!	new!

 

ArrayList.cpp

/// <summary>
/// ArrayList의 끝에 값을 추가한다.
/// </summary>
/// <param name="value">ArrayList 끝에 추가할 값</param>
/// <returns>값이 추가된 인덱스</returns>
int ArrayList::Add(int value)
{
	if (IsNeedToResize())
	{
		Resize();
	}
	m_items[m_count] = value;

	return m_count++;
}

/// <summary>
/// ArrayList의 끝에 다른 ArrayList를 추가한다.
/// </summary>
/// <param name="other">ArrayList 끝에 추가할 다른 ArrayList</param>
void ArrayList::AddRange(const ArrayList& other)
{
	while (IsNeedToResize(other.m_count))
	{
		Resize();
	}

	for (int i = 0; i < other.m_count; i++)
	{
		m_items[m_count++] = other.m_items[i];
	}
}

/// <summary>
/// ArrayList의 지정된 인덱스에 값을 추가한다.
/// </summary>
/// <param name="index">값을 추가할 인덱스</param>
/// <param name="value">추가할 값</param>
void ArrayList::Insert(int index, int value)
{
	if (index > m_count)
	{
		throw std::out_of_range("index");
	}

	if (IsNeedToResize())
	{
		Resize();
	}

	MoveToRight(index);
	m_items[index] = value;
	m_count++;
}

/// <summary>
/// ArrayList의 지정된 인덱스에 다른 ArrayList를 추가한다.
/// </summary>
/// <param name="index">다른 ArrayList를 추가할 인덱스</param>
/// <param name="other">추가할 다른 ArrayList</param>
void ArrayList::InsertRange(int index, const ArrayList& other)
{
	if (index > m_count)
	{
		throw std::out_of_range("index");
	}

	while (IsNeedToResize(other.m_count))
	{
		Resize();
	}

	MoveToRight(index, other.m_count);
	for (int i = 0; i < other.m_count; i++)
	{
		m_items[index + i] = other.m_items[i];
	}
	m_count += other.m_count;
}

/// <summary>
/// ArrayList에 count만큼의 값을 삽입할 수 있는지 확인한다.
/// </summary>
/// <param name="count">삽입할 값의 개수(기본: 1)</param>
/// <returns>삽입 가능 여부</returns>
bool ArrayList::IsNeedToResize(int insertCount)
{
	return m_capacity < m_count + insertCount;
}

/// <summary>
/// 데이터 삽입 시 공간이 부족한 경우 공간을 2배로 늘려준다.
/// </summary>
void ArrayList::Resize()
{
	int* newItems = new int[m_capacity * 2]{ 0 };
	for (int i = 0; i < m_capacity; i++)
	{
		newItems[i] = m_items[i];
	}
	m_capacity *= 2;

	delete[] m_items;
	m_items = newItems;
}

/// <summary>
/// 삽입을 위한 공간 확보를 위해 기존 값을 오른쪽으로 이동시킨다.
/// </summary>
/// <param name="index">데이터를 삽입할 인덱스</param>
/// <param name="insertCount">삽입할 값의 개수(기본: 1)</param>
void ArrayList::MoveToRight(int index, int insertCount)
{
	for (int i = m_count - 1; i >= index; i--)
	{
		m_items[i + insertCount] = m_items[i];
	}
}