LIFO/FIFO 및 Pointer 구조 설계를 통한 브라우저 히스토리 시스템 구현

Context

Python 내장 자료구조인 dict, set, list의 단순 활용에서 벗어나 데이터 구조의 내부 동작 원리 파악이 필요함. 특히 단순 리스트 기반의 큐 구현 시 발생하는 시간 복잡도 저하 문제를 해결하기 위한 최적의 구조 설계가 요구됨.

Technical Solution

• LIFO 특성을 활용하여 괄호 유효성 검사 및 브라우저 '뒤로 가기' 로직을 처리하는 Stack 구조 설계
• deque.popleft()를 적용하여 일반 리스트의 O(n) 시간 복잡도를 O(1)로 개선한 FIFO Queue 구현
• Node 클래스의 포인터 연결을 통한 동적 메모리 할당 기반의 Linked List 설계
• Dummy Node 패턴을 도입하여 리스트 병합 및 삽입 시 발생하는 Edge Case 처리 로직 단순화
• Fast/Slow Pointer 기법을 적용하여 리스트 길이를 사전 파악하지 않고도 특정 지점을 탐색하는 알고리즘 구현
• 두 개의 Stack을 조합하여 방문 기록의 Truncate-on-new-visit 동작을 처리하는 브라우저 히스토리 트래커 구축