코드 8-8을 보면 이전 원소를 가져오는 prev() 메서드와 다음 원소를 가져오는 next() 메서드가 매우 유사하다는 것을 알 수 있습니다. prev 메서드만 예로 보면 next 함수는 쉽게 구현할 수 있습니다. 이전 요소를 가져올 때 크게 두 가지 경우가 있을 수 있습니다.

그림으로 살펴봅시다.

▲ 그림 8-7 prev( ) 메서드

그림 8-7은 prev() 메서드가 다루는 크게 두 가지 상황을 연출한 것입니다. 그림에서 왼쪽은 왼쪽 자식 노드가 있는 경우인데, 이때 노드 7의 이전 노드는 왼쪽 자식 노드에서 가장 큰 노드를 구하면 됩니다. 이 그림에서는 노드 6이 되겠지요. 두 번째는 왼쪽 자식이 없는 경우인데 이때는 부모를 따라 올라갑니다. 이 상황에서 부모의 오른쪽 자식이 현재 노드라면 이는 부모 노드가 현재 노드의 이전 노드임을 의미합니다. 그림 8-7에서 오른쪽 아래 그림을 눈여겨보세요.