1472-design-browser-history.py

# Linked List Implementation
classListNode:
def__init__(self, val, prev=None, next=None):
self.val=val
self.prev=prev
self.next=next

classBrowserHistory:
def__init__(self, homepage: str):
self.cur=ListNode(homepage)

# O(1)
defvisit(self, url: str) ->None:
self.cur.next=ListNode(url, self.cur)
self.cur=self.cur.next

# O(n)
defback(self, steps: int) ->str:
whileself.cur.prevandsteps>0:
self.cur=self.cur.prev
steps-=1
returnself.cur.val

# O(n)
defforward(self, steps: int) ->str:
whileself.cur.nextandsteps>0:
self.cur=self.cur.next
steps-=1
returnself.cur.val


# Array Implementation
classBrowserHistory: 
def__init__(self, homepage: str):
self.i=0
self.len=1
self.history= [homepage]

# O(1)
defvisit(self, url: str) ->None:
iflen(self.history) <self.i+2:
self.history.append(url)
else:
self.history[self.i+1] =url
self.i+=1
self.len=self.i+1

# O(1)
defback(self, steps: int) ->str:
self.i=max(self.i-steps, 0)
returnself.history[self.i]

# O(1)
defforward(self, steps: int) ->str:
self.i=min(self.i+steps, self.len-1)
returnself.history[self.i]