바쁜 철도 네트워크를 위한 열차 운행 일정 시스템을 개발하는 프로젝트를 진행하고 있어요.
이 운행 일정 시스템에서 쓸 열차 노선의 프로토타입을 만들어 달라는 요청을 받았어요. 각 노선은 특정 열차가 정차하는 역들의 순서로 구성되어 있어요.
여러분의 팀은 시간표에 있는 각 기차 노선을 표현하는 데 이중 연결 리스트를 사용하기로 했어요. 기차 노선을 따라 있는 각 역은 연결 리스트의 노드로 표현돼요.
역의 도착 시간과 출발 시간은 신경 쓰지 않아도 돼요. 각 역은 그냥 숫자로 표현돼요.
노선은 확장할 수 있어요. 노선의 처음이나 끝에 역을 추가하면 돼요. 노선의 처음이나 끝에서 역을 제거하면 노선을 줄일 수도 있어요.
가끔 역이 폐쇄되기도 하는데, 이때는 그 역이 노선의 처음이나 끝에 있지 않더라도 노선에서 제거해야 해요.
노선의 크기는 기차가 얼마나 멀리 가는지가 아니라 몇 개의 역에 정차하는지로 측정해요.
연결 리스트는 컴퓨터 과학의 기본적인 자료 구조로, 다른 자료 구조를 구현할 때 자주 사용돼요. 이름에서 알 수 있듯이, 연결 리스트는 서로 연결된 노드들의 리스트예요. 각 노드가 이웃한 노드 하나 또는 여러 개와 연결된 "노드"들의 리스트예요. 단일 연결 리스트에서는 각 노드가 자신의 뒤에 오는 노드에만 연결돼요. 이중 연결 리스트에서는 각 노드가 자신의 앞에 오는 노드와 뒤에 오는 노드 모두에 연결돼요.
연결 리스트를 더 깊이 파고들고 싶다면, 멋진 그림으로 설명해 주는 이 글을 확인해 봐요.
이번에는 이중 연결 리스트를 구현해 볼 거예요.
값 하나와 다음 노드 및 이전 노드를 가리키는 포인터를 담는 Node를 구현해요.
그다음 첫 번째 노드와 마지막 노드에 대한 참조를 가지고, 항목을 추가하고 제거할 수 있는 배열과 비슷한 인터페이스를 제공하는 LinkedList를 구현해요.
push (값을 뒤에 삽입해요);pop (값을 뒤에서 제거해요);shift (값을 앞에서 제거해요);unshift (값을 앞에 삽입해요);delete (일치하는 첫 번째 노드를 제거해요)구현을 단순하게 유지하기 위해, 테스트는 오류 조건을 다루지 않아요.
즉, pop이나 shift는 빈 리스트에서 호출되지 않아요.
Exercism에 가입하고 Tcl 트랙을 연습 문제 135개, 그리고 실제 사람의 멘토링과 함께 배우고 익혀 보세요. 모두 무료예요.