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

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

-배열 

-연결 리스트

-스택/큐

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

-트리

-그래프

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

배열:

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

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

장점:연속된 방

단점 방을 추가 / 축소 불가

동적 배열:

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

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

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

동적 배열 할당 정책:

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

       - 이사 횟수를 최소화

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

단점: 중간 삽입/삭제

연결 리스트:

       -연속 되지 않은 방을 사용

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

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