ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • 순차 자료구조 - 선형 리스트(ArrayList)
      프로그래밍 기초/자료구조 2020. 10. 2. 12:49

        순차 자료구조와 선형 리스트 

      순차 자료구조

      데이터를 순서대로 저장하고 인덱스를 부여하여 관리하는 자료구조를 말한다. 배열을 이용해 리스트를 구현한 선형 리스트(또는 ArrayList)를 포함한다.

       

      선형 리스트

      데이터가 메모리에 물리적으로 연속적으로 저장되기 때문에 리스트 중간에서 데이터를 삽입하거나 삭제하는 연산을 하는 경우 데이터를 옮긴 후 연산을 처리해야 하는 오버헤드가 발생한다.

       

      - 삽입(Insert) 연산

      기본적으로 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
      데이터 10 20 30 40 40
      인덱스 0 1 2 3 4
      데이터 10 20 30 30 40
      인덱스 0 1 2 3 4
      데이터 10 20 50 30 40

       

      삽입 시도 시 빈 공간이 없는 경우 저장 공간을 두배로 늘려준 뒤 삽입한다.

      인덱스 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!

       

      - 삭제(Delete) 연산

      데이터 삭제의 경우 빈 공간이 늘어나도 공간을 축소하지 않는다.

       

      예를 들어 기존에 공간(Capacity)이 5인 ArrayList에 삽입 연산을 통해 공간이 10으로 증가했을 때, 다시 데이터를 삭제한다고 해서 공간을 5로 줄이지는 않는다.

       

      리스트 끝의 데이터를 삭제하는 경우 데이터를 바로 삭제한다.

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

       

      리스트 중간에 데이터를 삭제하는 경우 해당 데이터 삭제 후 빈 공간이 없어질 때까지 데이터를 옮겨준다.

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

       

      ※ 데이터를 옮길 때 기존 값은 제거하지 않는다.

       

        선형 리스트 구현 

      선형 리스트의 이해를 기반으로 C#의 ArrayList를 간략화하여 int만 저장할 수 있는 ArrayList를 만든다.

       

      구현이 필요한 메서드 및 속성은 다음과 같다.

      • 생성자
        • ArrayList() 비어있고 기본 초기 용량을 가지는 인스턴스 생성
        • ArrayList(ArrayList&) 다른 ArrayList의 데이터로 인스턴스 생성
        • ArrayList(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성
      • 속성 
        • Capacity 저장될 수 있는 총 크기
        • Count 실제 사용되고 있는 크기
        • Item[int] 저장된 데이터의 접근 및 설정
      • 메서드 
        • Add(data) 마지막 위치에 데이터 삽입
        • AddRange(ArrayList&) 마지막 위치에 다른 ArrayList의 데이터를 모두 삽입
        • Insert(int, data) 지정된 위치에 데이터 삽입
        • InsertRange(int, ArrayList&) 지정된 위치에 다른 ArrayList의 모든 데이터를 삽입
        • Remove(data) 가장 처음 일치한 data 삭제
        • RemoveAt(int) 지정한 위치의 데이터 삭제
        • RemoveRange(int, int) 지정한 범위의 데이터 삭제
        • Clear() 저장되어 있는 모든 데이터 삭제
        • Contains(data) 데이터가 저장되어 있는지 여부 확인
        • IndexOf(data) 가장 처음 일치한 데이터의 인덱스 반환
        • LastIndexOf(data) 가장 마지막 일치한 데이터의 인덱스 반환

       

      ArrayList 클래스 선언 및 속성 구현

      속성(Property)은 C++에서 지원하지 않으므로 메서드 호출 시 레퍼런스를 넘기는 방식으로 구현한다.

       

      ArrayList.h

      #pragma once
#include <xutility>
#include <iostream>

class ArrayList
{
public:
#pragma region 생성자
	ArrayList(int capacity = 10);
	ArrayList(const ArrayList& other);
	~ArrayList();
#pragma endregion

#pragma region 속성
	const int Capacity() { return m_capacity; }
	const int Count() { return m_count; }
	int& Item(int index) { 
		if (index < 0 || index >= m_count)
		{
			throw std::out_of_range("index");
		}
		return m_items[index];
	}
#pragma endregion

#pragma region 메서드
	int Add(int value);
	void AddRange(const ArrayList& other);
	void Insert(int index, int value);
	void InsertRange(int index, const ArrayList& other);

	void Remove(int value);
	void RemoveAt(int index);
	void RemoveRange(int index, int count);
	void Clear();

	bool Contains(int value);
	int IndexOf(int value);
	int LastIndexOf(int value);
#pragma endregion

private:
#pragma region Class Util
	bool IsNeedToResize(int insertCount = 1);
	void Resize();
	void MoveToRight(int index, int insertCount = 1);
	void MoveToLeft(int index, int removeCount = 1);
#pragma endregion

#pragma region 변수
	size_t m_capacity;
	size_t m_count;
	int* m_items;
#pragma endregion
};

       

      생성자/소멸자 구현

      사이즈를 인자로 받는 생성자와 ArrayList를 인자로 받는 복사 생성자를 구현한다.

       

      ArrayList.cpp

      /// <summary>
/// 비어있고 초기 용량을 가지는 ArrayList를 생성한다.
/// </summary>
/// <param name="capacity">생성할 공간의 크기(기본: 10)</param>
ArrayList::ArrayList(int capacity)
	: m_capacity(capacity), m_count(0)
{
	if (capacity < 0)
	{
		throw std::out_of_range("capacity");
	}
	m_items = new int[m_capacity] {0};
}

/// <summary>
/// 다른 ArrayList와 동일한 값을 가지는 ArrayList를 생성한다.
/// </summary>
/// <param name="other">기준이 될 ArrayList</param>
ArrayList::ArrayList(const ArrayList& other)
	: ArrayList(other.m_capacity)
{
	m_count = other.m_count;
	for (int i = 0; i < m_capacity; i++)
	{
		m_items[i] = other.m_items[i];
	}
}

/// <summary>
/// 메모리 누수를 막기 위해 동적 생성한 데이터 영역을 제거한다.
/// </summary>
ArrayList::~ArrayList()
{
	if (m_items != nullptr)
	{
		delete[] m_items;
	}
}

       

      데이터 삽입 메서드 구현

      데이터 삽입 연산에 필요한 메서드들을 구현한다.

       

      ArrayList.cpp

      /// <summary>
/// ArrayList의 끝에 값을 추가한다.
/// </summary>
/// <param name="value">추가할 값</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</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 < 0 || index > m_count)
	{
		throw std::out_of_range("index");
	}

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

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

/// <summary>
/// ArrayList의 지정된 인덱스에 다른 ArrayList를 추가한다.
/// </summary>
/// <param name="index">다른 ArrayList를 추가할 인덱스</param>
/// <param name="other">추가할 다른 ArrayList</param>
void ArrayList::InsertRange(int index, const ArrayList& other)
{
	if (index < 0 || 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];
	}
}

/// <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];
	}
	m_count += insertCount;
}

       

      데이터 삭제 메서드 구현

      데이터 삭제 연산에 필요한 메서드를 구현한다.

       

      ArrayList.cpp

      /// <summary>
/// ArrayList에서 가장 먼저 발견되는 값을 제거한다.
/// </summary>
/// <param name="value">제거할 값</param>
void ArrayList::Remove(int value)
{
	int index = IndexOf(value);
	if (index != -1)
	{
		MoveToLeft(index);
	}
}

/// <summary>
/// ArrayList에서 지정된 인덱스의 값을 제거한다.
/// </summary>
/// <param name="index">제거할 인덱스(조건: 0이상)</param>
void ArrayList::RemoveAt(int index)
{
	if (index < 0 || index >= m_count)
	{
		throw std::out_of_range("index");
	}

	MoveToLeft(index);
}

/// <summary>
/// ArrayList에서 지정된 범위의 값을 제거한다.
/// </summary>
/// <param name="index">제거할 범위의 시작 인덱스</param>
/// <param name="count">제거할 값 개수</param>
void ArrayList::RemoveRange(int index, int count)
{
	if (index < 0)
	{
		throw std::out_of_range("index");
	}
	else if (count < 0)
	{
		throw std::out_of_range("count");
	}

	if (index >= m_count)
	{
		throw std::invalid_argument("index");
	}
	else if (count > m_count - index)
	{
		throw std::invalid_argument("count");
	}

	MoveToLeft(index, count);
}

/// <summary>
/// ArrayList의 모든 값을 제거한다.
/// </summary>
void ArrayList::Clear()
{
	m_count = 0;
}

/// <summary>
/// 제거 이후 빈 공간 제거를 위해 값을 왼쪽으로 이동시킨다.
/// </summary>
/// <param name="index">데이터를 삭제할 인덱스</param>
/// <param name="removeCount">삭제할 값의 개수(기본: 1)</param>
void ArrayList::MoveToLeft(int index, int removeCount)
{
	for (int i = index; i < m_count - removeCount; i++)
	{
		m_items[i] = m_items[i + removeCount];
	}
	m_count -= removeCount;
}

       

      기능 메소드 구현

      자료구조를 효율적으로 사용하기 위한 기능 메서드를 구현한다.

       

      ArrayList.cpp

      /// <summary>
/// ArrayList에 지정한 값이 존재하는지 확인한다.
/// </summary>
/// <param name="value">ArrayList에서 찾을 값</param>
/// <returns>값의 존재 여부</returns>
bool ArrayList::Contains(int value)
{
	return IndexOf(value) != -1;
}

/// <summary>
/// ArryList을 앞에서 부터 지정한 값을 검사해 인덱스를 반환한다.
/// </summary>
/// <param name="value">찾을 값</param>
/// <returns>값의 인덱스(없으면 -1)</returns>
int ArrayList::IndexOf(int value)
{
	for (int i = 0; i < m_count; i++)
	{
		if (m_items[i] == value)
		{
			return i;
		}
	}
	return -1;
}

/// <summary>
/// ArryList을 뒤에서 부터 지정한 값을 검사해 인덱스를 반환한다.
/// </summary>
/// <param name="value">찾을 값</param>
/// <returns>값의 인덱스(없으면 -1)</returns>
int ArrayList::LastIndexOf(int value)
{
	for (int i = m_count - 1; i >= 0; i--)
	{
		if (m_items[i] == value)
		{
			return i;
		}
	}
	return -1;
}

       

      저작자표시 비영리 변경금지

      관련글 관련글 더보기

      댓글

    Designed by Tistory.

    티스토리툴바