[코테 적용] 연결리스트 구현

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

코테 적용 방법

Linked List의 다양한 활용
1. Linked List 자유자재로 구현 (선형 자료구조 + 중간에 데이터 추가/삭제 해야하는 문제)
2. Tree or Graph에 활용

문제 보는 방법

• input, output 확인
  • input 값의 특징 (정수인가? 값 크기의 범위는? 마이너스도 되는건가? 소수인가? 자료형은 문자열인가? 등등
  • output 값의 특징 (내가 어떤 값을 반환해줘야 하는지, 정해진 형식대로 반환하려면 어떻게 구현할지)
• input size N 확인
  • 시간복잡도를 계산하기 위한 input size N 또는 M이 무엇인지 확인
• 제약조건 확인
  • 시간복잡도 제한이 있는지 확인
  • 내가 선택할 수 있는 알고리즘이 무엇이 있는지
• 예상할 수 있는 오류 파악
  • 상황을 가정하면서 예상할 수 있는 오류를 파악한다.
  • 입력값의 범위, stack overflow 등등

기본 문제

(https://leetcode.com/problems/design-browser-history/)

• 순서가 있는 선형 자료구조를 써야겠구나
  • list(Array, Linked List)

class ListNode:
    def __init__(self, value=0, next=None, prev=None):
        self.value = value
        self.next = next
        self.prev = prev

class BrowserHistory:
    def __init__(self, homepage):
        self.head = self.current = ListNode(value=homepage)
    
    def visit(self, url):
        # 새 노드를 현재 노드의 다음에 연결하고 현재 노드를 새 노드로 업데이트합니다.
        self.current.next = ListNode(value=url, prev=self.current)
        self.current = self.current.next
        return None
    
    def back(self, steps):
        # steps 만큼 뒤로 이동하며 현재 노드를 갱신합니다.
        while steps > 0 and self.current.prev is not None:
            steps -= 1
            self.current = self.current.prev
        return self.current.value
    
    def forward(self, steps):
        # steps 만큼 앞으로 이동하며 현재 노드를 갱신합니다.
        while steps > 0 and self.current.next is not None:
            steps -= 1
            self.current = self.current.next
        return self.current.value


browserHistory = BrowserHistory("leetcode.com")
browserHistory.visit("google.com")
browserHistory.visit("facebook.com")
browserHistory.visit("youtube.com")
print(browserHistory.back(1))       # "facebook.com"
print(browserHistory.back(1))       # "google.com"
print(browserHistory.forward(1))    # "facebook.com"
browserHistory.visit("linkedin.com")
print(browserHistory.forward(2))    # "linkedin.com"
print(browserHistory.back(2))       # "google.com"
print(browserHistory.back(7))       # "leetcode.com"

추가

1. head는 코드 내 한번도 사용하지 않아서 안 써도 된다.
2. head = tail = Node() 로 구현해야 같은 노드를 가르킨다.