Priori

대부분 어떤 프로그램을 만들 때 우리는 어느정도의 배열이 적당한지 바로 알 수 없습니다.

예를들면 사용자와 인터페이스를 제공하는 프로그램이라면 사용자의 입력에 따라서 사용할 저장공간의 크기가 달라져야 할 수도 있겠죠.

뭐 프로그램을 짜기 시작할 때에도 처음부터 완벽에 가까운 계획을 세우지 않는 이상 우리는 정확히 얼만큼의 저장공간을 확보해야할지 모를 것입니다.

즉, 이때 이렇게 한계가 존재하는 저장공간, 배열이 가득찰 경우에는 어떻게 해주어야 할까요?

이렇게 우리가 사용할 공간의 크기를 모른다는 문제를 Priori라고 합니다.

해결방법

Doubling Array

• Full Exception을 일으키면 배열의 크기를 doubling해준다

먼저 새롭게 배열의 크기를 다시 설정해 주는 방법이 있을 것입니다. 이 방식을 ArrayVector라고 생각하시면 될 것 같습니다.

이때, 배열의 크기를 어떻게 설정하느냐는 프로그래머가 결정해야 하는 사안입니다. 뭐,,, 주로 2배를 해주는 것이 적당하다는 의견이 많습니다..

Linked List

• 하나하나의 저장공간들을 이어붙여서 새로운 저장공간을 만드는 방법

두번째로 하나하나 저장공간을 만들어서 연결해주는 방법이 있을 것입니다. 이 방법이 List를 활용한 방법입니다.

두 방식은 각각 장단점이 서로 다르기 때문에 상황에 맞추어 그 방법을 결정하는 것이 좋을 것 같습니다.

구현

ArrayVector

위의 Doubling Vector는 주로 ArrayVector를 사용해서 구현합니다.

ArrayVector는 기본적으로 동적 배열할당의 형태를 가지고 있다고 생각하시면 됩니다.

• Heap(Array)

  • 동적으로 할당된 배열이 존재합니다.

• Stack(pointer)

  • 할당한 배열을 가리키는 포인터가 존재합니다.

이때 ArrayVector의 힘은 그 크기가 조절된다는 것에서 발생하게 됩니다.

위의 그림과 같이 가득찬 배열 A에 요소를 추가하고자 하면 크기가 2배인 동적 배열 B를 새로 만든 후 그 A의 값을 복사해 넣으면 될 것입니다.

즉, 다음과 같은 순서대로 진행될 것입니다.
1) 배열 A가 가득참

2) A의 2배 크기를 갖는 B를 새로 만듦

3) B에 A의 값을 복사함

4) 배열 A를 delete해줌

5) B의 이름을 다시 A로 바꿈

구현

위의 특성을 살리면 다음과 같이 구현할 수 있을 것입니당.

class ArrayVector {
public:
    ArrayVector();
    ~ArrayVector();
    ArrayVector(ArrayVector& Arr);

    ArrayVector& operator=(ArrayVector& Arr);
    Elem& operator[](int i){ if (i <= Size) return A[i]; }

    void reserve(int N);
    void insert(int i, const Elem& e);
    void erase(int i);
    
    int size() const { return Size; }
    int GetCapacity() const { return capacity; }
    bool empty() const { return Size == 0; }

    friend ostream& operator<<(ostream& out, ArrayVector& Arr);

private:
    int capacity;
    int Size;
    Elem* A;
};
inline ostream& operator<<(ostream& out, ArrayVector& Arr) {
    int i;
    out << "(";
    for (i = 0; i < Arr.size() - 1; i++)
        out << Arr[i] << ", ";
    out << Arr[i] << ")" << endl;
    return out;
}

ArrayVector::ArrayVector()
    :capacity(0), Size(0), A(NULL)
{ }

ArrayVector::~ArrayVector() {
    delete[] A;
}


ArrayVector::ArrayVector(ArrayVector& Arr) {
    capacity = Arr.GetCapacity();
    Size = Arr.size();

    A = new Elem[capacity];
    for (int i = 0; i < Size; i++) {
        A[i] = Arr[i];
    }
}

ArrayVector& ArrayVector::operator=(ArrayVector& Arr) {
    if (this != &Arr) {
        delete[] A;
        capacity = Arr.GetCapacity();
        Size = Arr.size();

        A = new Elem[capacity];
        for (int i = 0; i < Size; i++) {
            A[i] = Arr[i];
        }
    }
    return *this;
}

void ArrayVector::reserve(int N) {
    if (capacity >= N) return;
    Elem* B = new Elem[N];
    for (int j = 0; j < Size; j++)
        B[j] = A[j];
    if (A != NULL) delete[] A;
    A = B;
    capacity = N;
}
// 저장공간을 설정하는 함수
// 1. 입력값이 현재 용량보다 작으면 실행X
// 2. 입력받은 값으로 새로 동적할당 실행
// 3. 원래 A는 지우고 새로 동적할당한 배열을 다시 A가 가리키도록 함

void ArrayVector::insert(int i, const Elem& e) { 
    if (Size >= capacity) 
        reserve(max(1, 2 * capacity));
    for (int j = Size - 1; j >= i; j--)
        A[j + 1] = A[j];
    A[i] = e;
    Size++;
}
// i번째에 원소를 집어넣는 함수
// 1. 저장공간이 알맞는지 판단
// 2. 저장공간이 가득찬 경우 2배 (max(1, 2*capacity))
// 3. 한칸씩 미루고 그 자리에 삽입

void ArrayVector::erase(int i) {		
    for (int j = i + 1; j < Size; j++)
        A[j - 1] = A[j];
    Size--;
}
// i번째 원소를 삭제하는 함수
// 1. i+1부터 한칸씩 앞으로 당겨 i번째 원소 삭제

List

List는 몇개의 Node가 연결되어 만들어 지게 됩니다. 이때 이 Node의 연결 방식에 따라 다음 두개로 다시 나뉠 수 있습니다.

Singly Linked List

Singly Linked List는 각 Node에 1개의 값과 다음 Node의 주소가 적혀있는 list의 형태를 가집니다.

• Heap (Node)

  • Node들이 각각 다음 Node들을 가리키면서 존재합니다.

  • 마지막 Node의 next는 Null을 가리킵니다.

• Stack (head + tail)

  • head와 tail이 존재하고 이 둘은 각각 list의 끝에있는 Node를 가리킵니다.

Doubly Linked List

Doubly Linked List는 각 Node에 1개의 값과 앞과 뒤 Node의 주소가 적혀있는 list의 형태를 갖습니다.

• Heap (Node + SentinelNode)

  • Node들이 각각 앞과 뒤의 Node들을 가리키면서 존재합니다

  • 첫번째 Node의 prev는 앞쪽에 고정된 Sentinel Node를 가리키고, 마지막 Node의 next는 뒤쪽에 고정된 Sentinel Node를 가리킵니다.

• Stack (header + trailer)

  • header는 맨 앞쪽에 고정된 Sentinel Node를 가리키고
    trailer는 맨 뒤쪽에 고정된 Sentinel Node를 가리킵니다.

비교

Array VS List

• fixed size vs variable size

• simplevs complicate

• high space efficientcy vs low space efficiency

• O(1) vs O(n)

즉, 정적인 환경, 배열의 사이사이에 무언가를 넣을 필요가 없을 경우 Array가 훨씬 더 좋은 성능을 가진다.

하지만 동적인 환경, 배열의 사이에 무언가를 넣을 필요가 있는 경우에는 List를 사용하는 것이 더 낫다.