[C# 자료구조] 선형 자료 구조 ( 배열 vs 동적 배열 vs 연결 리스트)

        public int[] _data = new int[25]; //배열
        public List<int> _data1 = new List<int>(); //동적 배열
        public LinkedList<int> _data3 = new LinkedList<int>(); //(이중)연결 리스트

**주의 C++과 혼돈될 수 있는데 

C#에서의 List<int>는 C++에서의 Vector<int>,

C#에서의 LinkedList<int>는 C++에서의 List<int>

각각 대응해서 비슷하게 짜여진 자료구조이다.

 

 

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

- 배열

- 연결 리스트

- 스택 / 큐

 

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

- 트리

- 그래프

---

1. 배열

(1) 장점 : 연속성(임의 접근 Random Access 가능)

(2) 단점 : 사이즈 추가 / 축소 불가 (고정)

 

2. 동적 배열

(1) 장점 : 연속성(임의 접근 Random Access 가능) / 유동적인 사이즈

(2) 단점 : 비용 (중간 삽입, 삭제) 한칸씩 땡겨주는 활동 필요

(3) 핵심 idea : 

 -1- 실제로 사용할 분량보다 많이, 여유분을 두기

 -2- -1-을 통한 이사 횟수(비용) 최소화

 

3. 연결리스트

(1) 연속되지 않은 공간을 사용

(자기 노드의 앞 노드, 뒤 노드만 알 수 있음.)

(2) 장점 : 중간 추가/ 삭제 이점 : 연결점만 바꿔주면 됨

(3) 단점 : N번째 공간을 바로 찾을 수가 없음(임의 접근 Random Access 불가)