1. 배열, 동적 배열, 연결 리스트 비교

1. 자료구조

자료구조를 크게 선형자료구조와 비선형자료구조로 구분할 수 있다.

선형자료구조

• 배열 / 동적배열
• 연결리스트
• 스택 / 큐

비선형자료구조

• 트리
• 그래프

---

2. 배열, 동적배열, 연결리스트

1. 배열

특징

• 초기 선언 시 크기를 결정되며, 해당 크기는 고정
• 메모리 상에 데이터가 연속적으로 붙어 있음.

장점

• 연속된 메모리 공간을 가지고 있다는 의미는 인덱스로 손쉽게 접근이 가능하다는 것을 의미한다.

단점

• 메모리 공간을 추가 및 삭제가 불가능하다.

-> 이런 특징을 기반으로 해당 강좌에서 길찾기 맵을 만들기 위한 Tile을 배열을 활용한다. 맵을 크기가 고정되며 맵마다 빠르게 접근할 필요성이 있기 때문에, 배열을 활용하는 것이 적합하다. (이처럼 활용에 따라 사용할 자료구조는 다양하다. 여러 자료구조를 알 수록 보다 쉽게 데이터를 다룰 수 있을 것으로 보인다.)

---

2. 동적배열

특징

• 배열의 크기를 유동적으로 변경하는 것이 가능하다.
• 메모리 상에 데이터가 연속적으로 붙어 있음.

동적 배열 할당 정책 :

• 실제로 사용할 방보다 많이, 여유분을 두고(대략 1.5~2배) 예약
  • 예를 들어 101호, 102호만 필요하지만 여유분으로 103호를 예약
  • 예약분까지 방이 차면?? -> 필연적으로 이사 필요!.
  • 이사가 필요하지만 추가 예약을 한다.
  • 방을 100개 사용한다. 여유분 50개!. 이사를 많이 하면 여유분이 점점 많아진다
• 이사 횟수를 최소화 -> 실제 코드 구현에서는 size와 capacity를 활용한다.

장점

• 유동적으로 변경이 가능하다는 점에서 기존 배열과 차별점이 있다.
• 배열과 마찬가지로 연속된 메모리 공간을 점유하기 떄문에 인덱스로 접근이 가능하다.

단점

• 데이터 삽입을 가정하면, 메모리 연속성을 유지하기 위해 전체 배열이 통째로 재배치가 이루어져야 한다.
  • 비용 발생
  • 중간 삽입 및 삭제가 어렵다.

---

3. 연결리스트

c++과 c#에서 사용되는 키워드가 다르다는 점을 알아둘 필요가 있다.

	동적배열	연결리스트
c++	Vector	List
c#	List	LinkedList

특징

• 연속된 메모리 공간을 가지지 않음.

장점

• 중간 삽입 및 삭제가 용이하다.

단점

• 연속된 메모리 공간이 아님으로 인덱스 사용 불가(임의접근 Random Access 불가)