연결 리스트

지침

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

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

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

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

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

구현

이중 연결 리스트를 구현해요. 값과 다음 및 이전 노드에 대한 포인터를 담는 Node를 구현해요. 그다음 첫 번째와 마지막 노드에 대한 참조를 담고, 항목을 추가하고 제거하는 함수를 제공하는 List를 구현해요.

Node에는 다음과 같은 필드와 메서드가 있어야 해요:

• Value: 노드의 값이에요 (any를 사용해요).
• Next() *Node: 다음 노드를 가리키는 포인터예요.
• Prev() *Node: 이전 노드를 가리키는 포인터예요.

List를 만들어서 반환하는 NewList() 함수가 있어야 해요:

• NewList(args ...any) *List: 값의 순서를 유지하면서 새로운 연결 리스트를 만들어요.

List에는 다음과 같은 메서드가 있어야 해요:

• First() *Node: 첫 번째 노드(헤드)를 가리키는 포인터를 반환해요.
• Last() *Node: 마지막 노드(테일)를 가리키는 포인터를 반환해요.
• Push(v any): 리스트의 뒤쪽에 값을 삽입해요.
• Pop() (any, error): 리스트의 뒤쪽에서 값을 제거해요.
• Unshift(v any): 리스트의 앞쪽에 값을 삽입해요.
• Shift() (any, error): 리스트의 앞쪽에서 값을 제거해요.
• Reverse(): 연결 리스트를 뒤집어요.