개념 - 선형 자료구조의 특성 정리

// 2018-03-04 (이름)

/***********************************************************************************************************

선형 자료의 저장방식에 따른 특성

정적배열 기반 :

장점 : 상수시간 원소접근, 캐싱 친화적

단점 : 고정적인 크기, 삽입 삭제시 복사비용 발생(데이터가 크고 많을 수록)

동적배열 기반 :

장점 : 상수시간 원소접근, 캐싱 친화적, 가변적인 크기

단점 : 삽입 삭제시 복사비용 발생(데이터가 크고 많을 수록), 용량이 한계에 다다를 때마다 재할당 및 복사 발생

연결노드 기반 : 

장점 : 가변적인 크기, 중간의 삽입 삭제 용이

단점 : 상수시간 접근 불가능(치명적), 힙의 빈번한 삭제 재할당시 단편화 우려, 캐싱 비친화적

***********************************************************************************************************

선형 자료구조의 특성에 따른 분류

배열 : 일반적으로 (뒤로 커질 때) 가장 무난한 자료구조.

정적 배열 : std::array

동적 배열 : std::vector

리스트 : 삽입 삭제에 좀 더 유연한 자료구조.

정적 리스트 : 일반 배열에 인터페이스만 갖춘 모양새

이중 연결리스트 : std::list

단일 연결리스트   : std::forward_list

원형 연결리스트

덱 : 앞 뒤 삽입 삭제에 좀 더 유리한 자료구조. 

동적 배열의 배열 : std::deque

(일반적으로는 더블 링크드 리스트로 구현할 수 있음)

스택, 큐 : 삽입, 삭제의 위치를 제한함. std에서는 컨테이너 어댑터로 사용됨. 기본적으로는 deque 사용.

std::stack

std::queue

***********************************************************************************************************

선형 자료구조의 대표적 ADT

배열(정적) : []

배열(동적) : [],++, --, resize, reserve, push_back

리스트 : insert, erase. (단일 연결일 경우) insert_after, erase_after

접근 : ++,--, next, advance 등으로 순차 접근(sequential access) 

덱 : push_back, pop_back, push_front, pop_front

접근 : front, back

스택 : push_back, pop_back

접근 : back

큐 : push_back, pop_front

접근 : front

***********************************************************************************************************/

비선형구조 들어가기 전에 필요성을 느껴서 정리했다.