[Data Structure] 3. 배열(Array), 리스트(List)

배열이란

배열은 연속적인 메모리상에 동일한 타입의 요소를 일렬로 저장하는 자료구조입니다.

배열의 사용

int 자료형 변수를 100개 선언해야 한다고 합시다.

int number1;
int number2;
int number3;
 .........
int number100;

한 눈에 보기에도 비효율적입니다.
이럴 때 사용할 수 있는 자료구조가 배열(Array)입니다.

int[] numbers;

너무 간단해지지 않았나요?
배열은 자료형 뒤에 '[ ]'(대괄호)를 붙여 선언합니다.
하지만 지금은 배열 선언만 했을 뿐 메모리는 할당되어 있지 않습니다.
사용하기 위해 배열의 메모리를 할당해 주도록 하겠습니다.

int[] numbers = new int[100];

new 키워드를 사용해 메모리를 할당해주곘습니다.
뒤의 대괄호에는 배열의 크기(메모리)값을 명시해주어야 합니다.

배열의 초기화

이제 배열의 메모리를 할당해주었으니 배열의 각 요소에 값을 지정해주겠습니다.
중괄호를 이용하여 요소의 값을 일일히 정해줄 수 있습니다.

int[] numbers = {1, 2, 3, 4, ... 99, 100};
// 하지만 100개의 값을 일일히 지정해주는 것은 비효율적입니다.

배열의 특징

• Index

  배열은 연속된 메모리 공간으로 이루어져 있어 메모리 관리에 용이합니다.
  또한 배열의 값들은 index로 이루어져 있어 index를 사용해 접근 시 빠르게 해당 값을 찾을 수 있습니다.
  접근 / 탐색 시간 복잡도 O(1)

• 동적할당이 불가능

  하지만 배열은 동적할당이 불가능하다는 단점이 있습니다.

• 메모리 낭비

  Array에 할당된 많은 메모리 블록은 고정 크기 메모리가 할당된 후 새 항목이 추가될 때까지 사용되지 않은 상태로 유지됩니다. 또한 다른 프로세스에 할당할 수 없으므로 메모리 낭비가 발생합니다.

리스트와의 차이점

리스트는 배열 기반의 자료구조입니다. 하지만 배열에 비해 자료의 입출력이 더 역동적이고 특히 크기를 자유자재로 조절할 수 있다는 점(동적할당이 가능하다)이 있습니다.

배열은 초기화할 때 크기를 선언해주어야 하지만 리스트는 데이터를 추가할 때 size가 default Length에 도달하였을 경우 리스트의 길이를 늘리는 작업을 합니다.

1. 리스트의 Size(Count)가 Capacity(Length)에 도달한다.
2. 새로운 Capacity를 설정해준다. (보통은 기존의 2배)
3. 새로운 List[Capacity]를 만들어준다.
4. Array.Copy()를 통해 기존 배열을 복사한다.
5. 원래의 List = 새로운 List

public void Add(T item) // List에 데이터를 추가
{
	if(size < items.Length) // items : 기존 List
    	items[size++] = item;
    else
    	Grow(); // List의 길이를 늘리는 함수
}

public void Grow() // List의 길이를 늘리는 함수
{
	int newCapacity = items.Length * 2; // 보통은 2배
    T[] newItems = new T[newCapacity];
    Array.Copy(items, 0, newItems, 0, size); // items의 자료를 newItems에 0번부터 size만큼 복사한다.
    items = newItems;
}