배열

배열

• 여러 자료들을 메모리 덩어리 안에 줄지어놓은 구조
• 각 자료는 색인(INDEX) 로 접근한다.

C로 구현

enum{ MAX_NUMS = 8};
int s_nums[MAX_NUMS];
size_t s_num_count = 0;

void insert_at(size_t index, int n){
	size_t i;
    
    assert(index <= s_num_count); // 이미 삽입된 index에 접근하려는 것인지 확인
    assert(s_num_count < MAX_NUMS); // 배열 크기를 초과하는지 확인

	for(i = s_num_count; i > index; -- i){
		    s_nums[i] = sums[i-1];
    }
    s_num[index] = n;
    ++s_num_count;

}

배열의 삽입

처음 or 중간

삽입하려는 위치의 요소부터 전부 뒤로 한 칸씩 밀어낸 뒤 삽입 : O(n)

마지막

삽입 후 끝 O(1)

배열의 삭제

삭제할 값을 찾는데 O(n) 소요, 중간에 빈 인덱스를 채울때까지 인덱스를 당김 O(n)
: 총 O(n) 소요

배열의 검색

배열 속 요소를 방문하며 값이 있는지 확인 : O(n)

인덱스를 알고있는 경우 : O(1)
연결리스트와 가장 큰 차이점임, 잘 알아둬야 함