[C#] 배열, 동적 배열, 연결 리스트 비교

 

선형 vs 비선형

 1) 선형 구조는 자료를 순차적으로 나열한 형태

  - 배열

  - 연결 리스트

  - 스택 / 큐

 

 2) 비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

  - 트리

  - 그래프

 

배열 vs 동적배열 vs 연결 리스트

 1) 배열

  - 사용할 방 개수를 고정해서 계약하고 (절대 변경 불가)

  - 연속된 방으로 배정 받아 사용

장점 : 연속된 방

단점 : 방을 추가/축소 불가

 2) 동적 배열

  - 사용할 방 개수를 유동적으로 계약

  - 연속된 방으로 배정 받아 사용 (배열과 동일)

문제점 : 이사 비용은 어떻게?

동적 배열 할당 정책 :

  - 실제로 사용할 방보다 많이, 여유분을 두고 (대략 1.5 ~ 2배) 예약

  - 이사 횟수를 최소화

장점 : 유동적인 계약(방 추가 예약으로 이사 횟수 최소화)

단점 : 중간 삽입 / 삭제가 어렵다

 

 3) 연결 리스트

  - 연속 되지 않은 방을 사용

장점 : 중간 추가/삭제 이점

단점 : N번째 방을 바로 찾을 수가 없음(임의 접금 Random Access 불가)

 

 

 

---------------------------------------------------------------------------------------------------------------------------

참고 : [인프런] Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘