[알고리즘] 0.5 연결리스트

은행에서 대기번호를 저장하는 문제를 다시 생각해보자.

 

앞에서는 1차원 배열에 번호를 저장하도록 구현했다.

이 방법은 처음 선언하는 배열의 크기에 따라 입력할 수 있는 번호의 개수가 제한된다는 심각한 문제가 있다.

 

미리 너무 큰 배열을 잡으면 다른 중요한 은행 업무 프로그램들이 사용할 메모리가 부족하다.

그렇다고 배열을 너무 작게 잡으면 고객이 많이 몰리는 날에는 문제가 생긴다.

 

이를 해결하기 위해 연결리스트(Linked List) 자료구조를 써보자.

연결리스트는 노드(node)가 데이터를 담은 채로 연결되어 있는 자료구조다.

 

데이터와 포인터를 갖고 있는 노드들이 연결되어 있는데, 노드의 포인터는 다음 노드를 가리킨다.

Head는 첫 노드를, Tail은 마지막 노드를 가리킨다.

마지막 노드의 포인터는 아무것도 가리키지 않는다는 의미로 NULL 값을 가진다.

 

연결리스트는 배열과는 다르게 중간에 노드를 삽입하거나 제거할 때,

원소를 밀어내거나 이동할 필요가 없다.

 

하지만, 리스트에서 임의의 위치에 있는 ("n번째") 원소를 찾는 과정이 오래 걸린다.

 

1. 연결리스트로 큐 작성하기

연결리스트를 이용하여 대기번호 관리 프로그램을 구현하라.

 

[ 코드 ]

ㅇ

 

[ 결과 ]

ㅇ