linkedList - BrowserHistory 코드 질문

Question

안녕하세요 linkedList에서 BrowserHistory 코드를 구현할 때 저는 처음 linkedList 개념에서 생각했던 대로 linkedList + idx 로 접근하는 방향으로 생각했습니다. # idx로 생각한 예시 # O(n) def insert(self, idx): current = self.head NewNode = Node() # insert하려는 앞 노드까지 for i in range(idx - 1): current = current.next NewNode.next = current.next current.next = NewNode 그런데, BrowserHistory에선 linkedList + class 속성?(current)으로 풀이를 하신 것 같은데 맞을까요? 문제 풀이할 때, visit을 할때마다 현재 idx를 global 변수로 저장해둬야 하나?라는 고민을 했어서 혹시 잘못 생각한 부분이 있는지 알려주시면 감사하겠습니다..!

friedhamn · Answer

안녕하세요, wan님.   맞습니다. BrowserHistory에서 visit 메서드는 속성인 current를 사용하여 O(1)의 시간복잡도로 현재 노드에 바로 접근하고 다음 노드를 추가합니다. (back과 forward 메서드에서 current 값을 조정합니다)   만약 current 속성을 할당하지 않았다면 index 값을 속성을 할당한 후 접근을 해야하기 때문에 O(n)의 시간복잡도가 될 수 있습니다.   이해가 안되는 부분이 있다면 언제든 질문 주시기 바랍니다. 감사합니다.