Array

// 3칸짜리 빈 배열 생성 (0 / null)
int[] arrayA = new int[3];

// 3칸짜리 배열 생성 후 데이터 삽입
int[] arrayB = new int[3] { 10, 20, 30 };

// 배열 크기 생략
int[] arrayC = new int[] { 10, 20, 30 };

// new 생략
// 신택스 슈거(Syntactic Sugar) : 컴파일러 자동 처리
int[] arrayD = { 10, 20, 30};

• 선언 시점에 크기 고정
• 배열 객체 자체는 힙에 할당되며, 배열 요소는 객체 내부에 연속적으로 할당
• 타입 안정성
• 메모리가 연속적이므로 CPU 캐시 히트율이 매우 높아 순차적 접근에 빠름

Array 메모리 점유 지도

ex) int[3] { 10, 20, 30 }

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x1000	8	Object Header	runtime info
0x1008	8	MethodTable Pointer	type info
0x1010	4	Length	3
0x1014	4	Padding	(빈 값)
0x1018	4	array[0]	10
0x101C	4	array[1]	20
0x1020	4	array[2]	30

Q. 배열에 할당된 메모리에 Padding이 생기는 이유 ?

CLR은 객체 할당 시 메모리 접근 효율을 위해 일반적으로 8 바이트 정렬을 유지합니다. 따라서 배열의 데이터 시작 주소와 객체 전체 크기가 8의 배수가 되도록 패딩(Padding)이 삽입될 수 있습니다.

• Object Header + MethodTable Pointer + Length = 20 바이트
  • 8 바이트 정렬을 위한 고정 패딩
  • 데이터 시작 주소 정렬을 위해
• int라면 (4 바이트), 8로 안 떨어지기 때문에 꼬리 패딩
  • 객체 크기 정렬을 위해

Cache Hit

• 배열은 메모리가 연속적이라 CPU 캐시 히트율이 높아 빠르다
• CPU는 초고속 연산장치 ⇒ 천재 작업자
• RAM은 메인 메모리 ⇒ 아주 큰 도서관
• CPU가 연산을 하려면 RAM에서 데이터를 가져와야 하는데, RAM에 다녀오는 시간이 너무 오래 걸려서 CPU는 데이터를 기다리며 놀게 된다. 이 현상을 해결하기 위해 CPU 옆에 작지만 빠른 임시 저장소를 만들었는데 이것이 바로 CPU Cache
• 컴퓨터는 RAM에서 데이터를 가져올 때, Cache Line 단위로 주변 데이터까지 가져온다.
  • 캐시라인은 일반적으로 64 Byte
• 배열이 압도적으로 빠른 이유 = 연속된 메모리
  • 캐시 라인 단위로 가져온 CPU 캐시에 있는 데이터를 바로 사용하는 Cache Hit 덕분
  • 캐시 히트는 값 타입일 때 효율이 좋다

2차원 배열, Rectangular Array

int[,] gridA = new int[2, 3];

int[,] gridB = new int[2, 3] { { 1, 2, 3}, { 4, 5, 6} };

int[,] gridC = { { 1, 2, 3}, { 4, 5, 6} };

• 1차원 배열과 같이 일렬로 메모리 연속
  • 행 우선 방식 : [1] [2] [3] [4] [5] [6]
• 접근할 때는 내부적으로 곱셈 연산을 통해 주소 탐색

가변 배열, Jagged Array

int[][] jagged = new int[3][];
jagged[0] = new int[4];
jagged[1] = new int[2];

• 배열을 담는 배열
• 메모리 파편화. 메인 배열에는 실제 데이터가 아닌 다른 배열을 가리키는 주소가 들어있다.
  • 행마다 다른 크기의 배열 선언 가능
  • 메모리를 낭비하지 않을 수 있다

[,] vs [][]

• 가변 배열은 1차원 배열 접근을 두 번 수행하기 때문에 다차원 배열 접근(인덱스 계산 + 경계 검사)보다 빠를 수 있다
• GC 측면에서는 객체 수가 적은 2차원 배열이 유리
• 가변 배열은 메모리 지역성이 떨어진다

---

List

// 빈 리스트 생성 (Capacity = 0)
List<int> listA = new List<int>();

// 초기 용량 예약
List<int> listB = new List<int>(3);

// 컬렉션 초기자
List<int> listC = new List<int> { 1, 2, 3, 4, 5 };

https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs

• System.Collections.Generic
• Array를 래핑하여 크기를 자동으로 관리해주는 클래스
  • T[] _items : 내부 배열
  • int _size : 데이터 갯수
  • int _version : 수정 횟수
• 타입 안정성
  • 제너릭 사용으로 컴파일 시점에 타입 보장
• 동적 확장 알고리즘
  • Count : 실제 들어있는 요소의 갯수
  • Capacity : 리스트가 내부적으로 확보하고 있는 배열의 용량
  • 데이터를 추가하다가 Count가 Capacity와 같아지면, 리스트는 내부적으로 기존 배열 크기의 2배 크기를 가진 새로운 배열을 힙에 할당하고, 기존 데이터를 모두 복사. 기존 배열은 GC의 대상
  • 최적화를 위해 Capacity 미리 설정하는 것이 좋다
  • 선언 하지 않으면 초기 용량 = 0 → 4 → 8 → 16
• 요소 삭제 비용
  • O(N)
  • RemoveAt 을 사용해 삭제하면, 빈 공간을 메우기 위해 뒤에 있는 모든 요소의 메모리 주소를 한 칸씩 앞으로 당겨야(Shift)합니다. 데이터가 많을수록 성능 저하
• 시간 복잡도
  • Add (resize) : O(N)
  • Add : O(1)
  • 인덱스 접근 : O(1)
    • 메모리 지역성이 좋아 순차 접근 성능 좋음
  • Remove, RemoveAt, Insert, Contains : O(N)
• _version
  • 구조 변경 횟수 저장
  • 열거 중 컬렉션 수정 감지 (fail - fast : 구조 변경시 즉시 예외 발생)

List 메모리 점유 지도

ex) List(3) { 10, 20, 30 }

• 본체 : List

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x1000	8 Byte	Object Header	(시스템 정보)
0x1008	8	MethodTable Pointer	(타입 정보 주소)
0x1010	8	_items	0x2000	내부 배열 주소
0x1018	4	_size	3	현재 데이터 갯수
0x101C	4	_version	3	변경 횟수

• _items 배열 : int[]

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x2000	8	Object Header	runtime info
0x2008	8	MethodTable Pointer	type info
0x2010	4	Length	4
0x2014	4	Padding	(빈 값)
0x2018	4	_items[0]	10
0x201C	4	_items[1]	20
0x2020	4	_items[2]	30
0x2024	4	_items[3]	0
0x2028	4	padding	(빈 값)

Array와 List의 접근 속도 차이

리스트의 내부는 결국 배열이기 때문에, 아주 미세한 속도 차이 발생

• 이중 참조 (Double Indirection)
  • 배열은 메모리에 접근할 때 한 번에 배열 데이터가 있는 곳으로 직행
  • 리스트는 데이터에 접근할 때 힙 메모리에 있는 리스트 객체를 찾고 그 안에 내부 배열의 주소로 한 번 더 이동하기 때문에 발생하는 미세한 비용
• 경계 검사 (Bounds Checking)
  • 접근하려는 인덱스가 Count보다 작은지 확인

Add 반복 vs AddRange

배열이나 컬렉션을 한 번에 추가할 때는 AddRange가 더 효율적입니다.
AddRange는 추가할 갯수를 미리 확인해서 Capacity를 한 번만 확장하고 Array.Copy로 복사하지만, Add를 반복하면 Capacity 체크가 매번 발생하고 Resize가 여러 번 일어날 수 있기 때문입니다.

• AddRange
  • ≠ foreach로 원소 추가
  • == Array.Copy
• Array.Copy
  • CPU가 메모리를 블록 단위로 복사
• 기존 리스트의 용량이 충분해서 Resize가 일어나지 않을 정도라면 비슷

Indexer

List<Vector3> positions = new List<Vector3>(1) { Vector3.zero };

// CS1612 컴파일 에러 발생
positions[0].x = 10;

• List의 Indexer는 값을 복사
  • 참조 타입일 경우 : 객체 주소
  • 값 타입일 경우 : 임시 변수
    • ⇒ 별개의 복사된 값이 나오기 때문에 컴파일 오류 발생
• 해결 방법
  • 값을 꺼내서 수정하고 다시 넣기

    Vector3 temp = positions[0];
    temp.x = 10;
    positions[0] = temp;

    • 값 복사 비용
  • 리스트를 배열로 수정
    • 배열의 인덱서는 값을 복사하지 않고, 요소의 메모리 주소에 직접 접근
  • 구조체를 클래스로 수정
    • GC 부담
• Q. List가 ref로 구현되었다면 ?
  • ⇒ 동적 배열이기 때문에 Resize 할 때 내부 배열이 새로 할당되며 기존 배열을 참조하던 ref가 망가진다 (dangling reference)

리스트는 중간을 제거하면 왜 앞당길까

• 인덱스의 신뢰성 + 순회 성능 + 캐시 지역성
• 내부 배열 메모리는 그대로
  • Array.Copy로 요소만 이동
• TrimExcess() : 내부 배열을 현재 갯수에 맞춰 재할당
  • Resize하지 않을 읽기 전용으로 사용할 때만 사용하는 것이 좋다
  • Clear와 함께 리스트를 껍데기만 남기고 완벽하게 비울 때 사용

---

ArrayList

ArrayList arrayList = new ArrayList();
arrayList.Add(10);
arrayList.Add("Hello World");

• System.Collections
• 크기가 동적으로 변하는 배열
  • 내부적으로 object[] 타입의 배열을 캡슐화하여 사용
• 타입 안정성 없음
  • 내부 요소가 object 타입으로 다양한 타입 저장 가능
  • 컴파일 시 타입 체크 불가능
• 성능 문제
  • 값 타입을 넣을 때 박싱, 꺼낼때는 언박싱
  • 런타임 캐스팅 검사
  • GC 부담 증가

⇒ 이런 문제 때문에 List 등장

---

LinkedList

LinkedList<int> linkedList = new LinkedList<int>();

https://github.com/dotnet/runtime/blob/main/src/libraries/System.Collections/src/System/Collections/Generic/LinkedList.cs

• System.Collections.Generic
• 연속되지 않은 메모리 점유
  • => Cache Miss : 캐시 효율 낮음
  • 파편화된 노드의 연결
  • Next와 Previous의 이중 연결 리스트(Double Linked List)
  • 초기 용량 지정 불가
• 원형 연결 리스트
  • 첫 노드의 prev가 마지막 노드를 가리키고, 마지막 노드의 next가 첫 노드를 가리킨다
  • O(1) 속도의 AddLast를 위해
  • Q. 그럼 반복문에서 무한 루프인가요 ? ⇒ node.Next 가 head라면 null 반환
• 핵심 메소드
  • AddFirst, AddLast, AddBefore, AddAfter : O(1)
  • RemoveFirst, RemoveLast, Remove(node) : O(1) / Remove(value) : O(N)
  • Find(value), FindLast(value), Contains(value) : O(N)
• 주로 딕셔너리 (Dictionary)와 함께 사용
  • 노드를 캐싱해서 사용
  • ex) 데이터가 여러개인데, 순서가 수시로 바뀌고 중간에서 데이터가 들어오고 빠질 때

LinkedList 메모리 점유 지도

• 본체 : LinkedList

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x1000	8 Byte	Object Header	(시스템 정보)
0x1008	8	MethodTable Pointer	(타입 정보 주소)
0x1010	8	head	0x2000	첫 노드 주소
0x1018	4	count	3	데이터 갯수
0x101C	4	version	3	변경 횟수

• 첫 번째 노드 : LinkedListNode

메모리 주소	크기	변수 이름 / 역할	저장된 값
0x2000	8 Byte	Object Header	(시스템 정보)
0x2008	8	MethodTable Pointer	(타입 정보 주소)
0x2010	8	list	0x1000	속한 본체 주소
0x2018	8	next	0x3000	다음 노드 주소
0x2020	8	prev	0x4000	이전 노드 주소
0x2028	4	item	10	데이터
0x202C	4	padding	(빈 공간)	8 바이트 정렬용