数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学异或链表 – 一种内存高效的双向链表
链表
链表是一种线性数据结构，包含称为节点的元素。每个节点包含两个主要组成部分：数据（该节点的有效负载）和指向列表中下一个节点的指针。它们简单易用，高效，易于分配和释放内存。
双向链表
双向链表是一种特殊的链表，同样由称为节点的基本元素组成。每个节点包含三个主要组成部分：数据（该节点的有效负载）、指向序列中前一个节点的指针和指向序列中下一个节点的指针。这种双向链接允许高效地双向遍历。
异或链表
异或链表，也称为 XOR 双向链表，使用按位异或 (^) 运算来节省内存，与传统的双向链表相比。每个节点包含两个主要组成部分：数据（该节点的有效负载）以及序列中前一个节点和下一个节点的内存地址的异或值。
示例
给定一个双向链表：A - B - C - D
异或表示为：
link(A) = NULL ^ address(B) link(B) = address(A) ^ address(C) link(C) = address(B) ^ address(D) link(D) = address(C) ^ NULL
正向遍历
对于上面的示例，让我们考虑正向遍历，即从左到右，看看如何使用节点中存储的链接到达下一个节点。给定正向遍历，前一个节点的地址存储在一个变量中。假设我们位于节点 B 并想要到达节点 C。
address(A) ^ link(B) = address(A) ^ (address (A) ^ address(C)) = 0 ^ address(C) = address(C)
反向遍历
对于上面的示例，让我们考虑反向遍历，即从右到左，看看如何使用节点中存储的链接到达下一个节点。给定反向遍历，前一个节点的地址存储在一个变量中。假设我们位于节点 D 并想要到达节点 C。
NULL ^ link(D) = NULL ^ (address(C) ^ NULL) = 0 ^ address(C) = address(C)
伪代码
structure Node:
data : integer
link : Node
function xor(x : Node, y : Node) : Node
return Node with address (address of x) xor (address of y)
function traverse(head : Node)
curr : Node = head
prev : Node = null
next : Node
while curr is not null
output curr.data, " --> "
next = xor(prev, curr.link)
prev = curr
curr = next
end while
output "nullptr"
function push(headRef : Node reference, data : integer)
newNode : Node = create new Node
newNode.data = data
newNode.link = xor(headRef, null)
if headRef is not null
headRef.link = xor(newNode, xor(headRef.link, null))
end if
headRef = newNode
示例：C++ 实现
#include <iostream>
#include <vector>
#include <cstdint>
using namespace std;
// Structure of XOR Linked list
struct Node {
int data;
Node *link;
};
// Dunction to calculate XOR of two node address
Node *XOR(Node *x, Node *y) {
return (Node *)((uintptr_t)(x) ^ (uintptr_t)(y));
}
// Forward traversal
void traverse(Node *head) {
Node *curr = head;
Node *prev = nullptr;
Node *next;
while (curr != nullptr) {
cout << curr->data << " --> ";
next = XOR(prev, curr->link);
prev = curr;
curr = next;
}
cout << "nullptr";
}
// Function to push an element at front of XOR linked list
void push(Node *&headRef, int data) {
Node *newNode = new Node();
newNode->data = data;
newNode->link = XOR(headRef, nullptr);
if (headRef) {
headRef->link = XOR(newNode, XOR(headRef->link, nullptr));
}
headRef = newNode;
}
int main() {
vector<int> values = {1, 2, 3, 4};
Node *head = nullptr;
for (int i = values.size() - 1; i >= 0; i--) {
push(head, values[i]);
}
traverse(head);
return 0;
}
输出
1 --> 2 --> 3 --> 4 --> nullptr
结论
总之，异或链表是实现双向链表的一种高效方法。但是它有点复杂，与双向链表相比编码不太容易，而且节点删除也不可能。此外，许多语言（如 Java）不支持异或链表。
更新于：2023年11月3日
2K+ 次浏览
广告