(Data_structure) Array

1. Array

Fig. 1   A[10] 예시

 

Array는 같은 타입의 data들을 연속으로 저장할 수 있는 자료구조이다.

int arr[5], double arr[7], string arr[3] 등으로 활용 할 수 있다.

 

(1) Array의 기본 연산 

- insert_data(_idx, _data) : 해당 _idx의 위치에 _data를 삽입한다. (시간 복잡도 O(n))

- set(_idx, _data): 해당 _idx의 위치에 _data를 덮어쓴다. (시간 복잡도 O(1))

- remove(idx): 해당 _idx의 위치에 있는 data를 삭제한다. (시간 복잡도 O(n))

- at(idx): 해당 _idx의 위치에 있는 _data를 return 해준다. (시간 복잡도 O(1))

- printData(): 배열 내부에 존재하는 _data들을 _idx 순으로 출력한다. 

 

(2) Array의 장점

- 직관적이다.

- idx 값을 알 때 data를 불러오기 편하다.

- ... 

 

(3) Array의 단점

- Array의 크기가 결정된다. (크기를 미리 알고 선언해야한다)

- Array에 삽입시 시간 복잡도는 O(n)을 가진다.

 

(4) 관련 STL

- C++ 에서는 array를 제공해준다. (#include <array> 존재, 관련 내용 =  ) //추후 작성 예정

- array의 단점을 해결하는 대안 STL (#include <vector>존재, 관련 내용 = ) //추후 작성 예정

 

(5) 개인적으로 코드를 작성 했을 경우

#include <iostream>

using namespace std;

class Array {
public:
	int n; // 원소 수
	int* arr; 

	Array(int size) { // size가 지정되고 바꿀 수 없음
		this->n = 0;
		this->arr = new int[size];
		for (int i = 0; i < size; i++) { // Array 원소 0으로 초기화
			arr[i] = 0;
		}
	}


	int at(int idx) {
		if (idx >= n) {
			return 0;
		}
		else {
			return arr[idx];
		}

	}

	void set(int idx, int X) {
		if (idx >= n) {
			cout << 0 << "\n";
		}
		else {
			arr[idx] = X;
		}
	}

	void insert_data(int idx, int num) {
		if (n == 0) {
			arr[0] = num;
			n++;
		}

		else if (idx > n) {
			arr[n] = num;
			n++;
		}
		else {
			for (int i = n; i >= idx; i--) { //한칸씩 뒤로
				arr[i] = arr[i - 1];
			}
			arr[idx] = num;
			n++;
		}
	}

	int remove(int idx) {
		if (idx >= n) {
			return 0;
		}
		else {
			int value = arr[idx];
			for (int i = idx; i < n; i++) {
				arr[i] = arr[i + 1];
			}
			arr[n - 1] = 0;
			n--;
			return value;
		}
	}

	void printData() {
		if (n == 0) {
			cout << "Empty\n";
		}
		else {
			for (int i = 0; i < n; i++) {
				cout << arr[i] << " ";
			}
			cout << "\n";
		}
	}
};