*선형 자료구조는?
말 그대로 하나의 자료 뒤에 자료가 선 처럼 이어지는 형식이다. 앞 뒤로 1대 1로 연결되어 이어지는게 특징 (ex: 배열, 연결 리스트, 스택 / 큐)
*배열
사용할 개수가 고정되어 있으며, 변경이 불가능하다. 데이터가 연속되어야한다.
장점: 연속된 방
단점: 데이터를 추가하거나, 축소하는게 불가능하다.
*동적 배열
사용할 데이터를 유동적으로 삽입한다. 배열과 마찬가지로 데이터가 연속되어야 한다. 동적 배열에는 할당 정책이 있다. 실제 들어올 데이터보다 여유분을 두고 미리 배열의 크기(대략 1.5배~2배)를 할당한다.
장점: 유동적으로 데이터를 추가 할 수 있다. 또한 배열을 여유분을 미리 할당해놓기에, 유동성이 확보된다.
단점: 중간 삽입 및 삭제는 가능하나. 이 때 비용이 필연적으로 발생.
*연결 리스트
연속되지 않은 데이터를 링크만 걸어두는 형식
장점: 중간 추가/삭제 이점
단점: N번째 데이터를 바로 찾을 수 없음 (임의 접근, Random Access 불가)