[자료구조] 배열, 동적 배열, 연결 리스트

---

배열

- 사용할 방 개수를 고정해서 계약하고 절대 변경이 불가하다.

- 연속된 방으로 배정 받아 사용

- 장점: 연속된 방

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

 

예시) 1인 1실 이용. 3명이 예약

호텔
501호	502호	503호	504호	505호	506호	507호	508호
401호	402호	403호	404호	405호	406호	407호	408호
301호	302호	303호	304호	305호	306호	307호	308호
201호	202호	203호	204호	205호	206호	207호	208호
101호	102호	103호	104호	105호	106호	107호	108호

 

 

동적 배열

- Vector

- push_back(O), front_back (X)

- 사용할 방 개수를 유동적으로 계약

- 연속된 방으로 배정 받아 사용

- 동적 배열 할당 정책: 실제로 사용할 방보다 여유분을 두고 (대략 1.5~2배) 예약, 이사 횟수를 최소화

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

- 단점: 중간 삽입/삭제가 비효율적이다. 복사비용이 더 들어간다.  ex. 303호를 사용하는 인원이  나가면 304, 305, 306호를 사용하는 인원이 한칸씩 당겨 301~305호가 채워지게 변경한다. 또 다른 예로 303호에 다른 인원이 추가되면 303~306호 인원이 한칸씩 뒤로 밀리게 변경된다.

 

예시) 1인 1실 이용. 3명이 예약. 

두세명이 더 올 수 있기 때문에 초기에 추가 방 예약. 

호텔
501호	502호	503호	504호	505호	506호	507호	508호
401호	402호	403호	404호	405호	406호	407호	408호
301호	302호	303호	304호	305호	306호	307호	308호
201호	202호	203호	204호	205호	206호	207호	208호
101호	102호	103호	104호	105호	106호	107호	108호

 

 

연결 리스트

- List

- push_back(O), front_back (O)

- 연속되지 않은 방을 사용

- 임의 접근이 불가능하다. 하지만 중간 삽입/삭제가 용이하다.   <- 모순적이다. N번째 위치에 삽입/삭제하려면 리스트를 처음부터 타고가서 접근한 후 삽입/삭제해야 한다. 위치를 저장하고 있을 때는 유용하지만 그렇지 않은경우 빠르다고 할 수 없다. 위치를 저장하고 있으려면 iterator를 활용하는게 좋다.

- 장점: 중간 삽입/삭제가 용이하다. 삽입/삭제할 위치를 저장하고 있을 때 빠르게 삽입/삭제를 할 수 있다. 하지만 위치를 저장하지 않고 단순히 위치만 알고 있으면 리스트를 통해 찾아가는 과정이 오래걸려 빠르다고 할 수 없다. 

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

 

예시. 1인 1실 이용. 3명이 예약. 

호텔
501호	502호	503호	504호	505호	506호	507호	508호
401호	402호	403호	404호	405호	406호	407호	408호
301호	302호	303호	304호	305호	306호	307호	308호
201호	202호	203호	204호	205호	206호	207호	208호
101호	102호	103호	104호	105호	106호	107호	108호

 

 

 

임의 접근이란?

- N번째 방이 몇 번 방인지 바로 찾을 수 있는지 여부.