연결 리스트

지침

여러분의 팀은 시간표에 있는 각 기차 노선을 표현하는 데 이중 연결 리스트를 사용하기로 했어요. 기차 노선을 따라 있는 각 역은 연결 리스트의 노드로 표현돼요.

역의 도착 시간과 출발 시간은 신경 쓰지 않아도 돼요. 각 역은 그냥 숫자로 표현돼요.

노선은 확장할 수 있어요. 노선의 처음이나 끝에 역을 추가하면 돼요. 노선의 처음이나 끝에서 역을 제거하면 노선을 줄일 수도 있어요.

가끔 역이 폐쇄되기도 하는데, 이때는 그 역이 노선의 처음이나 끝에 있지 않더라도 노선에서 제거해야 해요.

노선의 크기는 기차가 얼마나 멀리 가는지가 아니라 몇 개의 역에 정차하는지로 측정해요.

C++ track에서 이 연습 문제가 구성되는 방식

연결 리스트는 다양한 기반 자료 구조를 이용해 여러 방식으로 구현할 수 있지만, 여기서는 연결 리스트를 객체 지향 방식으로 구현해 주세요.

linked_list_test.cpp 파일을 보면 템플릿 List 클래스가 호출되는 것을 알 수 있어요. 이 클래스에는 다음 멤버 함수를 작성해야 해요:

• push는 리스트 끝에 원소를 추가하고,
• pop은 리스트의 마지막 원소를 제거한 뒤 반환하고,
• shift는 리스트의 첫 번째 원소를 제거한 뒤 반환하고,
• unshift는 리스트 맨 앞에 원소를 추가하고,
• count는 현재 리스트에 있는 원소의 총 개수를 반환해요.

마지막으로, 위에서 설명한 메서드에 더해 erase도 구현해 주세요. erase는 인자 하나를 받는데, 그 인자는 연결 리스트에서 제거할 값이에요. 같은 값이 두 번 이상 나타나면 처음 나타난 것 하나만 제거해야 해요. erase는 원소가 삭제되었는지 여부를 반환해야 해요.

테스트되지는 않지만, 빈 List에서 pop과 shift를 호출하면 예외를 발생시키고 싶을 수도 있어요.