[자료구조] 배열(Array)(1): 배열의 개념과 메모리 관리, 정적 배열(Array) vs 동적 배열(Dynamic Array)

반응형

 

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

 

 

💋 배열(Array)

✔️ 개념

 

• 같은 타입의 데이터를 연속적인 메모리 공간에 저장해 인덱스로 접근하는 자료구조
• 하나의 유형에 속하는 일정한 개수의 값들을 담고 있는 컨테이너 - oracle

An array is a container object that holds a fixed number of values of a single type.

 

✔️ 특징

• 인덱스(Index) 기반
• 각 element는 순서에 따라 고유한 인덱스를 가진다
• index를 통해 element에 접근할 수 있다.
• 대부분의 프로그래밍 언어에서는 0부터 시작하는 인덱스를 사용한다.
• 고정된 크기
• 배열은 한 번 크기가 지정되면 변경할 수 없다. 즉, 크기를 줄일 수도, 늘릴 수도 없다.
• 만약 더 많은 데이터를 저장해야 한다면 새로운 배열을 생성해야 한다.
• 연속적인 메모리 할당
• 배열의 각 element는 메모리 상에 연속적으로 저장되어 있어, 인덱스를 통한 빠른 접근이 가능하다.

 

다음 인덱스의 저장 위치는 우리가 어떤 데이터 타입을 쓰냐에 따라 달라진다. 

 

✔️ 인덱스는 왜 0부터 시작될까?

배열의 첫 번째 원소가 저장된 위치에서 0번째 떨어진 원소에 접근하겠다는 것과 같은 의미로, 인덱스는 배열에서 offset 개념으로 사용됩니다.

• offset : 배열의 첫 번째 원소와 다른 원소의 위치 차이

 

✔️ 장점

1. 빠른 접근: 인덱스를 통해 원하는 위치의 데이터에 빠르게 접근할 수 있습니다.
2. 메모리 효율성: 연속적인 메모리 할당으로 메모리를 효율적으로 사용할 수 있습니다.
3. CPU Cache: 연속된 메모리 공간에 데이터를 저장하기 때문에, CPU Cache를 통해서 같은 배열에 있는 다른 데이터에 접근하는 시간을 단축할 수 있습니다. (참고)

 

✔️ 단점

1. 고정된 크기: 배열의 크기는 고정되어 있어, 미리 크기를 정해야 합니다. 이는 불필요한 메모리 사용이나 부족한 공간으로 인한 문제를 일으킬 수 있습니다.
2. 삽입과 삭제의 어려움: 배열의 중간에 데이터를 삽입하거나 삭제하기 어려우며, 이로 인해 데이터 이동이 필요할 수 있습니다.

 

✔️ 원소가 저장된 위치를 간단하게 계산할 수 있다

 

배열의 특징 중 연속적인 메모리를 할당하기 때문에, 배열은 각 element의 위치를 아래와 같이 간단하게 계산할 수 있습니다.

 

 

element가 저장된 위치 = base address + offset

• base address : 배열의 첫 번째 원소(index 0인 원소)의 메모리 주소
• offset : 배열의 첫 번째 원소와 다른 원소의 위치 차이

 

✔️ 2차원 배열의 메모리 할당

 

2차원 배열은 아래와 같이 메모리에 할당됩니다.

 

이미지 출처: https://www.youtube.com/watch?v=Hpg6zS0Nq28&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=3

 

✔️ 객체를 담은 배열의 메모리 할당 (in Java)

 

자바에서 객체의 경우, 각 객체는 배열의 메모리 공간에 레퍼런스의 주소를 저장합니다.

실제 각 객체는 메모리상 다른 곳에 존재하고, 각 객체의 메모리 주소(reference)를 배열에 저장합니다.

 

이미지 출처: https://www.youtube.com/watch?v=Hpg6zS0Nq28&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=3

 

 

✔️ 참고자료

• https://www.geeksforgeeks.org/what-is-array/?ref=roadmap
• https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html
• https://www.geeksforgeeks.org/difference-between-static-arrays-and-dynamic-arrays/
• https://www.youtube.com/watch?v=Hpg6zS0Nq28&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=3

 

 

💋 동적 배열(Dynamic Array)

✔️ 개념

• 크기가 변할 수 있는 배열로, 데이터를 더하거나, 빼는 것이 가능한 자료구조
• resizable array, arraylist라고도 불린다.
• C++에서는 vector, Java에서는 ArrayList로 구현되었다.

 

정적 배열에서 고정된 크기로 인한 단점을 해결한 것 외에는, 특징과 장단점은 정적 배열에서 설명한 내용과 같습니다. 

 

동적 배열은 프로그래밍 언어의 표준 라이브러리나 언어 자체에서 지원되며, 내부적으로 정적 배열을 사용하여 동작한다.

예를 들어서, 자바의 경우에 동적 배열을 구현한 ArrayList 소스 코드에서는 정적 배열을 사용한다. 

참고로, 자바에서 정적 배열의 소스 코드는 자바 언어 자체에 내장되어 있어 직접적으로 확인하기 어렵다.

 

출처: https://en.wikipedia.org/wiki/Dynamic_array

 

 

✔️ 데이터 추가

 

(프로그래밍 언어마다 구현이 조금씩 다를 수 있는데, 일반적인 기준에서 동작 원리만 이해하면 된다.)

 

• 배열을 처음 선언할 때, (보통) 초기 데이터보다 조금 더 큰 메모리 사이즈로 생성한다.
• 데이터가 없이 남는 메모리 공간은, 비워두거나 예약해두거나 한다.
• 메모리 공간이 남는 상태에서 새로운 데이터가 추가되면 ,동적 배열 메모리 공간 끝에 차례대로 추가한다.
• 메모리 공간이 꽉 찬 상태에서 데이터를 추가하려고 하면, 동적 배열은 더 큰 메모리 사이즈를 할당한 (보통 2배) 새로운 배열을 만들어 기존 데이터들을 모두 옮기고, 그 뒤에 이어서 데이터를 추가한다.
• 모든 데이터를 복사하는 데 들어가는 시간 복잡도는 O(n)이지만, 이 경우는 currSize == capacity 인 경우에만 해당해서 그렇게 자주 발생하는 일은 아니긴 하다. (위안) 그 외의 경우에는 O(1)
• 참고로, 구현에 따라서 여기서 발생하는 성능 이슈가 너무 치명적이라, 일정 간격으로 새로운 메모리를 할당하여 데이터를 복사한다던가, 해서 전체 복사를 피하려고 하기도 한다.

 

 

✔️ 데이터 삭제

 

(프로그래밍 언어마다 구현이 조금씩 다를 수 있는데, 일반적인 기준에서 동작 원리만 이해하면 된다.)

 

삭제하는 인덱스보다 큰 인덱스의 모든 데이터의 인덱스를 하나씩 줄여가면서, 메모리 상에 저장된 주소까지 변경해야 하므로 비효율적이다.

 

✔️ Java의 동적 배열 동작 원리 파헤치기

 

Java에서 별도의 메모리 사이즈 지정 없이 ArrayList를 생성하면, 디폴트 capacity는 10이다.

 

Java의 Arraylist 클래스의 코드 중 일부인데, 위의 add(E e)를 호출한 경우, 자체적으로 세고 있던 사이즈를 조정한 후에 아래의 private 메서드인 add(E e, Object[] elementData, int s) 를 내부적으로 호출한다. 현재 메모리 공간이 가득 찼다면, grow()를 호출하고, 아닌 경우에 배열에 원소를 하나 추가한다.

 

public boolean add(E e) {
	++this.modCount;
	this.add(e, this.elementData, this.size);
	return true;
}

private void add(E e, Object[] elementData, int s) {
	if (s == elementData.length) {
		elementData = this.grow();
	}

	elementData[s] = e;
	this.size = s + 1;
}

 

grow()까지 따라가보면, newLength의 배열을 새로 만들고, 현재 배열의 데이터를 옮겨담는 과정을 확인할 수 있다. (Java 8 기준)

 

private void grow(int minCapacity) {
	// 현재 배열의 길이
	int oldCapacity = elementData.length;
	// 현재 배열보다 1.5배 크게 새로운 길이를 계산
	int newCapacity = oldCapacity + (oldCapacity >> 1);

	// 만약 계산된 새로운 길이가 사용자가 요구한 최소 크기보다 작다면, 최소 크기를 사용
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;

	// 만약 계산된 새로운 길이가 Integer.MAX_VALUE를 초과하면, Integer.MAX_VALUE로 설정
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);

	// Arrays.copyOf 메서드를 사용하여 새로운 길이의 배열을 생성하고 기존 배열의 요소를 복사
	elementData = Arrays.copyOf(elementData, newCapacity);
}

 

이 코드에서 (oldCapacity >> 1)는 비트 연산자를 사용하여 oldCapacity를 2로 나누는 것을 나타낸다. 따라서, 자바의 ArrayList는 1.5배 크기 배열을 새로 만든다. 

 

다만, 최소 크기 이하로 할당하거나 Integer.MAX_VALUE를 초과하는 경우에는 해당 값으로 설정하도록 로직이 처리되어 있다.

 

✔️ 참고자료

• https://www.enjoyalgorithms.com/blog/dynamic-array
• https://www.geeksforgeeks.org/how-do-dynamic-arrays-work/
• https://en.wikipedia.org/wiki/Dynamic_array
• https://www.youtube.com/watch?v=Hpg6zS0Nq28&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=3

 

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!