배열(Array)

배열은 프로그래밍시 가장 자주 사용되는 자료구조다. 

자바에서 배열을 선언은 아래처럼 한다. 

// 선언과 동시에 초기화.
int []elements = { 15, 7, 11, 44, 93, 20};

 

배열의 특성을 알기 위해서 위와 같이 선언시  컴퓨터 메모리에 어떻게 저장되는지 이해할 필요가 있어 아래 그림 기준으로 설명한다.

 

우선 컴퓨터 내부적으로는 6개의 정수를 저장할 메모리 공간을 할당한다.

자바에서 integer는 4bytes 이므로 총 6x4 = 24bytes를 할당하게 될 것이다.   

핵심은 이렇게 할당된 메모리 공간은 연속되어 있다는 것이다.

즉, 위 그림은 보면 메모리 주소가 address = 1100 에서 4bytes씩 address=1120까지 연속(4bytes씩 증가하면서 끊기지 않고 되어 있다는 뜻)되어 할당 되어 있고 그 메모리에 값을 저장한 것을 보여주고 있는데 address (1100) 에 15를 그리고 integer 가 4bytes를 차지하니 그 다음것은 4bytes가 더 해진 주소 address(1104)에 7이 저장되고 address(1108) = 11 식으로 저장되고 있다. 

 

보통 C  or C++ 개발자들은 포인터 개념이 있어서 항상 메모리를 머리속에 그리면서 프로그래밍하다 보니 위 설명은 그리 어렵지 않을수 있으나 모던 랭귀지나 메모리를 직접 관리해주는 언어만 알고 있는경우  이해가 어려울수도 있겠다. 

 

이렇게 연속된 메모리 공간에 값이 할당되어 있으면 장점이 있는데 값을 엑세스 할 때 매우 빠르다는것이다. 

// 선언과 동시에 초기화.
int []elements = { 15, 7, 11, 44, 93, 20};
 
System.out.println(elements[0]);
System.out.println(elements[2]);
System.out.println(elements[4]);
 
elements[5] = 21;

 

랜덤액세스가 매우 빠른 이유는 연속된 메모리의 공간에 저장되어 있다 보니 단순한 공식만 알면 어느 index던 O(c)의 속도로 엑세스 가능하다. 

 

공식 f(i) = [0] 번 인덱스의 address + i*sizeof(integer)  , i =  엑세스하려는 인덱스 

 

예를들어 3번째 인덱스에 엑세스 한다면 [0]번의 주소 1100 + 3 x 4bytes(sizeof(integer)) = address (1112) 이고 이주소에 있는 값은 위 그림의 3번째 인덱스에 있는 44와 정확히 일치한다. 

 

그래서 보통 랜덤엑세스가 자주 일어나고, 빨리 읽고/쓰기(R/W)가 필요하다면 배열 자료구조를 선택하는 것이 유리하다. 

하지만 장점이 있으면 단점이 있는데 랜덤 엑세스가 빠르지만 중간에 삽입, 삭제는 오퍼레이션(operation)은 굉장히 불리하다. 

 

왜냐하면 배열은 연속된 메모리가 공간에 값이 할당된다고 하였는데 중간에 삽입되거나 삭제 될 때 메모리 연속성이 깨지는 경우 기존의 메모리를 삭제하고 다시 할당해야 하거나 각 인덱스들을 한칸씩 앞/뒤로 모두 이동해야 하는 operation들이 추가로 일어나기 때문이다. 

 

그래서 배열은 추가,삭제가 빈번한 자료구조를 저장하기에 적당하지 않다. 이런 경우는 배열보다 링크드리스트가 더 유리하다. 

물론 링크드리스트는 랜덤엑세스에는 불리하다는 단점을 가지고 있다. 따라서 내가 저장하려는 자료구조가 어떤 오퍼레이션이 빈번한지 검토후 최적의 자료구조를 선택해야 한다. 

어쨌든 자바에서는 이런 배열 자료구조를 위해 콜렉션(Collections)에서 ArrayList<> 를 C++ 에서는 stl::vector 를 built-in 으로 제공하고 있다

// java
List<Integer> v = new ArrayList<>(); 
v.add(10);
v.add(20);
 
// C++
stl::vector<int> v;
v.push_back(10);
v.push_back(20);
 
 
// Python
import array as arr
v = arr.array('i')
v.append(10)
v.append(20)
 
// Swift
import Foundation
 
var v: Array<Int> = [Int]()
v.append(10);
v.append(20);
print(v[0]);
 
// kotlin
val v: MutableList<Int> = ArrayList()
v.add(10);
v.add(20);
    
println(v[0]);
 
// Objective-C
NSMutableArray *v = [NSMutableArray arrayWithCapacity: 10];  
[v addObject: [NSNumber numberWithInteger: 10]]; 
[v addObject: [NSNumber numberWithInteger: 20]];
NSLog (@"%d", [[v objectAtIndex: 0] integerValue]);// 10