[자료구조와 알고리즘] 10강 실습(1) | 양방향 연결 리스트 역방향 순회

강의

[프로그래머스] 어서와! 자료구조와 알고리즘은 처음이지? - Python

 

 

문제

 

제 10 강에서 소개된 추상적 자료구조 DoublyLinkedList 에 대하여, 또한 강의 내용에서 언급한 reverse() 메서드를 구현하세요.

이 reverse() 메서드는 양방향 연결 리스트를 끝에서부터 시작해서 맨 앞에 도달할 때까지 (tail 방향에서 head 방향으로) 순회하면서, 방문하게 되는 node 에 들어 있는 data item 을 순회 순서에 따라 리스트에 담아 리턴합니다.

예를 들어, DoublyLinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [62, 85, 43] 입니다.

이 규칙을 적용하면, 빈 연결 리스트에 대한 역방향 순회 결과로 reverse() 메서드라 리턴해야 할 올바른 결과는 [] 입니다.

 

💬 요구 사항

- dummy head, dummy tail을 갖는 양방향 연결 리스트를 tail에서부터 순회해서 리스트로 리턴

 

 

 

풀이

 

내 풀이 | dummy head를 가지는 경우 

 

    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev :
            curr = curr.prev
            result.append(curr.data)
        return result

💬 Comment

이전과 다르게 surr.prev.prev로 조건이 붙는 이유는 dummy head가 있기 때문이다.