Array (배열)

배열이란?

같은 타입의 데이터를 나열한 선형 자료구조이다(sequence container)

연속된 메모리 공간에 순차적으로 저장한다.

배열의 크기가 고정되어 있고, 선언 시 배열의 크기를 정하고 이를 변경할 수 없다.

 

장점

• 구현이 쉽다.
• 인덱스를 이용해 접근이 가능해 검색 성능이 좋다.
• 데이터의 크기가 확정적일 때 배열을 사용하는 것이 메모리나 처리속도 면에서 좋다.
• 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다.

 

단점

• 삽입과 삭제가 어렵고 오래 걸린다.
  • 원소를 삽입하거나 삭제할 경우, 다음 항목의 모든 요소를 이동시켜야 한다. (연속된 메모리 공간)
  • 이를 위한 연산작업이 수행되어 비효율적이다.
  • 자료의 수에 비례하여 성능이 떨어지게 된다.
• 배열의 크기를 바꿀 수 없다.
  • 크게 잡을 경우 메모리가 낭비된다.
  • 작게 잡을 경우 그 이상의 자료를 저장하지 못한다.
• 메모리의 재사용이 불가능하다.
  • 배열은 초기 사이즈만큼의 메모리를 할당받아 사용하기
  • 데이터의 존재 유무와 관계없이 그 만큼의 메모리를 사용한다.
  • 이미 삭제된 데이터여도 (배열 요소 삭제)
  • 배열 자체를 제거하지 않는 이상 삭제된 공간의 메모리 재사용은 불가능하다.

언제 사용?

• 데이터가 정해져 있을 때
• 데이터 삽입 삭제를 적게 하는 경우
• 검색

시간복잡도

• 삽입/삭제
  • 배열의 맨 앞에 삽입/삭제 하는 경우 -> O(n)
  • 배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)
  • 배열의 중간에 삽입/삭제하는 경우 : O(n)
• 탐색
  • O(1)

 

배열의 성질

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

 

배열 추가 삭제 구현

public class ArrayManipulator {
    private int[] array;
    private int size;
    
    public ArrayManipulator(int initialCapacity) {
        array = new int[initialCapacity];
        size = 0;
    }
    
    public void insert(int index, int value) {
        if (size == array.length) {
            // 배열이 꽉 찼을 때, 더 큰 배열을 생성하여 요소를 복사합니다.
            int[] newArray = new int[array.length * 2];
            for (int i = 0; i < size; i++) {
                newArray[i] = array[i];
            }
            array = newArray;
        }
        
        // index 위치에 value를 삽입하고, 뒤의 요소들을 한 칸씩 뒤로 이동합니다.
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = value;
        size++;
    }
    
    public void erase(int index) {
        // index 위치의 요소를 삭제하고, 뒤의 요소들을 한 칸씩 앞으로 이동합니다.
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        size--;
    }
    
    public void print() {
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

public static void main(String[] args) {
    ArrayManipulator arr = new ArrayManipulator(3);
    arr.insert(0, 1);
    arr.insert(1, 2);
    arr.insert(2, 3);
    arr.print(); // 1 2 3
    arr.insert(1, 4);
    arr.print(); // 1 4 2 3
    arr.erase(2);
    arr.print(); // 1 4 3
}

배열의 선언 방법

public class ArrayExample {

	public static void main(String[] args) {
		int[] a;		// 구성 요소의 자료형이 int형인 배열
        a = new int[];	// new를 사용하여 배열 본체를 생성한 뒤 배열 변수 a와 연결
        int[] a = new int[5];
	} // end of main()
}// end of class

 

 

배열의 특성 확인하기

// 구성 요소의 자료형이 int형인 배열(구성 요솟수는 ５: new에 의해 본체를 생성）

class IntArray {
    public static void main(String[] args) {
        int[] a = new int[5];   // 배열 선언

        a[1] = 37;              // a[1]에 37을 대입
        a[2] = 51;              // a[2]에 51을 대입
        a[4] = a[1] * 2;        // a[4]에 a[1] * 2 곧 74를 대입

        for (int i = 0; i < a.length; i++)    // 각 요소의 값을 표시
            System.out.println("a[" + i + "] = " + a[i]);
    }
}

 

배열의 요솟값을 초기화하며 배열 선언하기

// 구성 요소의 자료형이 int형인 배열(구성 요솟수는 5: 배열 초기화에 의해 생성)

class IntArrayInit {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};        // 배열 초기화에 의해 생성

        for (int i = 0; i < a.length; i++)
            System.out.println("a[" + i + "] = " + a[i]);
    }
}

---

용어정리

 

- Cache hit rate

캐시 히트율(Cache hit rate)은 컴퓨터 시스템에서 캐시에 저장된 데이터 중에서
요청에 응답할 수 있는 데이터의 비율을 나타내는 지표입니다.
이것은 캐시가 유용하게 사용되고 있는 정도를 평가하는 데 사용됩니다.

캐시는 빠른 접근이 가능한 저장장치입니다.
배열의 경우, 캐시 히트율은 어떤 요소를 참조할 때 해당 요소가 캐시에 이미 저장되어 있을 확률을 의미합니다.
즉, 캐시 히트가 발생하면 해당 데이터를 가져오는 데 걸리는 시간이 크게 줄어들어 더 빠른 응답이 가능해집니다. 따라서 캐시 히트율이 높을수록 배열의 데이터 접근 속도가 향상됩니다.

하지만, 캐시 히트율이 높다고 해서 항상 좋은 것은 아닙니다.
만약 캐시의 크기가 작거나, 캐시의 유효성 검사 알고리즘이 비효율적이라면,
캐시 메모리를 비워주는 작업이 자주 발생할 수 있습니다.
이 경우 캐시 히트율이 높더라도 시스템 성능이 저하될 수 있습니다.
따라서 적절한 캐시 크기와 유효성 검사 알고리즘을 선택하는 것이 중요합니다.

---

참조

velog.io/@choiiis/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4Array%EA%B3%BC-%EB%A6%AC%EC%8A%A4%ED%8A%B8List

[자료구조] 배열(Array)과 리스트(List)

opentutorials.org/module/1335/8677

배열 - Data Structure (자료구조)

codedragon.tistory.com/7468

배열(array)의 장단점