Design Browser History

시간복잡도(Big-O)에 데이터의 크기를 넣어서 나온 값이 100,000,000(10^8)이 넘으면 시간 제한 초과할 가능성이 있다.

---

정수가 저장된 배열 nums이 주어졌을 떄, nums의 원소중 두 숫자를 더해서 target이 될수 있으면 True 불가능하면 False를 반환하세요.
같은 원소를 두 번 사용할 수 없습니다.

class Node {  
  var value: String  
  var prev: Node?  
  var next: Node?

  init(value: String) {
      self.value = value
  }
}

class BrowserHistory {  
  var head: Node  
  var current: Node

  init(_ homepage: String) {
      let newNode: Node = .init(value: homepage)
      head = newNode
      current = newNode
  }
  //O(1)
  func visit(_ url: String) {
          let newNode: Node = .init(value: url)
          current.next = newNode
          newNode.prev = current
          current = current.next!
  }

  //O(N)
  func back(_ steps: Int) -> String {
      for _ in 0 ..< steps {
          if current.prev != nil {
              current = current.prev!
          }
      }
      return (current.value)
  }

  //O(N)
  func forward(_ steps: Int) -> String {
      for _ in 0 ..< steps {
          if current.next != nil {
              current = current.next!
          }
      }
      return (current.value)
  }

}


1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage and url consist of  '.' or lower case English letters.
At most 5000 calls will be made to visit, back, and forward

해당 문제에서 시간복잡도에 영향을 끼치는 부분은 steps.count(100) * calls(5000) 이다. 10^5 이므로 10^8이 안넘기 위해 LinkedList 사용하였고,linkedList의 back, forward는 O(n)이므로 시간초과가 나지 않는다.