Chương 3: LINKED LISTS – 5.Doubly Linked List hiệu quả về bộ nhớ

3.9 Doubly Linked List hiệu quả về bộ nhớ

Trong cách triển khai thông thường, chúng ta cần giữ một con trỏ next trỏ đến mục tiếp theo trong danh sách và một con trỏ prev trỏ tới mục trước đó.
Điều đó có nghĩa là, các phần tử trong triển khai danh sách được liên kết kép bao gồm dữ liệu, một con trỏ đến nút tiếp theo và một con trỏ đến nút trước đó trong danh sách như được hiển thị bên dưới.

Conventional Node Definition

    public class DLLNode{
        private int data;
        private DLLNode next;
        private DLLNode prev;
        ...............
    }

Hiện tại chúng ta có một cách triển khai thay thế của danh sách liên kết kép ADT, với các thao tác chèn, duyệt và xóa.
Việc triển khai này dựa trên sự khác biệt của con trỏ. Mỗi nút chỉ sử dụng một con trỏ để duyệt qua lại danh sách.
Nó còn được gọi là XOR Linked List

New Node Definition

    public class ListNode{
        private int data;
        private ListNode ptrdiff;
        ...............
    }

Con trỏ ptrdiff chứa sự khác biệt giữa con trỏ tới nút tiếp theo và con trỏ tới nút trước đó.
Sự khác biệt của con trỏ được tính bằng cách sử dụng phép toán exclusive-or $(\oplus )$

ptrdiff = pointer to previous node $\oplus$ pointer to next node

Điểm chính của nút bắt đầu (head node) là $\oplus$ của NULL và nút tiếp theo của head.
Tương tự, điểm thứ tự của nút kết thúc là $\oplus$ của nút trước đó (trước đến nút cuối) và NULL.
Ví dụ, hãy xem xét danh sách liên kết sau đây.

Trong ví dụ trên,

• Con trỏ tiếp theo của A là: NULL $\oplus$ B
• Con trỏ tiếp theo của B là: A $\oplus$ C
• Con trỏ tiếp theo của C là: B $\oplus$ D
• Con trỏ tiếp theo của D là: C $\oplus$ NULL

Why does it work?
Để tìm câu trả lời cho câu hỏi này, chúng ta hãy xem xét các thuộc tính của ⊕:

• X ⊕ X = 0
• X ⊕ 0 = X
• X ⊕ Y = Y ⊕ X (symmetric – tính đối xứng)
• (X ⊕ Y) ⊕ Z = X ⊕ (Y ⊕ Z) (transitive – tính bắc cầu)

Với ví dụ trên, chúng ta hãy giả sử rằng chúng ta đang ở nút C và muốn chuyển đến nút B.
Chúng ta biết rằng ptrdiff của nút C được định nghĩa là B ⊕ D.
Nếu chúng ta muốn di chuyển đến B, thực hiện ⊕ trên điểm thứ ba của C với D sẽ cho B.
Điều này là do thực tế rằng,

Tương tự, nếu chúng ta muốn chuyển đến D, thì chúng ta phải áp dụng ⊕ cho ptrdiff của C với B để có được D.

Từ thảo luận trên, chúng ta có thể thấy rằng chỉ bằng cách sử dụng một con trỏ duy nhất, chúng ta có thể di chuyển qua lại.
Có thể triển khai danh sách liên kết kép một cách hiệu quả về bộ nhớ mà không ảnh hưởng đến hiệu quả thời gian một cách tối thiểu.

Note: Ở đây mình không implement vì nếu chúng ta cần lấy XOR của hai địa chỉ, chúng ta cần truyền địa chỉ bộ nhớ thành số nguyên, điều này không thể thực hiện được trong java. Nó có thể implement sử dụng C/C++, các bạn nếu muốn tìm hiểu thêm có thể tham khảo ở đây