이중 연결 리스트 - 앞뒤로 연결된 줄

노드(node) = 데이터 + 화살표 2개(prev: 앞 사람, next: 뒷 사람). 이 노드들이 앞뒤로 손을 잡은 형태가 이중 연결 리스트입니다.

None ← [A] ⇄ [B] ⇄ [C] → None
      head              tail

왜 LRU에 이걸 쓰나?

"가장 최근에 쓴 것"을 항상 맨 앞(head 근처)에 두고 싶을 때:

• 맨 앞에 삽입(insert_front): 새 노드가 head와 그 다음 노드의 화살표만 바꾸면 됨 → O(1)
• 특정 노드 제거(remove_node): 이미 그 노드를 갖고 있으면, 앞뒤 노드의 화살표만 서로 이어주면 됨 → O(1)
• 맨 앞으로 이동(move_to_front): 제거했다가 맨 앞에 삽입 → O(1)

일반 배열(list)은 가운데 원소를 빼면 뒤의 것들을 전부 당겨야 해서 O(n)입니다. 화살표만 바꾸는 연결 리스트는 자리 이동이 없어서 O(1)인 게 핵심입니다.

class Node:
    """이중 연결 리스트의 칸 하나"""
    def __init__(self, data):
        self.prev = None   # 앞 노드
        self.next = None   # 뒷 노드
        self.data = data   # 실제 값

---

출처: Codyssey-B1/B5-1