Danh sách liên kếtLinked Lists

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Linked list lưu một dãy dưới dạng chuỗi các node, mỗi node chứa một giá trị và một tham chiếu tới node kế tiếp. Khác với array, các node không cần nằm cạnh nhau trong bộ nhớ — chúng có thể nằm rải rác bất kỳ đâu trên heap, và chính các pointer next là thứ áp đặt thứ tự lên chúng.

Chỉ một thay đổi đó thôi đã lật ngược toàn bộ bảng độ phức tạp. Vì không còn tính liên tục, không còn công thức địa chỉ, nên muốn tới phần tử i phải đi qua i liên kết: truy cập trở thành O(n). Nhưng cũng vì không còn tính liên tục, chèn vào giữa hai node chỉ là ghi lại hai pointer và không gì khác: chèn tại một vị trí đã biết trở thành O(1), không dịch chuyển, không resize.

Linked list là ví dụ chuẩn mực để dạy thao tác pointer, và nó là nền tảng cho vài cấu trúc rất quan trọng trong thực tế — các chain trong hash table dùng separate chaining, các intrusive list bên trong scheduler và memory allocator của hệ điều hành, doubly linked list nằm ở lõi của một LRU cache, và chuỗi block (theo nghĩa nhàm chán của từ này) bên trong collections.deque.

Nhưng trong code ứng dụng, chúng hầu như luôn là lựa chọn sai. Note này sẽ dựng chúng cẩn thận rồi nói thẳng điều đó: trên phần cứng hiện đại, hành vi cache của việc đuổi theo pointer tệ tới mức array thắng ngay cả trong những tình huống mà lý thuyết tiệm cận nói nó không nên thắng. Biết chính xác khi nào linked list thực sự thắng thì hữu ích hơn là biết cách đảo ngược một cái — dù ta cũng sẽ làm điều đó, vì nó là câu hỏi phỏng vấn được hỏi nhiều nhất về linked list.

Kiến thức nền tảng

Singly linked list

   head
    |
    v
  +------+------+     +------+------+     +------+------+
  |  17  |  ----+---> |   3  |  ----+---> |  99  | None |
  +------+------+     +------+------+     +------+------+
   value   next        value   next        value   next

  Các node nằm ở địa chỉ heap tuỳ ý. Chỉ pointer mới áp đặt thứ tự.
  `next` của node cuối là None — đó là dấu kết thúc.

Toàn bộ cấu trúc chỉ tiếp cận được từ head. Mất head là mất cả list vào tay garbage collector.

class Node:
    """Một mắt xích: một giá trị cộng một tham chiếu tới node kế tiếp."""

    __slots__ = ("value", "next")                  # tiết kiệm bộ nhớ: bỏ __dict__ mỗi node

    def __init__(self, value, next=None):
        self.value = value
        self.next = next


class SinglyLinkedList:
    """Singly linked list có head, tail và size được cache lại."""

    def __init__(self, iterable=()):
        self.head = None
        self.tail = None                           # tail pointer giúp append thành O(1)
        self.size = 0
        for value in iterable:
            self.append(value)

    def __len__(self):
        return self.size

    def push_front(self, value):
        """O(1) — chính là lý do linked list tồn tại."""
        node = Node(value, self.head)
        self.head = node
        if self.tail is None:                      # list đang rỗng: head và tail trùng nhau
            self.tail = node
        self.size += 1
        return node

    def append(self, value):
        """O(1) chỉ vì ta giữ tail pointer; không có nó thì là O(n)."""
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1
        return node

    def pop_front(self):
        """O(1) — gỡ head ra và đẩy head tiến lên."""
        if self.head is None:
            raise IndexError("pop from empty list")
        node = self.head
        self.head = node.next
        if self.head is None:                      # list vừa trở thành rỗng
            self.tail = None
        self.size -= 1
        node.next = None                           # giúp GC, tránh liên kết chết
        return node.value

    def pop_back(self):
        """O(n) ngay cả khi có tail pointer: ta cần node NGAY TRƯỚC tail,
        mà singly linked list không có cách nào đi ngược lại."""
        if self.head is None:
            raise IndexError("pop from empty list")
        if self.head is self.tail:
            value = self.head.value
            self.head = self.tail = None
            self.size -= 1
            return value
        prev = self.head
        while prev.next is not self.tail:          # đi tới node áp chót
            prev = prev.next
        value = self.tail.value
        prev.next = None
        self.tail = prev
        self.size -= 1
        return value

    def find(self, value):
        """O(n) — không random access, không cách nào nhảy cóc."""
        node = self.head
        while node is not None:
            if node.value == value:
                return node
            node = node.next
        return None

    def remove(self, value):
        """O(n): phần đắt là tìm node đứng trước, không phải thao tác gỡ liên kết."""
        prev, node = None, self.head
        while node is not None:
            if node.value == value:
                if prev is None:
                    self.head = node.next
                else:
                    prev.next = node.next          # thao tác gỡ liên kết thật sự là O(1)
                if node is self.tail:
                    self.tail = prev
                self.size -= 1
                node.next = None
                return True
            prev, node = node, node.next
        return False

    def __iter__(self):
        node = self.head
        while node is not None:
            yield node.value
            node = node.next

    def __repr__(self):
        return " -> ".join(repr(v) for v in self) + " -> None"


lst = SinglyLinkedList([17, 3, 99])
lst.push_front(42)
print(lst)                 # 42 -> 17 -> 3 -> 99 -> None
lst.remove(3)
print(lst, len(lst))       # 42 -> 17 -> 99 -> None 3

Hãy để ý điều mà remove cho thấy: thao tác gỡ liên kết đúng là O(1), nhưng bạn đã phải đi O(n) để tìm ra node đứng trước. Tính chất insert/delete O(1) của linked list chỉ có được nếu bạn đã sẵn có tham chiếu tới đúng node đó. Chính điều kiện tiên quyết ấy làm linked list hữu ích trong LRU cache (hash table đưa node cho bạn) và vô dụng khi làm list đa dụng.

Doubly linked list

Thêm pointer prev và mỗi node biết cả hai hàng xóm. Xoá một node đã có sẵn trở thành O(1) thực sự — không phải đi tìm node trước — và list duyệt được theo cả hai chiều.

        head                                                  tail
         |                                                     |
         v                                                     v
      +------+----+----+   +------+----+----+   +------+----+----+
None<-+ prev | 17 |next+-->+ prev |  3 |next+-->+ prev | 99 |next+-->None
      +------+----+----+<--+------+----+----+<--+------+----+----+

Cái giá là thêm một pointer mỗi node (8 byte trên máy 64-bit) và kỷ luật giữ cho hai chiều nhất quán — một bug cập nhật next mà quên prev sẽ tạo ra list duyệt xuôi vẫn đúng và hỏng ngay lần duyệt ngược đầu tiên.

Sentinel node

Mọi method ở trên đều lộn xộn với if self.head is None và if prev is None. Chính những case đặc biệt đó là nơi bug ẩn nấp. Cách khắc phục là sentinel (node giả): một node cố định không bao giờ thuộc về dữ liệu nhưng luôn nằm ở biên, khiến case “list rỗng” và “phần tử đầu tiên” thôi không còn là case đặc biệt nữa.

   Circular doubly linked list với một sentinel:

        +--------------------------------------------------+
        |                                                   |
        v                                                   |
   +---------+     +------+     +------+     +------+       |
   | SENTINEL| <-> |  17  | <-> |   3  | <-> |  99  | <-----+
   +---------+     +------+     +------+     +------+
        ^                                        |
        +----------------------------------------+

   List rỗng:   SENTINEL.next == SENTINEL.prev == SENTINEL
   Không có kiểm tra None ở đâu cả. Mọi insert và delete đều là cùng ba dòng.

class DNode:
    """Node hai chiều: giá trị cộng cả hai hàng xóm."""

    __slots__ = ("value", "prev", "next")

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


class DoublyLinkedList:
    """Circular doubly linked list có sentinel — không kiểm tra None, không case biên."""

    def __init__(self, iterable=()):
        self._sentinel = DNode()                   # tự trỏ vào chính nó khi rỗng
        self.size = 0
        for value in iterable:
            self.append(value)

    def __len__(self):
        return self.size

    def _insert_between(self, value, left, right):
        """Nguyên thuỷ thứ nhất: chèn node mới giữa hai node đã biết. O(1)."""
        node = DNode(value)
        node.prev, node.next = left, right
        left.next = node
        right.prev = node
        self.size += 1
        return node

    def _unlink(self, node):
        """Nguyên thuỷ thứ hai: gỡ một node ta đã có sẵn. O(1), không phải tìm kiếm."""
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None               # tách ra để tham chiếu cũ không đi ngược lại
        self.size -= 1
        return node.value

    def append(self, value):                       # O(1)
        return self._insert_between(value, self._sentinel.prev, self._sentinel)

    def push_front(self, value):                   # O(1)
        return self._insert_between(value, self._sentinel, self._sentinel.next)

    def pop_back(self):                            # O(1) — đây là thứ mà `prev` mua được
        if self.size == 0:
            raise IndexError("pop from empty list")
        return self._unlink(self._sentinel.prev)

    def pop_front(self):                           # O(1)
        if self.size == 0:
            raise IndexError("pop from empty list")
        return self._unlink(self._sentinel.next)

    def move_to_front(self, node):
        """O(1): gỡ ra rồi chèn lại. Thao tác cốt lõi của một LRU cache."""
        node.prev.next = node.next
        node.next.prev = node.prev
        first = self._sentinel.next
        node.prev, node.next = self._sentinel, first
        self._sentinel.next = node
        first.prev = node

    def __iter__(self):
        node = self._sentinel.next
        while node is not self._sentinel:          # sentinel chính là điều kiện dừng
            yield node.value
            node = node.next

    def __reversed__(self):
        node = self._sentinel.prev
        while node is not self._sentinel:
            yield node.value
            node = node.prev

    def __repr__(self):
        return "[" + " <-> ".join(repr(v) for v in self) + "]"


dll = DoublyLinkedList([17, 3, 99])
dll.push_front(42)
print(dll)                     # [42 <-> 17 <-> 3 <-> 99]
print(list(reversed(dll)))     # [99, 3, 17, 42]
print(dll.pop_back(), dll)     # 99 [42 <-> 17 <-> 3]

So sánh _insert_between và _unlink với phiên bản singly linked. Không có một câu if nào trong cả hai. Đó chính là toàn bộ ý nghĩa của sentinel, và đó là thiết kế được dùng bởi list_head của Linux kernel, bởi std::list của C++, và bởi gần như mọi doubly linked list trong production.

Circular linked list

Circular list không có dấu kết thúc None — node cuối trỏ ngược về node đầu. Phiên bản sentinel ở trên vốn đã là circular. Ứng dụng:

• Round-robin scheduling. Giữ một pointer duy nhất; đẩy nó tiến mãi là đi vòng qua tất cả thành viên.
• Ring buffer dựng từ node (dù circular buffer dựa trên array gần như luôn tốt hơn).
• Bài toán Josephus và các trò loại trừ tương tự.

Nguy cơ là bất kỳ vòng while node is not None nào cũng trở thành vòng lặp vô hạn. Circular list phải được duyệt dựa trên một mốc cố định (while node is not start), và đó chính xác là thứ sentinel cung cấp.

Khái niệm chính

Độ phức tạp — và so sánh với array

Thao tác	Singly linked	Doubly linked	Dynamic array	Ghi chú
Truy cập theo index i	O(n)	O(n)	O(1)	Khác biệt quyết định
Tìm theo giá trị	O(n)	O(n)	O(n)	Array thắng về hằng số (cache)
Chèn ở đầu	O(1)	O(1)	O(n)	Linked list thắng
Chèn ở cuối	O(1) nếu có tail ptr	O(1)	O(1) amortized	Hoà
Chèn sau một node đã biết	O(1)	O(1)	O(n)	Linked list thắng
Chèn tại index i	O(n)	O(n)	O(n)	Hoà — traversal tốn ngang việc dịch chuyển
Xoá ở đầu	O(1)	O(1)	O(n)	Linked list thắng
Xoá ở cuối	O(n)	O(1)	O(1)	Pointer prev là thứ cứu vãn
Xoá một node đã biết	O(n) (cần node trước)	O(1)	O(n)	Doubly linked thắng
Đảo ngược	O(n), O(1) bộ nhớ	O(n)	O(n)
Bộ nhớ mỗi phần tử	giá trị + 1 pointer + object header	giá trị + 2 pointer + header	giá trị (+ ≤100% phần dư)	Array thắng đậm
Hành vi cache	Kém — đuổi theo pointer	Kém	Xuất sắc	Xem bên dưới
Không gian	O(n)	O(n)	O(n)	Hằng số chênh ~3×

Dòng quan trọng nhất lại không nằm trong bảng: hằng số. Một object Node của CPython có __slots__ tốn khoảng 56 byte để chứa một tham chiếu số nguyên. Cũng số nguyên đó trong một list tốn 8 byte pointer. Đó là chênh lệch 7× về bộ nhớ, và mỗi node nằm ở một địa chỉ không đoán trước được, nên duyệt list là một cache miss mỗi phần tử (~80 ns) so với khoảng một miss mỗi 8 phần tử với list (~10 ns amortized).

Nói thẳng ra: quét một list 1000 phần tử thường nhanh hơn quét một linked list 1000 phần tử với hệ số rất lớn, và một lần chèn O(n) vào array 1000 phần tử thường vẫn nhanh hơn cả lần traversal O(n) cần thiết để tìm ra vị trí chèn trong linked list. Bài trình bày nổi tiếng của Bjarne Stroustrup về chuyện này (“Why you should avoid linked lists”) đáng xem một lần.

Khi nào linked list thực sự thắng array

Hiếm, nhưng không phải không bao giờ. Những trường hợp thật:

1. Bạn đã sẵn có pointer tới node. Đây là trường hợp lớn nhất. Trong LRU cache, hash table ánh xạ key → node, nên việc đưa một entry lên vị trí mới-dùng-nhất là O(1) và không phải tìm kiếm gì cả. Array hoàn toàn không làm được điều này.
2. Splice cả một đoạn con. Chuyển một đoạn k node từ list này sang list khác là O(1) với linked list (nối lại 4 pointer) và O(n) với array. std::list::splice tồn tại vì lý do này.
3. Tham chiếu phải giữ nguyên giá trị qua các lần thay đổi. Một lần resize của vector/list làm vô hiệu mọi pointer và index vào nó; địa chỉ node của linked list thì không bao giờ đổi chỗ. Các cấu trúc trong kernel dựa nhiều vào tính chất này — một list_head intrusive nhúng trong một struct vẫn hoạt động dù list làm gì đi nữa.
4. Tăng trưởng không giới hạn mà không có khoảng dừng để cấp phát lại. Lần resize O(n) của dynamic array là một cú tăng vọt latency. Linked list không có cú tăng vọt đó, điều này quan trọng với hard real-time và với các allocator không thể xin nổi một khối liên tục lớn.
5. Bạn thực sự không thể cấp phát liên tục. Memory allocator và free list của filesystem nối các block lại chính vì khối liên tục là thứ chúng đang cố tạo ra.

Lưu ý rằng “tôi cần một queue” không nằm trong danh sách này — circular buffer dựa trên array hoặc một deque theo block đều tốt hơn. Và “tôi hay chèn vào giữa” thường cũng không nằm trong danh sách, vì tìm ra chỗ giữa đã là O(n).

Đảo ngược linked list

Bài tập kinh điển. Ba pointer, một lượt duyệt, O(n) thời gian và O(1) bộ nhớ:

def reverse_iterative(head):
    """Đảo ngược tại chỗ. O(n) thời gian, O(1) bộ nhớ. Trả về head mới."""
    prev, node = None, head
    while node is not None:
        nxt = node.next        # lưu phần còn lại của list trước khi ghi đè `next`
        node.next = prev       # lật liên kết này về phía sau
        prev, node = node, nxt # đẩy cả hai pointer tiến lên
    return prev                # `node` giờ là None, nên `prev` là node cuối = head mới

   Từng bước trên 1 -> 2 -> 3 -> None

   prev=None  node=1        1 -> 2 -> 3 -> None
   sau đó:    prev=1 node=2  None <- 1    2 -> 3 -> None
   sau đó:    prev=2 node=3  None <- 1 <- 2    3 -> None
   sau đó:    prev=3 node=None  None <- 1 <- 2 <- 3
   return prev = 3

Phiên bản đệ quy thì thanh lịch và, trong Python, là một quả stack overflow chờ sẵn — giới hạn đệ quy mặc định là 1000, nên nó vỡ với bất kỳ list nào dài hơn thế. Xem đệ quy.

def reverse_recursive(head):
    """O(n) thời gian, O(n) bộ nhớ STACK. Hỏng với list dài trong Python (recursion limit)."""
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)        # đảo ngược toàn bộ phần sau head
    head.next.next = head                          # bắt node kế tiếp trỏ ngược về ta
    head.next = None                               # rồi cắt liên kết xuôi của ta
    return new_head

Phát hiện chu trình — thuật toán rùa và thỏ của Floyd

Một linked list có chu trình thì không có dấu kết thúc None, nên duyệt ngây thơ sẽ không bao giờ dừng. Phát hiện điều này bằng một set các node đã thăm là O(n) thời gian nhưng O(n) bộ nhớ. Thuật toán Floyd làm được trong O(n) thời gian và O(1) bộ nhớ bằng hai pointer chạy với tốc độ khác nhau.

   1 -> 2 -> 3 -> 4 -> 5
             ^         |
             +---------+

   slow đi 1 bước, fast đi 2. Bên trong chu trình, fast rút ngắn khoảng cách
   với slow đúng 1 vị trí mỗi vòng, nên cuối cùng nó phải đáp trúng slow.
   Một khoảng cách giảm đi 1 mỗi bước thì không thể nhảy qua số 0.

def has_cycle(head):
    """Phát hiện chu trình kiểu Floyd. O(n) thời gian, O(1) bộ nhớ."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next                           # 1 bước
        fast = fast.next.next                      # 2 bước
        if slow is fast:                           # chúng chỉ có thể gặp nhau trong chu trình
            return True
    return False                                   # fast rơi khỏi cuối list -> không có chu trình


def cycle_start(head):
    """Tìm node đầu tiên của chu trình, hoặc None. O(n) thời gian, O(1) bộ nhớ."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            # Khoảng cách từ head tới đầu chu trình == khoảng cách từ điểm gặp nhau
            # tới đầu chu trình (đi xuôi). Cho cả hai đi cùng tốc độ.
            probe = head
            while probe is not slow:
                probe, slow = probe.next, slow.next
            return probe
    return None


def cycle_length(meeting_node):
    """Sau khi hai pointer đã gặp nhau, đếm độ dài chu trình. O(độ dài chu trình)."""
    count, node = 1, meeting_node.next
    while node is not meeting_node:
        count += 1
        node = node.next
    return count

Vì sao mẹo tìm đầu chu trình lại đúng. Gọi L là khoảng cách từ head tới đầu chu trình và C là độ dài chu trình. Khi chúng gặp nhau, slow đã đi d bước và fast đã đi 2d, nên fast đã đi nhiều hơn đúng d, và phần dôi ra đó phải là một số nguyên lần vòng: d = kC. Điểm gặp nhau do đó nằm cách đầu chu trình d − L = kC − L bước tính từ đầu chu trình, tức là L bước trước đầu chu trình (theo mod C). Cho một pointer đi từ head và một pointer đi từ điểm gặp nhau, mỗi lần một bước, chúng va vào nhau đúng tại đầu chu trình.

Mẫu hình này tổng quát hoá xa hơn linked list rất nhiều — nó phát hiện chu trình trong bất kỳ hàm “trạng thái kế tiếp” nào, đó là cách nó tìm phần tử trùng lặp trong một array n+1 số nguyên thuộc [1, n] và là cách thuật toán phân tích thừa số Pollard’s rho hoạt động. Xem hai con trỏ và fast/slow pointer.

Trộn và tìm node giữa

Hai thao tác chuẩn mực nữa, cả hai đều O(n):

def find_middle(head):
    """Lại là fast/slow: khi fast tới cuối, slow đang ở điểm giữa. O(n), O(1)."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
    return slow                                    # với độ dài chẵn, đây là node giữa thứ hai


def merge_sorted(a, b):
    """Trộn hai singly linked list đã sort. O(n + m) thời gian, O(1) bộ nhớ phụ.
    Một sentinel loại bỏ hoàn toàn case đặc biệt 'list nào rỗng'."""
    sentinel = Node(None)
    tail = sentinel
    while a is not None and b is not None:
        if a.value <= b.value:                     # dùng <= để phép trộn giữ tính stable
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a is not None else b          # nối nốt phần còn thừa
    return sentinel.next

merge_sorted là lõi của merge sort trên linked list, thuật toán sắp xếp duy nhất thực sự hợp với linked list: nó không cần random access và có thể chạy với O(1) bộ nhớ phụ (khác với merge sort trên array vốn cần một buffer phụ O(n)). Quicksort và heapsort đều cần index nên gần như không dùng được ở đây. Xem thuật toán sắp xếp.

Ứng dụng thật trong code production

• collections.deque — CPython hiện thực nó dưới dạng doubly linked list của các block, mỗi block là một array cố định 64 pointer. Đây là thiết kế thực dụng: bạn được O(1) ở cả hai đầu từ cấu trúc liên kết, và duyệt thân thiện với cache từ các block array. Linked list thuần một-node-một-phần-tử gần như không bao giờ là thứ bạn muốn; loại theo block thì thường xuyên là.
• LRU cache — một hash table ánh xạ key → node, cộng một doubly linked list sắp xếp node theo mức độ vừa dùng. get tra cứu trong O(1) rồi gọi move_to_front trong O(1); việc trục xuất là pop tail trong O(1). functools.lru_cache của Python chính xác là như vậy (với circular doubly linked list). Tham chiếu chéo: caching.
• Separate chaining trong hash table — mỗi bucket là một linked list ngắn chứa các entry va chạm. “Ngắn” là từ khoá; khi chain dài ra, các implementation tốt chuyển chúng thành cây. Xem hash table.
• Free list của allocator — các block trống của một memory pool được nối với nhau bằng chính vùng nhớ trống đó để lưu pointer, nên list tốn 0 byte bộ nhớ phụ.
• Stack undo/redo, lịch sử trình duyệt, playlist nhạc — những ví dụ sách giáo khoa, và thực sự hợp lý, vì chúng được duyệt tuần tự và thay đổi tại những vị trí đã biết.

from collections import OrderedDict


class LRUCache:
    """LRU cache: hash table cho tra cứu O(1) + linked list cho thứ tự recency O(1).
    OrderedDict chính là hiện thực của CPython cho đúng cặp đôi đó."""

    def __init__(self, capacity):
        self.capacity = capacity
        self._data = OrderedDict()

    def get(self, key, default=None):
        if key not in self._data:
            return default
        self._data.move_to_end(key)                # O(1) — gỡ node ra và nối lại
        return self._data[key]

    def put(self, key, value):
        if key in self._data:
            self._data.move_to_end(key)
        self._data[key] = value
        if len(self._data) > self.capacity:
            self._data.popitem(last=False)         # O(1) — trục xuất phần tử lâu chưa dùng nhất


cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")                                     # "a" giờ là mới nhất
cache.put("c", 3)                                  # trục xuất "b", không phải "a"
print(list(cache._data))                           # ['a', 'c']

Best Practices

• Mặc định dùng array; chỉ dùng linked list khi có lý do gọi tên được. “Chèn là O(1)” không phải lý do trừ khi bạn đã sẵn có node. Nếu phải đi tìm vị trí thì linked list không có lợi thế nào mà lại thua đậm về hằng số.
• Dùng sentinel node. Gần như mọi bug linked list đều là một kiểm tra null ở case biên (list rỗng, một phần tử, xoá head, xoá tail). Sentinel biến những case đó thành giống hệt case tổng quát và các câu if biến mất.
• Giữ tail pointer nếu bạn có append. Không có nó, append là O(n) và dựng một list n phần tử là O(n²). Đây là lỗi rất dễ đưa lên production.
• Duy trì biến đếm size. Tính độ dài bằng cách duyệt là O(n), và code gọi len() trong điều kiện vòng lặp sẽ biến tuyến tính thành bậc hai.
• Tách rời node đã xoá (node.next = node.prev = None). Nó ngăn một tham chiếu cũ đi ngược vào list mà nó vừa bị gỡ ra, và trong runtime dùng reference counting nó phá vòng tham chiếu mà collector nếu không sẽ phải đi tìm.
• Không bao giờ dùng while node is not None trên một list có thể là circular. Hãy duyệt dựa trên một node dừng cố định.
• Ưu tiên collections.deque hơn mọi linked list tự viết trong Python. Nó được viết bằng C, theo block, O(1) ở cả hai đầu, và nhanh hơn khoảng một bậc so với linked list bằng object Python. Hạn chế duy nhất là index vào giữa là O(n) — mà linked list cũng vậy.
• Vẽ pointer ra trước khi viết code. Đảo ngược, splice và xoay đều là ba tới năm lần cập nhật pointer mà thứ tự rất quan trọng; một sơ đồ có đánh số bước bắt được lỗi “tôi ghi đè next trước khi kịp lưu nó” trước cả debugger.
• Test bốn case biên mỗi lần: list rỗng, một phần tử, hai phần tử, và thao tác trên head/tail. Bộ đó bắt được gần như mọi bug linked list.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Linked list — Wikipedia
• Doubly linked list — Wikipedia
• Cycle detection (Floyd’s algorithm) — Wikipedia
• Cache replacement policies (LRU) — Wikipedia
• CLRS — Introduction to Algorithms, Chapter 10: Elementary Data Structures
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• Python Documentation — collections.deque
• Python Documentation — functools.lru_cache
• Python Documentation — TimeComplexity of built-in types
• VisuAlgo — Linked list visualisation
• Big-O Cheat Sheet

   head
    |
    v
  +------+------+     +------+------+     +------+------+
  |  17  |  ----+---> |   3  |  ----+---> |  99  | None |
  +------+------+     +------+------+     +------+------+
   value   next        value   next        value   next

  Nodes live at arbitrary heap addresses. Only the pointers impose order.
  The last node's `next` is None — that is the terminator.

class Node:
    """One link in the chain: a value plus a reference to the next node."""

    __slots__ = ("value", "next")                  # saves memory: no per-node __dict__

    def __init__(self, value, next=None):
        self.value = value
        self.next = next


class SinglyLinkedList:
    """Singly linked list with a head, a tail, and a cached size."""

    def __init__(self, iterable=()):
        self.head = None
        self.tail = None                           # tail pointer makes append O(1)
        self.size = 0
        for value in iterable:
            self.append(value)

    def __len__(self):
        return self.size

    def push_front(self, value):
        """O(1) — the reason linked lists exist."""
        node = Node(value, self.head)
        self.head = node
        if self.tail is None:                      # was empty: head and tail coincide
            self.tail = node
        self.size += 1
        return node

    def append(self, value):
        """O(1) only because we keep a tail pointer; O(n) without one."""
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1
        return node

    def pop_front(self):
        """O(1) — unlink the head and move it forward."""
        if self.head is None:
            raise IndexError("pop from empty list")
        node = self.head
        self.head = node.next
        if self.head is None:                      # list is now empty
            self.tail = None
        self.size -= 1
        node.next = None                           # help the GC, avoid stale links
        return node.value

    def pop_back(self):
        """O(n) even with a tail pointer: we need the node BEFORE the tail,
        and a singly linked list gives no way back."""
        if self.head is None:
            raise IndexError("pop from empty list")
        if self.head is self.tail:
            value = self.head.value
            self.head = self.tail = None
            self.size -= 1
            return value
        prev = self.head
        while prev.next is not self.tail:          # walk to the second-to-last node
            prev = prev.next
        value = self.tail.value
        prev.next = None
        self.tail = prev
        self.size -= 1
        return value

    def find(self, value):
        """O(n) — no random access, no way to skip ahead."""
        node = self.head
        while node is not None:
            if node.value == value:
                return node
            node = node.next
        return None

    def remove(self, value):
        """O(n): finding the predecessor is the expensive part, not the unlink."""
        prev, node = None, self.head
        while node is not None:
            if node.value == value:
                if prev is None:
                    self.head = node.next
                else:
                    prev.next = node.next          # the actual unlink is O(1)
                if node is self.tail:
                    self.tail = prev
                self.size -= 1
                node.next = None
                return True
            prev, node = node, node.next
        return False

    def __iter__(self):
        node = self.head
        while node is not None:
            yield node.value
            node = node.next

    def __repr__(self):
        return " -> ".join(repr(v) for v in self) + " -> None"


lst = SinglyLinkedList([17, 3, 99])
lst.push_front(42)
print(lst)                 # 42 -> 17 -> 3 -> 99 -> None
lst.remove(3)
print(lst, len(lst))       # 42 -> 17 -> 99 -> None 3

        head                                                  tail
         |                                                     |
         v                                                     v
      +------+----+----+   +------+----+----+   +------+----+----+
None<-+ prev | 17 |next+-->+ prev |  3 |next+-->+ prev | 99 |next+-->None
      +------+----+----+<--+------+----+----+<--+------+----+----+

   Circular doubly linked list with one sentinel:

        +--------------------------------------------------+
        |                                                   |
        v                                                   |
   +---------+     +------+     +------+     +------+       |
   | SENTINEL| <-> |  17  | <-> |   3  | <-> |  99  | <-----+
   +---------+     +------+     +------+     +------+
        ^                                        |
        +----------------------------------------+

   Empty list:   SENTINEL.next == SENTINEL.prev == SENTINEL
   No None checks anywhere. Every insert and delete is the same three lines.

class DNode:
    """Doubly linked node: value plus both neighbours."""

    __slots__ = ("value", "prev", "next")

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


class DoublyLinkedList:
    """Circular doubly linked list with a sentinel — no None checks, no edge cases."""

    def __init__(self, iterable=()):
        self._sentinel = DNode()                   # points at itself when empty
        self.size = 0
        for value in iterable:
            self.append(value)

    def __len__(self):
        return self.size

    def _insert_between(self, value, left, right):
        """The one primitive: splice a new node between two known nodes. O(1)."""
        node = DNode(value)
        node.prev, node.next = left, right
        left.next = node
        right.prev = node
        self.size += 1
        return node

    def _unlink(self, node):
        """The other primitive: remove a node we already hold. O(1), no search."""
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None               # detach so stale refs cannot walk back
        self.size -= 1
        return node.value

    def append(self, value):                       # O(1)
        return self._insert_between(value, self._sentinel.prev, self._sentinel)

    def push_front(self, value):                   # O(1)
        return self._insert_between(value, self._sentinel, self._sentinel.next)

    def pop_back(self):                            # O(1) — this is what `prev` buys us
        if self.size == 0:
            raise IndexError("pop from empty list")
        return self._unlink(self._sentinel.prev)

    def pop_front(self):                           # O(1)
        if self.size == 0:
            raise IndexError("pop from empty list")
        return self._unlink(self._sentinel.next)

    def move_to_front(self, node):
        """O(1): unlink then re-insert. The core operation of an LRU cache."""
        node.prev.next = node.next
        node.next.prev = node.prev
        first = self._sentinel.next
        node.prev, node.next = self._sentinel, first
        self._sentinel.next = node
        first.prev = node

    def __iter__(self):
        node = self._sentinel.next
        while node is not self._sentinel:          # the sentinel is the stop condition
            yield node.value
            node = node.next

    def __reversed__(self):
        node = self._sentinel.prev
        while node is not self._sentinel:
            yield node.value
            node = node.prev

    def __repr__(self):
        return "[" + " <-> ".join(repr(v) for v in self) + "]"


dll = DoublyLinkedList([17, 3, 99])
dll.push_front(42)
print(dll)                     # [42 <-> 17 <-> 3 <-> 99]
print(list(reversed(dll)))     # [99, 3, 17, 42]
print(dll.pop_back(), dll)     # 99 [42 <-> 17 <-> 3]

def reverse_iterative(head):
    """Reverse in place. O(n) time, O(1) space. Returns the new head."""
    prev, node = None, head
    while node is not None:
        nxt = node.next        # save the rest of the list before we overwrite `next`
        node.next = prev       # flip this link backwards
        prev, node = node, nxt # advance both pointers
    return prev                # `node` is now None, so `prev` is the last node = new head

   Step by step on 1 -> 2 -> 3 -> None

   prev=None  node=1        1 -> 2 -> 3 -> None
   after:     prev=1 node=2  None <- 1    2 -> 3 -> None
   after:     prev=2 node=3  None <- 1 <- 2    3 -> None
   after:     prev=3 node=None  None <- 1 <- 2 <- 3
   return prev = 3

def reverse_recursive(head):
    """O(n) time, O(n) STACK space. Fails on long lists in Python (recursion limit)."""
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)        # reverse everything after head
    head.next.next = head                          # make the next node point back at us
    head.next = None                               # and cut our forward link
    return new_head

   1 -> 2 -> 3 -> 4 -> 5
             ^         |
             +---------+

   slow moves 1 step, fast moves 2. Inside the cycle, fast gains
   exactly 1 position on slow per iteration, so it must eventually land on it.
   A gap that shrinks by 1 each step cannot skip over 0.

def has_cycle(head):
    """Floyd's cycle detection. O(n) time, O(1) space."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next                           # 1 step
        fast = fast.next.next                      # 2 steps
        if slow is fast:                           # they can only meet inside a cycle
            return True
    return False                                   # fast fell off the end -> no cycle


def cycle_start(head):
    """Find the first node of the cycle, or None. O(n) time, O(1) space."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            # Distance from head to cycle start == distance from meeting point
            # to cycle start (going forward). Walk both at the same speed.
            probe = head
            while probe is not slow:
                probe, slow = probe.next, slow.next
            return probe
    return None


def cycle_length(meeting_node):
    """Once the pointers have met, count the cycle's length. O(cycle length)."""
    count, node = 1, meeting_node.next
    while node is not meeting_node:
        count += 1
        node = node.next
    return count

def find_middle(head):
    """Fast/slow again: when fast reaches the end, slow is at the midpoint. O(n), O(1)."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
    return slow                                    # for even length, the second middle


def merge_sorted(a, b):
    """Merge two sorted singly linked lists. O(n + m) time, O(1) extra space.
    A sentinel removes the 'which list is empty' special case entirely."""
    sentinel = Node(None)
    tail = sentinel
    while a is not None and b is not None:
        if a.value <= b.value:                     # <= keeps the merge stable
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a is not None else b          # attach whatever is left
    return sentinel.next

from collections import OrderedDict


class LRUCache:
    """LRU cache: hash table for O(1) lookup + linked list for O(1) recency ordering.
    OrderedDict is CPython's implementation of exactly that pairing."""

    def __init__(self, capacity):
        self.capacity = capacity
        self._data = OrderedDict()

    def get(self, key, default=None):
        if key not in self._data:
            return default
        self._data.move_to_end(key)                # O(1) — unlink and relink the node
        return self._data[key]

    def put(self, key, value):
        if key in self._data:
            self._data.move_to_end(key)
        self._data[key] = value
        if len(self._data) > self.capacity:
            self._data.popitem(last=False)         # O(1) — evict the least recent


cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")                                     # "a" is now most recent
cache.put("c", 3)                                  # evicts "b", not "a"
print(list(cache._data))                           # ['a', 'c']