Danh Sách Liên Kết XOR – Bí Mật Của Cấu Trúc Dữ Liệu Tiết Kiệm Bộ Nhớ

Hôm trước, một người bạn tên Nam đang xây dựng hàng đợi thông điệp bằng cấu trúc danh sách liên kết. Dù gọi là danh sách, nhưng yêu cầu không đòi hỏi thao tác chèn/xóa nút ở giữa – chỉ cần đảm bảo nguyên tắc FIFO (vào trước – ra trước). Để tối ưu hiệu suất, cuối cùng bạn ấy đã chọn cài đặt danh sách liên kết kép thông thường.

Cấu trúc này được viết bằng Lua, ngôn ngữ cho phép xây dựng danh sách liên kết kép tương đối dễ dàng. Thực tế, ngay cả danh sách đơn kết hợp thêm biến theo dõi nút đuôi cũng có thể đáp ứng yêu cầu. Nhưng hôm nay chúng ta hãy khám phá một kỹ thuật đặc biệt: Trong lập trình C, chúng ta hoàn toàn có thể xây dựng hàng đợi hai đầu với khả năng duyệt cả hai chiều, chỉ sử dụng không gian lưu trữ bằng danh sách đơn! Phương pháp này có độ phức tạp mã không khác nhiều so với danh sách đơn, nhưng lại áp dụng một nguyên tắc toán học cực kỳ thông minh – đó chính là danh sách liên kết XOR (XOR Linked List).

Nguyên lý hoạt động cơ bản

Thay vì lưu trữ riêng biệt hai con trỏ prev và next như danh sách kép truyền thống, mỗi nút trong danh sách XOR sẽ chứa giá trị XOR của hai con trỏ này. Cụ thể:

1
2
3
4

typedef struct Node {
    Data data;
    struct Node* xor_ptr;
} Node;

Để tính toán giá trị xor_ptr, chúng ta ép kiểu con trỏ về kiểu nguyên uintptr_t và thực hiện phép toán XOR bit:

1

node->xor_ptr = (uintptr_t)prev ^ (uintptr_t)next;

Bí mật toán học phía sau

Cấu trúc này hoạt động dựa trên tính chất toán học của phép XOR:
A ^ (A ^ B) = B
B ^ (A ^ B) = A

Điều này có nghĩa là: Nếu biết được một trong hai con trỏ (prev hoặc next), chúng ta có thể tính ngược lại con trỏ còn lại thông qua giá trị xor_ptr. Ví dụ khi duyệt từ đầu về cuối:

1

Node* next_node = (Node*)((uintptr_t)current ^ (uintptr_t)prev);

Thuật toán duyệt danh sách

Dù duyệt theo chiều nào, thuật toán đều thống nhất về mặt logic:

1. Duyệt từ đầu đến cuối:

   • Bắt đầu với prev = NULL, current = head
   • Tính next = xor_ptr ^ prev
   • Cập nhật prev = current, current = next cho bước tiếp theo

2. Duyệt từ cuối về đầu:

   • Bắt đầu với next = NULL, current = tail
   • Tính prev = xor_ptr ^ next
   • Cập nhật next = current, current = prev

Các thao tác hàng đợi

Thêm phần tử (enqueue):

1. Tạo nút mới, đặt xor_ptr = head
2. Nếu danh sách không rỗng:

   1	head->xor_ptr = (uintptr_t)new_node ^ ((uintptr_t)head->xor_ptr ^ (uintptr_t)NULL);

3. Cập nhật head thành new_node

Loại bỏ phần tử (dequeue):

1. Lưu next_node = head->xor_ptr
2. Cập nhật next_node->xor_ptr = (uintptr_t)head ^ ((uintptr_t)next_node->xor_ptr ^ (uintptr_t)NULL);
3. Đặt head = next_node

Ưu điểm vượt trội

• Tiết kiệm 50% bộ nhớ: So với danh sách kép thông thường
• Dễ dàng triển khai không khóa (lock-free): Phù hợp lập trình đa luồng
• Hiệu suất tối ưu: Thao tác O(1) cho cả enqueue/dequeue

Hạn chế cần lưu ý

• Phụ thuộc vào ngôn ngữ: Chỉ khả thi trong các ngôn ngữ hỗ trợ thao tác con trỏ như C/C++
• Khó gỡ lỗi: Giá trị xor_ptr không mang ý nghĩa rõ ràng khi debug
• Yêu cầu thông tin lân cận: Phải biết trước/sau nút thao tác để thực hiện chèn/xóa

Ứng dụng thực tế

XOR Linked List không chỉ là một trò đùa trí tuệ. Trong các hệ thống nhúng với giới hạn bộ nhớ nghiêm ngặt, cấu trúc này mang lại giải pháp tối ưu. Nó cũng chứng minh rằng đôi khi sự kết hợp giữa toán học và lập trình có thể tạo ra những giải pháp hiệu quả đến bất ngờ – giống như việc sử dụng XOR để đổi chỗ hai biến, nhưng ở quy mô phức tạp hơn nhiều.

“Cấu trúc dữ liệu không quan trọng hình thức bề ngoài, mà nằm ở cách bạn sử dụng không gian bộ nhớ một cách thông minh.” – Nguyên tắc thiết kế tối ưu trong lập trình hệ thống.