Linked Lists: Cấu trúc Dữ liệu Tuần tự Động

// TypeScript - Singly Linked List Node
class ListNode<T> {
  val: T;
  next: ListNode<T> | null;
 
  constructor(val: T, next: ListNode<T> | null = null) {
    this.val = val;
    this.next = next;
  }
}

# Python - Singly Linked List Node
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

// TypeScript - Singly Linked List
class SinglyLinkedList<T> {
  head: ListNode<T> | null = null;
  size: number = 0;
 
  // Chèn vào đầu - O(1)
  prepend(val: T): void {
    const newNode = new ListNode(val, this.head);
    this.head = newNode;
    this.size++;
  }
 
  // Chèn vào cuối - O(n)
  append(val: T): void {
    const newNode = new ListNode(val);
 
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }
 
  // Chèn vào vị trí cụ thể - O(n)
  insertAt(val: T, index: number): void {
    if (index < 0 || index > this.size) {
      throw new Error("Index out of bounds");
    }
    if (index === 0) {
      this.prepend(val);
      return;
    }
 
    const newNode = new ListNode(val);
    let current = this.head;
    for (let i = 0; i < index - 1; i++) {
      current = current!.next;
    }
    newNode.next = current!.next;
    current!.next = newNode;
    this.size++;
  }
 
  // Xóa theo giá trị - O(n)
  delete(val: T): boolean {
    if (!this.head) return false;
 
    // Nếu node head chứa giá trị
    if (this.head.val === val) {
      this.head = this.head.next;
      this.size--;
      return true;
    }
 
    let current = this.head;
    while (current.next) {
      if (current.next.val === val) {
        current.next = current.next.next;
        this.size--;
        return true;
      }
      current = current.next;
    }
    return false;
  }
 
  // Xóa theo index - O(n)
  deleteAt(index: number): T {
    if (index < 0 || index >= this.size) {
      throw new Error("Index out of bounds");
    }
 
    let removedVal: T;
    if (index === 0) {
      removedVal = this.head!.val;
      this.head = this.head!.next;
    } else {
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
        current = current!.next;
      }
      removedVal = current!.next!.val;
      current!.next = current!.next!.next;
    }
    this.size--;
    return removedVal;
  }
 
  // Tìm kiếm - O(n)
  search(val: T): number {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.val === val) return index;
      current = current.next;
      index++;
    }
    return -1; // Không tìm thấy
  }
 
  // Lấy giá trị theo index - O(n)
  get(index: number): T {
    if (index < 0 || index >= this.size) {
      throw new Error("Index out of bounds");
    }
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current!.next;
    }
    return current!.val;
  }
 
  // In danh sách
  print(): string {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.val);
      current = current.next;
    }
    return values.join(" -> ") + " -> null";
  }
}
 
// Sử dụng
const list = new SinglyLinkedList<number>();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);
console.log(list.print());  // 5 -> 10 -> 20 -> 30 -> null
list.insertAt(15, 2);
console.log(list.print());  // 5 -> 10 -> 15 -> 20 -> 30 -> null
list.delete(15);
console.log(list.print());  // 5 -> 10 -> 20 -> 30 -> null

# Python - Singly Linked List
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
 
    # Chèn vào đầu - O(1)
    def prepend(self, val):
        new_node = ListNode(val, self.head)
        self.head = new_node
        self.size += 1
 
    # Chèn vào cuối - O(n)
    def append(self, val):
        new_node = ListNode(val)
 
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1
 
    # Chèn vào vị trí cụ thể - O(n)
    def insert_at(self, val, index):
        if index < 0 or index > self.size:
            raise IndexError("Index out of bounds")
        if index == 0:
            self.prepend(val)
            return
 
        new_node = ListNode(val)
        current = self.head
        for _ in range(index - 1):
            current = current.next
        new_node.next = current.next
        current.next = new_node
        self.size += 1
 
    # Xóa theo giá trị - O(n)
    def delete(self, val):
        if not self.head:
            return False
 
        if self.head.val == val:
            self.head = self.head.next
            self.size -= 1
            return True
 
        current = self.head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        return False
 
    # Tìm kiếm - O(n)
    def search(self, val):
        current = self.head
        index = 0
        while current:
            if current.val == val:
                return index
            current = current.next
            index += 1
        return -1
 
    # In danh sách
    def print_list(self):
        values = []
        current = self.head
        while current:
            values.append(str(current.val))
            current = current.next
        return " -> ".join(values) + " -> None"
 
 
# Sử dụng
lst = SinglyLinkedList()
lst.append(10)
lst.append(20)
lst.append(30)
lst.prepend(5)
print(lst.print_list())  # 5 -> 10 -> 20 -> 30 -> None
lst.insert_at(15, 2)
print(lst.print_list())  # 5 -> 10 -> 15 -> 20 -> 30 -> None
lst.delete(15)
print(lst.print_list())  # 5 -> 10 -> 20 -> 30 -> None

// TypeScript - Doubly Linked List Node
class DoublyNode<T> {
  val: T;
  next: DoublyNode<T> | null;
  prev: DoublyNode<T> | null;
 
  constructor(val: T) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

# Python - Doubly Linked List Node
class DoublyNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None
        self.prev = None

// TypeScript - Doubly Linked List
class DoublyLinkedList<T> {
  head: DoublyNode<T> | null = null;
  tail: DoublyNode<T> | null = null;
  size: number = 0;
 
  // Chèn vào đầu - O(1)
  prepend(val: T): void {
    const newNode = new DoublyNode(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.size++;
  }
 
  // Chèn vào cuối - O(1) với tail pointer!
  append(val: T): void {
    const newNode = new DoublyNode(val);
    if (!this.tail) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }
 
  // Xóa node - O(1) khi có tham chiếu node
  deleteNode(node: DoublyNode<T>): void {
    if (node.prev) {
      node.prev.next = node.next;
    } else {
      this.head = node.next; // Đang xóa head
    }
 
    if (node.next) {
      node.next.prev = node.prev;
    } else {
      this.tail = node.prev; // Đang xóa tail
    }
    this.size--;
  }
 
  // Xóa từ đầu - O(1)
  deleteFirst(): T | null {
    if (!this.head) return null;
    const val = this.head.val;
    this.deleteNode(this.head);
    return val;
  }
 
  // Xóa từ cuối - O(1) với tail pointer!
  deleteLast(): T | null {
    if (!this.tail) return null;
    const val = this.tail.val;
    this.deleteNode(this.tail);
    return val;
  }
 
  // In tiến
  printForward(): string {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.val);
      current = current.next;
    }
    return "null <-> " + values.join(" <-> ") + " <-> null";
  }
 
  // In lùi
  printBackward(): string {
    const values: T[] = [];
    let current = this.tail;
    while (current) {
      values.push(current.val);
      current = current.prev;
    }
    return "null <-> " + values.join(" <-> ") + " <-> null";
  }
}
 
// Sử dụng
const dll = new DoublyLinkedList<number>();
dll.append(10);
dll.append(20);
dll.append(30);
dll.prepend(5);
console.log(dll.printForward());   // null <-> 5 <-> 10 <-> 20 <-> 30 <-> null
console.log(dll.printBackward());  // null <-> 30 <-> 20 <-> 10 <-> 5 <-> null
dll.deleteLast();
console.log(dll.printForward());   // null <-> 5 <-> 10 <-> 20 <-> null

# Python - Doubly Linked List
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
 
    def prepend(self, val):
        new_node = DoublyNode(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.size += 1
 
    def append(self, val):
        new_node = DoublyNode(val)
        if not self.tail:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
 
    def delete_node(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
 
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self.size -= 1
 
    def delete_first(self):
        if not self.head:
            return None
        val = self.head.val
        self.delete_node(self.head)
        return val
 
    def delete_last(self):
        if not self.tail:
            return None
        val = self.tail.val
        self.delete_node(self.tail)
        return val
 
    def print_forward(self):
        values = []
        current = self.head
        while current:
            values.append(str(current.val))
            current = current.next
        return "None <-> " + " <-> ".join(values) + " <-> None"
 
 
# Sử dụng
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.prepend(5)
print(dll.print_forward())  # None <-> 5 <-> 10 <-> 20 <-> 30 <-> None
dll.delete_last()
print(dll.print_forward())  # None <-> 5 <-> 10 <-> 20 <-> None

// TypeScript - Kiểm tra Circular Linked List
function isCircular<T>(head: ListNode<T> | null): boolean {
  if (!head) return false;
 
  let current = head.next;
  while (current && current !== head) {
    current = current.next;
  }
  return current === head;
}

# Python - Kiểm tra Circular Linked List
def is_circular(head):
    if not head:
        return False
 
    current = head.next
    while current and current != head:
        current = current.next
    return current == head

// Không dùng dummy head - phải xử lý head riêng
function deleteValue<T>(head: ListNode<T> | null, val: T): ListNode<T> | null {
  // Trường hợp đặc biệt: head chứa giá trị
  while (head && head.val === val) {
    head = head.next;
  }
 
  let current = head;
  while (current && current.next) {
    if (current.next.val === val) {
      current.next = current.next.next;
    } else {
      current = current.next;
    }
  }
  return head;
}
 
// Với dummy head - logic sạch, thống nhất
function deleteValueClean<T>(head: ListNode<T> | null, val: T): ListNode<T> | null {
  const dummy = new ListNode(0 as T, head); // Node giả trước head
  let current = dummy;
 
  while (current.next) {
    if (current.next.val === val) {
      current.next = current.next.next;
    } else {
      current = current.next;
    }
  }
  return dummy.next; // Head thật
}

# Python - Kỹ thuật Dummy head
def delete_value_clean(head, val):
    dummy = ListNode(0, head)
    current = dummy
 
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
 
    return dummy.next

// TypeScript - Đảo ngược Linked List (Lặp)
function reverseList(head: ListNode<number> | null): ListNode<number> | null {
  let prev: ListNode<number> | null = null;
  let current = head;
 
  while (current) {
    const next = current.next;  // Lưu next
    current.next = prev;        // Đảo con trỏ
    prev = current;             // Tiến prev
    current = next;             // Tiến current
  }
 
  return prev; // Head mới
}
 
// Time: O(n) | Space: O(1)

# Python - Đảo ngược Linked List (Lặp)
def reverse_list(head):
    prev = None
    current = head
 
    while current:
        next_node = current.next  # Lưu next
        current.next = prev       # Đảo con trỏ
        prev = current            # Tiến prev
        current = next_node       # Tiến current
 
    return prev  # Head mới
 
# Time: O(n) | Space: O(1)

// TypeScript - Đảo ngược Linked List (Đệ quy)
function reverseListRecursive(head: ListNode<number> | null): ListNode<number> | null {
  // Trường hợp cơ sở: list rỗng hoặc một node
  if (!head || !head.next) {
    return head;
  }
 
  // Đệ quy đảo ngược phần còn lại
  const newHead = reverseListRecursive(head.next);
 
  // Đảo con trỏ
  head.next.next = head;  // Node sau head trỏ ngược lại head
  head.next = null;       // Head bây giờ trỏ đến null
 
  return newHead;
}
 
// Time: O(n) | Space: O(n) do call stack

# Python - Đảo ngược Linked List (Đệ quy)
def reverse_list_recursive(head):
    # Trường hợp cơ sở
    if not head or not head.next:
        return head
 
    # Đệ quy đảo ngược phần còn lại
    new_head = reverse_list_recursive(head.next)
 
    # Đảo con trỏ
    head.next.next = head
    head.next = None
 
    return new_head
 
# Time: O(n) | Space: O(n) do call stack

// TypeScript - Phát hiện Cycle (LeetCode 141)
function hasCycle(head: ListNode<number> | null): boolean {
  let slow = head;
  let fast = head;
 
  while (fast && fast.next) {
    slow = slow!.next;        // 1 bước
    fast = fast.next.next;    // 2 bước
 
    if (slow === fast) {
      return true; // Phát hiện cycle
    }
  }
 
  return false; // Không có cycle (fast đến cuối)
}
 
// Time: O(n) | Space: O(1)

# Python - Phát hiện Cycle (LeetCode 141)
def has_cycle(head):
    slow = head
    fast = head
 
    while fast and fast.next:
        slow = slow.next       # 1 bước
        fast = fast.next.next  # 2 bước
 
        if slow == fast:
            return True  # Phát hiện cycle
 
    return False  # Không có cycle
 
# Time: O(n) | Space: O(1)

// TypeScript - Tìm Điểm Bắt đầu Cycle (LeetCode 142)
function detectCycle(head: ListNode<number> | null): ListNode<number> | null {
  let slow = head;
  let fast = head;
 
  // Bước 1: Phát hiện cycle
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
 
    if (slow === fast) {
      // Bước 2: Tìm điểm bắt đầu cycle
      let pointer = head;
      while (pointer !== slow) {
        pointer = pointer!.next;
        slow = slow!.next;
      }
      return pointer; // Điểm bắt đầu cycle
    }
  }
 
  return null; // Không có cycle
}

# Python - Tìm Điểm Bắt đầu Cycle (LeetCode 142)
def detect_cycle(head):
    slow = head
    fast = head
 
    # Bước 1: Phát hiện cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
        if slow == fast:
            # Bước 2: Tìm điểm bắt đầu cycle
            pointer = head
            while pointer != slow:
                pointer = pointer.next
                slow = slow.next
            return pointer  # Điểm bắt đầu cycle
 
    return None  # Không có cycle

// TypeScript - Tìm Node Giữa
function middleNode(head: ListNode<number> | null): ListNode<number> | null {
  let slow = head;
  let fast = head;
 
  while (fast && fast.next) {
    slow = slow!.next;      // 1 bước
    fast = fast.next.next;  // 2 bước
  }
 
  return slow; // Node giữa
}
 
// Với [1, 2, 3, 4, 5] → trả về node 3
// Với [1, 2, 3, 4, 5, 6] → trả về node 4 (node giữa thứ hai)

# Python - Tìm Node Giữa
def middle_node(head):
    slow = head
    fast = head
 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    return slow
 
# Time: O(n) | Space: O(1)

// TypeScript - Merge Two Sorted Lists
function mergeTwoLists(
  l1: ListNode<number> | null,
  l2: ListNode<number> | null
): ListNode<number> | null {
  const dummy = new ListNode(0);
  let current = dummy;
 
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }
 
  // Gắn các nodes còn lại
  current.next = l1 || l2;
 
  return dummy.next;
}
 
// Time: O(n + m) | Space: O(1) — tái sử dụng nodes hiện có

# Python - Merge Two Sorted Lists
def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    current = dummy
 
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
 
    # Gắn các nodes còn lại
    current.next = l1 if l1 else l2
 
    return dummy.next
 
# Time: O(n + m) | Space: O(1)

// TypeScript - Xóa Node thứ N từ Cuối
function removeNthFromEnd(
  head: ListNode<number> | null,
  n: number
): ListNode<number> | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode<number> | null = dummy;
  let slow: ListNode<number> | null = dummy;
 
  // Di chuyển con trỏ fast trước n+1 bước
  for (let i = 0; i <= n; i++) {
    fast = fast!.next;
  }
 
  // Di chuyển cả hai cho đến khi fast đến cuối
  while (fast) {
    fast = fast.next;
    slow = slow!.next;
  }
 
  // Bỏ qua node target
  slow!.next = slow!.next!.next;
 
  return dummy.next;
}
 
// Time: O(n) | Space: O(1)

# Python - Xóa Node thứ N từ Cuối
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy
 
    # Di chuyển con trỏ fast trước n+1 bước
    for _ in range(n + 1):
        fast = fast.next
 
    # Di chuyển cả hai cho đến khi fast đến cuối
    while fast:
        fast = fast.next
        slow = slow.next
 
    # Bỏ qua node target
    slow.next = slow.next.next
 
    return dummy.next
 
# Time: O(n) | Space: O(1)

// TypeScript - Palindrome Linked List
function isPalindrome(head: ListNode<number> | null): boolean {
  if (!head || !head.next) return true;
 
  // Bước 1: Tìm giữa
  let slow: ListNode<number> | null = head;
  let fast: ListNode<number> | null = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
 
  // Bước 2: Đảo ngược nửa sau
  let prev: ListNode<number> | null = null;
  let current = slow;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
 
  // Bước 3: So sánh hai nửa
  let left: ListNode<number> | null = head;
  let right: ListNode<number> | null = prev;
  while (right) {
    if (left!.val !== right.val) return false;
    left = left!.next;
    right = right.next;
  }
 
  return true;
}
 
// Time: O(n) | Space: O(1)

# Python - Palindrome Linked List
def is_palindrome(head):
    if not head or not head.next:
        return True
 
    # Bước 1: Tìm giữa
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    # Bước 2: Đảo ngược nửa sau
    prev = None
    current = slow
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
 
    # Bước 3: So sánh hai nửa
    left = head
    right = prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
 
    return True
 
# Time: O(n) | Space: O(1)

// TypeScript - Giao điểm hai Linked Lists
function getIntersectionNode(
  headA: ListNode<number> | null,
  headB: ListNode<number> | null
): ListNode<number> | null {
  let pA = headA;
  let pB = headB;
 
  while (pA !== pB) {
    pA = pA ? pA.next : headB;
    pB = pB ? pB.next : headA;
  }
 
  return pA; // Node giao hoặc null
}
 
// Time: O(n + m) | Space: O(1)

# Python - Giao điểm hai Linked Lists
def get_intersection_node(head_a, head_b):
    p_a = head_a
    p_b = head_b
 
    while p_a != p_b:
        p_a = p_a.next if p_a else head_b
        p_b = p_b.next if p_b else head_a
 
    return p_a  # Node giao hoặc None
 
# Time: O(n + m) | Space: O(1)

// TypeScript - Reorder List
function reorderList(head: ListNode<number> | null): void {
  if (!head || !head.next) return;
 
  // Bước 1: Tìm giữa
  let slow: ListNode<number> | null = head;
  let fast: ListNode<number> | null = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
 
  // Bước 2: Đảo ngược nửa sau
  let prev: ListNode<number> | null = null;
  let current = slow!.next;
  slow!.next = null; // Tách list
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
 
  // Bước 3: Merge hai nửa xen kẽ
  let first: ListNode<number> | null = head;
  let second: ListNode<number> | null = prev;
  while (second) {
    const tmp1 = first!.next;
    const tmp2 = second.next;
    first!.next = second;
    second.next = tmp1;
    first = tmp1;
    second = tmp2;
  }
}
 
// Time: O(n) | Space: O(1)

# Python - Reorder List
def reorder_list(head):
    if not head or not head.next:
        return
 
    # Bước 1: Tìm giữa
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    # Bước 2: Đảo ngược nửa sau
    prev = None
    current = slow.next
    slow.next = None  # Tách list
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
 
    # Bước 3: Merge hai nửa xen kẽ
    first = head
    second = prev
    while second:
        tmp1 = first.next
        tmp2 = second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2
 
# Time: O(n) | Space: O(1)

// TypeScript - Luôn kiểm tra các edge cases này
function safeOperation(head: ListNode<number> | null): ListNode<number> | null {
  // Edge case 1: List rỗng
  if (!head) return null;
 
  // Edge case 2: Một node
  if (!head.next) return head;
 
  // Edge case 3: Hai nodes (edge case phổ biến cho đảo ngược, etc.)
  // ... logic của bạn ở đây
 
  return head;
}

// Lịch sử trình duyệt đơn giản hóa dùng doubly linked list
class BrowserHistory {
  private current: DoublyNode<string>;
 
  constructor(homepage: string) {
    this.current = new DoublyNode(homepage);
  }
 
  visit(url: string): void {
    const newPage = new DoublyNode(url);
    this.current.next = newPage;
    newPage.prev = this.current;
    this.current = newPage;
  }
 
  back(steps: number): string {
    while (steps > 0 && this.current.prev) {
      this.current = this.current.prev;
      steps--;
    }
    return this.current.val;
  }
 
  forward(steps: number): string {
    while (steps > 0 && this.current.next) {
      this.current = this.current.next;
      steps--;
    }
    return this.current.val;
  }
}

# Python - LRU Cache (LeetCode 146)
class LRUNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
 
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> node
 
        # Dummy head và tail
        self.head = LRUNode()
        self.tail = LRUNode()
        self.head.next = self.tail
        self.tail.prev = self.head
 
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
 
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add_to_front(node)
            return node.val
        return -1
 
    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
 
        node = LRUNode(key, value)
        self._add_to_front(node)
        self.cache[key] = node
 
        if len(self.cache) > self.capacity:
            # Xóa least recently used (từ tail)
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
 
# Sử dụng
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # 1
cache.put(3, 3)        # Loại bỏ key 2
print(cache.get(2))    # -1 (không tìm thấy)