연결 리스트

지침

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

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

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

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

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

Python에서 이 연습 문제가 구성되는 방식

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

스텁 파일에는 Node 클래스의 시작 부분과 LinkedList 클래스가 보일 거예요. Node 클래스는 자신의 값과 어떤 노드가 앞뒤에 있는지 추적해야 해요. push, pop, shift, unshift, 그리고 len을 위한 특수 메서드는 LinkedList 클래스에 구현해야 해요. 반복을 위한 특수 iter 메서드를 구현하면 유용할 거예요.

기본 연습 문제와 달리, 여기서는 빈 LinkedLists에서 pop과 shift를 호출해 오류 상황을 테스트하므로, 오류를 적절히 raise해야 해요.

마지막으로, 위에 설명한 메서드 외에도 delete를 구현해 주세요. delete는 연결 리스트에서 제거할 값을 인자 하나로 받아요. 값이 두 번 이상 나타나면, 첫 번째 항목만 제거해야 해요.

예외 메시지

때로는 예외를 발생시켜야 할 때가 있어요. 이렇게 할 때는 오류의 원인이 무엇인지 알려 주는 의미 있는 오류 메시지를 항상 포함해야 해요. 이렇게 하면 코드가 더 읽기 쉬워지고 디버깅에 큰 도움이 돼요. 오류 원인이 특정 타입일 것이라고 아는 상황이라면 내장 오류 타입 중 하나를 발생시키도록 선택할 수 있지만, 그래도 의미 있는 메시지를 포함해야 해요.

이 연습 문제에서는 delete() 대상인 노드 값이 연결 리스트에서 발견되지 않을 때 raise 문을 사용해 ValueError를 "던져야" 해요. 또한 pop()할 노드가 남아 있지 않으면 IndexError를 던져야 해요. 테스트를 통과하려면 이 exceptions를 raise하고 메시지도 함께 포함해야 해요.

메시지와 함께 ValueError를 발생시키려면, 메시지를 exception 타입의 인자로 작성해요:

# When the value passed to `delete()` is not found.
if not found:
    raise ValueError("Value not found")

메시지와 함께 IndexError를 발생시키려면, 메시지를 exception 타입의 인자로 작성해요:

# When pop() is called and there are no nodes left in the linked list
if self.length == 0:
    raise IndexError("List is empty")

Python의 특수 메서드

이 연습 문제의 테스트는 LinkedList에 len()을 호출하기도 해요. len()이 작동하게 하려면 __len__ 특수 메서드를 만들어야 해요. Python에서 특수 메서드나 "dunder" 메서드를 구현하는 자세한 방법은 Python 문서: 기본 객체 사용자 정의와 Python 문서: object.len(self)를 참고해요.

또한 연결 리스트를 반복하는 데 도움이 되도록 특수 __iter__ 메서드를 만드는 것도 권장해요.