[C++ 자/알 Note] 배열, 동적배열, 연결리스트

선형 vs. 비선형

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

ex. 배열, 연결 리스트, 스택/큐

 

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

ex. 트리, 그래프

 

배열

장점: 연속된 데이터로 임의 접근 가능

단점 1: 배열의 크기 변경 불가

단점 2: 중간 삽입/삭제 매우 비효율

 

동적배열

장점 1: 연속된 데이터로 임의 접근 가능

장점 2: 배열의 크기 변경 가능

단점 1: 배열의 크기를 변경하는 경우, 전체 데이터를 복사해야 하는 부담

단점 2: 중간 삽입/삭제 매우 비효율

단점 1의 해결책: 배열의 크기가 변경되는 경우에

어느정도 더 크게 (1.5배 or 2배) 생성해서 배열의 크기가 증가될수록 

배열의 크기 변경 횟수를 최소화하도록 내부적으로 작동

 

연결리스트

장점: 중간 삽입/삭제 매우 효율

단점: 연속되지 않은 데이터로 임의 접근 불가능 및 탐색 비효율