資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告