Danh sách Liên kết XOR hoạt động như thế nào?

Question

Sau đây link giải thích nó.
Việc thực hiện được cho là hoạt động bằng cách lưu trữ XOR của địa chỉ trước đó và tiếp theo (nói nxp), thay vì lưu trữ cả hai (trước và địa chỉ tiếp theo) riêng biệt. Tuy nhiên, tiếp tục triển khai được thực hiện theo xor-ing địa chỉ trước đó và nxp, để nhận được địa chỉ tiếp theo.

Nhưng điều này không thực tế khi sử dụng cùng một không gian như có con trỏ trước đó và tiếp theo?

Answer 1

Trong danh sách được liên kết kép, bạn lưu trữ hai con trỏ trên mỗi nút: trước và sau. Trong một danh sách liên kết XOR, bạn lưu trữ một 'con trỏ' cho mỗi nút, đó là XOR của trước và tiếp theo (hoặc nếu một trong số chúng không có mặt, chỉ cái kia (giống như XORing với 0)). Lý do tại sao bạn vẫn có thể đi qua một danh sách liên kết XOR theo cả hai hướng dựa vào các thuộc tính của XOR và sự dư thừa thông tin vốn có trong một danh sách liên kết kép.

---

Hãy tưởng tượng bạn có ba nút trong danh sách liên kết XOR của bạn.

A là người đứng đầu, và có một con trỏ không khó hiểu đến B (B XOR 0, tiếp theo chỉ)

B là yếu tố trung lưu, và có XOR của con trỏ đến A và C.

C là đuôi, và con trỏ chưa được giải thích đến B (0 XOR B, chỉ áp dụng)

Khi tôi lặp lại danh sách này, tôi bắt đầu ở A. Tôi lưu ý vị trí của A khi tôi đi đến B. Khi tôi muốn di chuyển đến con trỏ C, I XOR B với A, cấp cho tôi con trỏ tới C. Sau đó tôi lưu ý vị trí của B trong bộ nhớ và di chuyển đến C.

Điều này làm việc vì XOR có đặc tính tự hoàn tác nếu áp dụng hai lần: C XOR A XOR A == C. Một cách khác để suy nghĩ về nó là danh sách được liên kết gấp đôi không lưu trữ thêm thông tin nào. chỉ cần lưu trữ tất cả các con trỏ trước như là bản sao của con trỏ tiếp theo ở một nơi khác trong bộ nhớ), do đó, bằng cách khai thác dự phòng này, chúng tôi có thể có các thuộc tính danh sách được liên kết gấp đôi chỉ với nhiều liên kết. Tuy nhiên, Điều này chỉ hoạt động nếu chúng tôi bắt đầu danh sách liên kết XOR của chúng tôi từ đầu hoặc cuối - như thể chúng ta chỉ cần nhảy vào một nút ngẫu nhiên ở giữa, chúng tôi không có thông tin cần thiết để bắt đầu duyệt qua.

---

Trong khi một danh sách XOR liên kết có lợi thế là sử dụng bộ nhớ nhỏ hơn, nó có nhược điểm - nó sẽ gây nhầm lẫn cho công cụ biên dịch, gỡ lỗi và phân tích tĩnh như XOR bạn của hai con trỏ sẽ không được công nhận một cách chính xác bởi một con trỏ bởi bất cứ điều gì ngoại trừ mã của bạn. Nó cũng làm chậm truy cập con trỏ để phải thực hiện thao tác XOR để khôi phục con trỏ thực sự đầu tiên. Nó cũng không thể được sử dụng trong mã được quản lý - Các con trỏ bị xáo trộn XOR sẽ không được bộ thu gom rác nhận ra.

Answer 2

Danh sách liên kết đôi cần 2 * N con trỏ được lưu trữ cho N nút, cộng thêm ít nhất một con trỏ bổ sung (đầu, hoặc có thể đầu và đuôi).

Danh sách liên kết XOR cần N con trỏ được lưu trữ cho N nút, cộng thêm ít nhất hai con trỏ bổ sung (đầu và nút truy cập lần cuối, hoặc có thể đầu và đuôi và nút truy cập lần cuối). Trong khi duyệt qua, bạn lưu trữ một nút (nút được truy cập lần cuối), nhưng khi bạn đi đến nút tiếp theo, bạn viết lại với nút địa chỉ của nút trước đó.

Answer 3

Nhưng thực tế này không sử dụng cùng một không gian như trước đây và con trỏ tiếp theo?

Không - nó sử dụng khoảng một nửa không gian, vì kích thước của kết quả XOR-ing "trước" và "tiếp theo" bằng với kích thước lớn hơn của hai.

Answer 4

XOR có một thuộc tính rất đặc biệt về nó, cụ thể là, chỉ có hai (bất kỳ hai) biến nào được yêu cầu để tính toán số thứ ba, với một số hạn chế. Xem XOR swap algorithm để biết lý do hoạt động.

Trong trường hợp này, con trỏ trước đó (hoặc tiếp theo) vẫn phải được thực hiện, nhưng chỉ thông qua tính toán truyền tải chứ không phải là thành viên riêng biệt.