선형vs비선형

자료구조는 크게 선형, 비선형으로 나뉜다.

• 선형 구조: 자료 순차적으로 배열한 형태, 일열로 하나씩 하나씩
  ex.은행에서 줄을 일열로 서는것
  - 배열
  - 연결 리스트
  - 스택/큐
  
• 비선형 구조: 하나의 자료 뒤에 다수의 자료
  ex. 윈도우 탐색기에서 폴더 하나 열면 1대 다 구조로 되어있는것
  - 트리
  - 그래프
  

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

• 배열:
  - 사용할 방의 개수를 고정해서 계약(절대 변경 불가)
  - 연속된 방으로 배정 받아 사용

장점 : 연속된 방

단점 : 유동적으로 추가 하거나 축소 불가

• 동적배열:
  - 사용할 방 개수를 유동적으로 계약
  - 연속된 방으로 배정 받아서 사용
  

문제점 : 이동하는 시간 이나 비용이 든다.

동적 배열 할당 정책 :
- 실제 사용할 것보다 더 많은 여유분을 둔다.
- 이동 횟수 최소화 해준다.(조금 쌈박한 논리임)

장점 : 유동적인 움직임(추가적인 여유분을 통해 이동 횟수 최소화 시킴)
단점 : 중간 삽입/삭제

• 연결리스트
  - 연속되지 않은 방을 사용

장점: 중간 추가 / 삭제 편리하다
단점 : N번째 위치로 바로 찾을 수 없음.(임의 접근 Random Access불가)
타고타고 연결을 해야지 찾아 갈 수 있다.