Bài đăng này sẽ thảo luận về danh sách liên kết XOR, được sử dụng để giảm yêu cầu bộ nhớ của danh sách liên kết kép bằng cách sử dụng toán tử XOR bitwise
Chúng tôi biết rằng mỗi nút của danh sách liên kết kép yêu cầu hai trường con trỏ để lưu trữ địa chỉ nút trước đó và nút tiếp theo của nó. Mặt khác, mỗi nút của danh sách liên kết XOR chỉ yêu cầu một trường con trỏ duy nhất, trường này không lưu địa chỉ bộ nhớ thực mà lưu XOR theo bit của địa chỉ cho nút trước và nút tiếp theo của nó
Để minh họa, hãy xem xét danh sách liên kết đôi sau đây
Ở đây, trường liên kết cho danh sách liên kết XOR tương đương lưu trữ các giá trị sau.
link[A] = NULL ^ addr[B] // XOR theo bit của NULL với địa chỉ của nút B
link[B] = addr[A] ^ addr[C]
link[C] = addr[B] ^ addr[D] // bitwise XOR between the address of node B and D
link[D] = addr[C] ^ NULL // bitwise XOR of the address of node A with NULL
Làm thế nào điều này giúp?
Chúng tôi biết rằng XOR có các thuộc tính sau
X^X = 0
X^0 = X
X^Y = Y^X
Chúng ta có thể dễ dàng duyệt qua danh sách liên kết XOR theo bất kỳ hướng nào bằng cách sử dụng các thuộc tính trên
1. Duyệt danh sách từ trái sang phải
Vì chúng tôi đang duyệt danh sách từ trái sang phải, giả sử chúng tôi lưu trữ địa chỉ của nút trước đó trong một số biến. Khi thông tin về nút trước đó có sẵn, chúng ta có thể lấy địa chỉ của nút tiếp theo bằng cách XOR giá trị trong trường liên kết với địa chỉ của nút trước đó
Ví dụ: giả sử chúng ta đang ở nút C, chúng ta có thể lấy địa chỉ của nút D, như hình bên dưới.
addr[B] ^ link[C]
= addr[B] ^ [addr[B] ^ addr[D]]
=
= addr[D]
Hoạt động XOR hủy bỏ addr[B] xuất hiện hai lần trong phương trình và tất cả những gì chúng ta còn lại là addr[D]. Tương tự, để lấy địa chỉ của nút A đầu tiên trong danh sách, chúng ta có thể XOR giá trị trong trường liên kết với NULL
NULL ^ link[A]
= NULL ^ [NULL ^ addr[B]]
= 0 ^ addr[B]
= addr[B]
2. Duyệt danh sách từ phải sang trái
Theo logic tương tự, để lấy địa chỉ của nút cuối cùng D trong danh sách, hãy XOR giá trị trường liên kết D's với NULL
NULL ^ link[D]
= NULL ^ [addr[C] ^ NULL]
= 0 ^ addr[C]
= addr[C]
Đối với bất kỳ nút giữa nào, giả sử nút C, chúng ta có thể lấy địa chỉ của nút trước đó B như sau
addr[D] ^ link[C]
= addr[D] ^ [addr[B] ^ addr[D]]
=
= addr[B]
Hãy xem xét chương trình sau đây, chương trình này xây dựng một danh sách được liên kết XOR và duyệt qua nó theo hướng chuyển tiếp bằng cách sử dụng các thuộc tính của toán tử XOR theo bit. Để duyệt qua danh sách đầy đủ, hãy duy trì ba con trỏ D0, D1 và D2 để lưu trữ địa chỉ nút hiện tại, địa chỉ nút trước đó và địa chỉ nút tiếp theo, tương ứng. Mỗi lần lặp của vòng lặp sẽ di chuyển các con trỏ này về phía trước hoặc phía sau một vị trí tùy thuộc vào hướng mà chúng ta đang duyệt qua danh sách
Việc triển khai có thể được nhìn thấy bên dưới trong C và C++
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include
#include
#include
// Cấu trúc dữ liệu để lưu trữ nút danh sách liên kết XOR
struct Nút
{
int dữ liệu;
struct Nút* liên kết;
};
// Hàm trợ giúp trả về XOR của `x` và `y`
struct Nút* XOR[struct Node *x, struct Node *y] {
return [struct Nút*][[uintptr_t][x] ^ [uintptr_t][y]];
}
// Hàm trợ giúp duyệt danh sách theo hướng thuận
void đi ngang[struct Nút *head]
{
struct Nút* curr = head;
struct Nút* prev = NULL;
struct Nút *tiếp theo;
trong khi [curr . = NULL]
{
printf["%d —> ", curr->data];
// Nút `tiếp theo` sẽ là xor địa chỉ của nút trước đó
// và liên kết nút hiện tại
tiếp theo = XOR[prev, curr->link];
// cập nhật con trỏ `prev` và `curr` cho lần lặp tiếp theo của vòng lặp
trước = hiện tại;
cuộn = tiếp theo;
}
printf["NULL"];
}
// Hàm trợ giúp để chèn một nút vào đầu danh sách liên kết XOR
void đẩy[struct Nút **head, int data]
{
// phân bổ nút danh sách mới và đặt dữ liệu cho nút đó
struct Node* newNode = [struct Node*]malloc[sizeof[struct Node]];
newNode->dữ liệu = data;
// Trường liên kết của nút mới là XOR của phần đầu hiện tại và `NULL`
// vì một nút mới đang được chèn vào đầu
newNode->link = XOR[*head, NULL];
// cập nhật giá trị liên kết của nút đầu hiện tại nếu danh sách được liên kết không trống
nếu [*đầu]
{
// *[head]->liên kết là XOR của `NULL` và địa chỉ của nút tiếp theo.
// Để lấy địa chỉ của nút tiếp theo, XOR nút đó bằng `NULL`
[*đầu]->link = XOR[newNode, XOR[[*head]->link, NULL]];
}
// cập nhật con trỏ đầu
*head = newNode;
}
int chính[void]
{
// phím nhập
int phím[] = { 1, 2, 3, 4, 5 };
int n = sizeof[keys]/sizeof[keys[0]];
struct Nút* đầu = NULL;
cho [int i = n - 1; i >=0; i--] {
đẩy[&đầu, keys[i]];
}
đi ngang[đầu];
return 0;
}
Tải xuống Chạy mã
Đầu ra.
1 —> 2 —> 3 —> 4 —> 5 —> NULL
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include
#include
#include
sử dụng không gian tên std;
// Cấu trúc dữ liệu để lưu trữ nút danh sách liên kết XOR
struct Nút
{
int dữ liệu;
Nút* liên kết;
};
// Hàm trợ giúp trả về XOR của `x` và `y`
Nút* XOR[Nút* x, Node* y] {
return [Nút*][[uintptr_t][x] ^ [uintptr_t][y]];
}
// Hàm trợ giúp duyệt danh sách theo hướng thuận
void đi ngang[Nút* head]
{
Nút* curr = head;
Nút* trước = nullptr;
Nút *tiếp theo;
trong khi [curr . = nullptr]
{
cout liên kết = XOR[newNode, XOR[headRef->link, nullptr]];
}
// cập nhật con trỏ đầu
headRef = newNode;
}
int chính[]
{
// phím nhập
vectơ keys = { 1, 2, 3, 4, 5 };
Nút* đầu = nullptr;
cho [int i = keys.kích thước[] - 1; i >=0; i--] {
đẩy[đầu, keys[i]];
}
đi ngang[đầu];
return 0;
}
Tải xuống Chạy mã
Đầu ra.
1 —> 2 —> 3 —> 4 —> 5 —> nullptr
Hạn chế của danh sách liên kết XOR
Danh sách liên kết XOR tương tự như danh sách liên kết kép nhưng không hoàn toàn tương đương với danh sách liên kết kép. Có một số nhược điểm của danh sách liên kết XOR so với danh sách liên kết kép, sẽ được thảo luận bên dưới