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

배열

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

 장점 : 연속된 방

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

 

동적배열:

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

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

동적배열 할당 정책:

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

장점: 유동적인 방 계약(방 여유분 추가 예약으로 이사 횟수 초기화)

단점 : 중간 삽입/삭제

 

연결리스트:

• 연속되지 않은 방을 사용

장점: 중간 삽입/삭제 이점

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