Re-Invent the Wheel ! 배열 리스트 ArrayList

01. 배열 리스트

- 메모리의 연속된 공간에 존재하는 선형 자료구조

- 원소들 간의 일대일 대응관계가 성립하며, 연속적인 구조를 가짐

- 배열의 중간에 원소의 삽입이나 삭제시 도미노 형태로 원소의 이동이 많아 느리다.

- 원소 탐색시 한 번에 접근 가능하므로 빠르다.

02. ADT(추상 자료형)

이름	입력	반환	설명
ArrayList()	int cap = 0	-	capacity가 cap인 배열리스트 생성자
push_back()	T data	bool 성공여부	끝에 원소 넣기
insert()	int index, T data	bool 성공여부	지정 위치에 원소 삽입
operator[] () const	int index	T	조회용 인덱스 연산자
operator[] ()	int index	T&	조회 및 수정용 인덱스 연산자
length() const	-	int	현재 배열리스트의 길이를 반환
capacity() const	-	int	배열리스트의 cap을 반환
remove()	int index	bool 성공여부	지정 위치의 원소 삭제
clear()	-	-	베열리스트 초기화
~ArrayList()	-	-	소멸자

03. 구현

* ArrayList.h

#ifndef __ARRAY_LIST_H__
#define __ARRAY_LIST_H__

#include <iostream>
using namespace std;

template<typename T>
class ArrayList
{
private:
    T* arr;
    int cap;
    int arrlen;
public:
    ArrayList(int cap = 10);
    bool push_back(T data);
    bool insert(int index, T data);
    T operator[] (int index) const;
    T& operator[] (int index);
    int length() const;
    int capacity() const;
    bool remove(int index);
    void clear();
    ~ArrayList();
    friend ostream& operator<< (ostream& os, const ArrayList<int>& arrayList);
};

template <typename T>
ArrayList<T>::ArrayList(int cap) 
    : cap(cap), arrlen(0) {
    this->arr = new T[cap];
}

template <typename T>
bool ArrayList<T>:: push_back(T data) {
    if(this->arrlen >= this->cap) {
        cout << "push_back : ArrayList is full" << endl;
        return false;
    }

    this->arr[this->arrlen++] = data;
    return true;
}

template <typename T>
bool ArrayList<T>::insert(int index, T data) {
    if(index >= this->cap || index < 0) {
        cout << "insert : index out of range." << endl;
        return false;
    }
    else if (index > this->arrlen) {
        cout << "insert : position of last possible index is "
            << this->arrlen << endl;
        return false;
    }
    else if (this->arrlen == this->cap) {
        cout << "insert : ArrayList is full" << endl;
        return false;
    }

    for(int i=arrlen-1; i>=index; --i)
        this->arr[i+1] = this->arr[i];
    this->arr[index] = data;
    this->arrlen++;
    return true;
}

template <typename T>
T ArrayList<T>::operator[] (int index) const {
    if(index >= cap || index < 0) {
        cout << "operator[] : index out of range" << endl;
        exit(1);
    }
    else if (index >= arrlen) {
        cout << "operator[] : empty space" << endl;
        exit(1);
    }

    return this->arr[index];
}

template <typename T>
T& ArrayList<T>::operator[] (int index) {
    if(index >= cap || index < 0) {
        cout << "operator[] : index out of range" << endl;
        exit(1);
    }
    else if (index >= arrlen) {
        cout << "operator[] : empty space" << endl;
        exit(1);
    }

    return this->arr[index];
}

template <typename T>
int ArrayList<T>::length() const {
    return this->arrlen;
}

template <typename T>
int ArrayList<T>::capacity() const {
    return this->cap;
}

template <typename T>
bool ArrayList<T>::remove(int index) {
    if(index >= this->cap || index < 0) {
        cout << "delete : index out of range." << endl;
        return false;
    }
    else if(index >= this->arrlen) {
        cout << "delete : empty space" << endl;
        return false;
    }
    else if(index == this->arrlen-1) {
        --this->arrlen;
        return true;
    }

    for(int i=index; i<this->arrlen; ++i)
        this->arr[i] = this->arr[i+1];
    --this->arrlen;
    return true;
}

template <typename T>
void ArrayList<T>::clear() {
    this->arrlen = 0;
}

template <typename T>
ArrayList<T>::~ArrayList() {
    delete []this->arr;
}

ostream& operator<< (ostream& os, const ArrayList<int>& arrayList) {
    cout << '{';
    for(int i=0; i<arrayList.arrlen; ++i) {
        cout << arrayList.arr[i];
        if(i != arrayList.arrlen-1)
            cout << ", ";
    }
    cout << '}';

    return os;
}

#endif

04. 적용

* main.cpp

#include "ArrayList.h"

int main(void)
{
    ArrayList<int> myList(5);
    cout << "1->" << myList << endl;

    myList.push_back(10);
    myList.push_back(20);
    myList.push_back(30);
    cout << "2->" << myList << endl;

    myList[1] = 40;
    cout << "3->" << myList << endl;

    myList.remove(2);
    cout << "4->" << myList << endl;

    for(int i=0; i<myList.length(); ++i)
        myList[i] = 100;
    cout << "5->" << myList << endl;

    myList.clear();
    cout << "6->" << myList << endl;

    cout << "capacity = " << myList.capacity() << endl;

    return 0; 
}

05. 실행 결과

1->{}
2->{10, 20, 30}
3->{10, 40, 30}
4->{10, 40}
5->{100, 100}
6->{}
capacity = 5