자료구조...5

선형 리스트 구현

선형 리스트의 이해를 기반으로 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) data가 저장되어 있는지 여부 확인
  • IndexOf(data) 가장 처음 일치한 data의 인덱스 리턴
  • LastIndexOf(data) 가장 마지막 일치한 data 인덱스 리턴

 

ArrayList.h

실제 구현에서 속성(Property)은 C++에서 지원하지 않기 때문에 적당히 get, set 함수로 치환해 구현한다.

#pragma once

class ArrayList
{
public:
	// 생성자
	ArrayList();
	ArrayList(ArrayList& other);
	ArrayList(int capacity);

	// 속성
	const size_t Capacity() { return m_capacity; }
	const size_t Count() { return m_count; }
	int& Item(int index) { return m_items[index]; }

	// 메서드
	int Add(int value);
	void AddRange(ArrayList& other);
	void Insert(int index, int value);
	void InsertRange(int index, 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);

private:
	size_t m_capacity;
	size_t m_count;
	int* m_items;
};

 

참고문헌

Microsoft MSDN.ArrayList 클래스 (System.Collections)