[자료구조/선형구조] 배열

배열

• 메모리 상에 원소를 연속하게 배치한 자료구조

배열의 성질

1. O(1)에 k번째 원소를 확인/변경 가능
2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음
3. Cache hit rate가 높음
   • cache hit rate: 캐시가 적중되는 정도
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

기능과 구현

• 임의의 위치에 있는 원소를 확인/변경 → O(1)
• 원소를 끝에 추가 → O(1)
• 마지막 원소를 제거 → O(1)
• 임의의 위치에 원소를 추가/제거 → O(N)
  • ex) 마치 책장에 책이 연속해서 꽂혀있을 때 중간에 책을 넣기 위해선 나머지 책들을 밀어야하는 것과 같은 상황

insert 함수

5번째 idx에 15를 추가하려면 (길이1추가) 오른쪽부터 땡겨오고 빈칸에 15를 넣어주자

void insert(int idx, int num, int arr[], int&len){
	for(let i=len; i>idx; i--) 
    	arr[i]=arr[i-1];
        arr[idx]=num;
        len++
}

erase 함수

2번째 idx에 6을 지우고 싶으면, 그냥 2번째부터 땡겨오면 된다. 길이는 -1

void erase(int idx, int arr[], int&len){
	len--;
    for(int i=idx; i<len; i++)
    arr[i]=arr[i+1];
}