[자료 구조] 선형 자료 구조

선형 vs 비선형

선형 자료 구조

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

• 배열
• 연결 리스트
• 스택 / 큐

비선형 자료 구조

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

• 트리
• 그래프

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

(호텔 방 예약으로 예시를 들면)

배열

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

장점 : 연속된 방

단점 : 방을 추가/ 축소 불가

동적 배열

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

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

단점 : 중간 삽입 / 삭제

=> 중간에 있는 방이 비어있을 경우 앞으로 땡겨서 이사해야 함
=> 추가할 방이 선점되어 있을 경우 다른 곳으로 이사해야 함

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

해결책

동적 배열 할당 정책

• 실제로 사용할 방보다 많이, 여유분을 두고 (대략 1.5~2배) 예약
  -> 이사 횟수를 최소화

연결 리스트

• 연속되지 않은 방을 사용

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

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