A variant of the doubly linked list – XOR linked list

Variation of doubly linked list – XOR linked list

  • XOR group
  • XOR linked list
    • structure
    • structure
    • insert
    • delete
    • traverse
  • accomplish

Exclusive OR group

Most programming languages define the XOR operation of integers. For example, the result of executing the statement 2 ^ 3 in Java is 1. From a higher perspective, integers are nothing more than fixed-length bit strings, and XOR operations are defined on all fixed-length bit strings. all

no

no

n bit strings make up the set

{

0

,

1

}

no

\{0,1\}^n

{0,1}n, XOR

{

0

,

1

}

no

\{0,1\}^n

Binary operations on {0,1}n

⊕

:

{

0

,

1

}

2

no

?

{

0

,

1

}

no

\oplus:\{0,1\}^{2n}\mapsto\{0,1\}^n

⊕:{0,1}2n?{0,1}n.

algebraic system

(

{

0

,

1

}

no

,

⊕

)

(\{0,1\}^n,\oplus)

({0,1}n,⊕) is an Abelian group, that is, for any

x

,

the y

,

z

∈

{

0

,

1

}

no

x,y,z\in\{0,1\}^n

x,y,z∈{0,1}n satisfies:

  1. Associative law:

    (

    x

    ⊕

    the y

    )

    ⊕

    z

    =

    x

    ⊕

    (

    the y

    ⊕

    z

    )

    (x \oplus y) \oplus z=x \oplus (y \oplus z)

    (x⊕y)⊕z=x⊕(y⊕z)

  2. There is a unitary:

    x

    ⊕

    0

    =

    0

    ⊕

    x

    =

    x

    x \oplus 0 = 0 \oplus x=x

    x⊕0=0⊕x=x

  3. There are inverses:

    x

    2

    =

    x

    ⊕

    x

    =

    0

    x^2 = x \oplus x = 0

    x2=x⊕x=0

  4. commutative law:

    x

    ⊕

    the y

    =

    the y

    ⊕

    x

    x \oplus y=y \oplus x

    x⊕y=y⊕x

realistic

no

no

n is usually

8

8

Multiples of 8, and it is usually specified that XOR is defined on integers represented by integers. For example in Java

no

∈

{

8

,

16

,

32

,

64

}

n \in \{8, 16, 32, 64\}

n∈{8,16,32,64}, respectively corresponding to integer byte, short, int, long. In some languages that support unsafe pointers such as C and C++, pointers can also be treated as integers. Using this feature, the pointer is not only a unique address or identifier of the variable, but also data that can be operated on.

XOR linked list

Each node of the singly linked list at least includes the data data and the pointer to the successor succ, and the double linked list passes Add a precursor pointer pred to the node, so that the linked list can be traversed bidirectionally. The XOR linked list can also achieve the effect of bidirectional traversal without adding additional pointers by using the nature of integer XOR.

Structure

The nodes of the XOR linked list and the one-way linked list have only one pointer, but the pointer link of the XOR linked list does not point to any node, and link is the XOR of its predecessor and successor. or. How does the XOR linked list ensure that the nodes are interconnected? If a node is known, such as B, and its predecessor A, pass the of A and B link XOR operation, you can get the successor C of B. Because A ^ B.link = A ^ (A ^ C) = C. Similarly, if B and the successor C of B are known, then A, the predecessor of B, can be obtained .

For convenience, using two sentinelshead and tail at the head and tail of the linked list can simplify the handling of boundary conditions, thus reducing the in the code The >if statement makes the code clearer and easier to read.

------------ ----------- ----------- ----------- --- --------
|H||A||B||C||T|
| |<--->| DataA |<--->| DataB |<--->| DataC |<--->|
|A||H^B||A^C||B^T||C|
----------- ----------- ----------- ----------- ------ -----

In the linked list above, there are five nodes in total, two of which are sentinels H and T, and the sentinels do not have any data. At the same time, it is stipulated that the predecessor of H and the successor of T are nullptr, that is, 0. According to property 2, the link of H is actually the first node A of the linked list, and the same for T link is actually the last node C of the linked list. The predecessor of B is A, and the successor is C, so the link of B is A ^ C.

The following C++ template class defines some basic fields and methods of XOR linked list. The two private sentinel nodes head and tail are of type XNode *, and XNode is defined in XLinkedList< Inside /code>, the constructor, insertion, deletion, and traversal are all public methods.

template <typename T>
class XLinkedList {<!-- -->
private:
    class XNode {<!-- -->
    public:
        XNode();
        XNode(T data, XNode *link);
        T data;
        XNode *link;
    };
    XNode *head;
    XNode *tail;
public:
    XLinkedList();
    void insert_front(T data);
    void insert_back(T data);
    T delete_front();
    T delete_back();
    void traverse_forwards(void (*visit)(T));
    void traverse_backwards(void (*visit)(T));
};

Construction

The construction process of XOR linked list needs to construct two sentinels and initialize link. Since the predecessor of head and the successor of tail are both 0, the linkhead > is tail, link of tail is head.

template<typename T>
XLinkedList<T>::XNode::XNode() = default;

template<typename T>
XLinkedList<T>::XNode::XNode(T data, XLinkedList::XNode *link) : data(data), link(link) {<!-- -->}

template<typename T>
XLinkedList<T>::XLinkedList() {<!-- -->
    head = new XNode;
    tail = new XNode;
    head->link = tail;
    tail->link = head;
}

Insert

Consider inserting node X at the front of the XOR list. The insertion operation needs to set the link of X to the XOR of the original head node of head, namely H ^ A . At the same time, since the successor and predecessor of H and A have changed, their link should also be updated in time to ensure the interconnection of nodes.

------------ ----------- ----------- ----------- --- --------
|H||A||B||C||T|
| |<--->| DataA |<--->| DataB |<--->| DataC |<--->|
|A||H^B||A^C||B^T||C|
----------- ----------- ----------- ----------- ------ -----
----------- ----------- ----------- ----------- ------ ----- -----------
|H||X||A||B||C||T|
| |<--->| DataX |<--->| DataA |<--->| DataB |<--->| DataC |<--->| |
| X | | H ^ A | | X ^ B | | A ^ C | | B ^ C | | C |
----------- ----------- ----------- ----------- ------ ----- -----------

Inserting a new node X in the front end requires three steps:

  1. First construct a new node X, and initialize data and link
  2. Change the link of the original first node A. After inserting X, the link of A becomes X ^ B, but updates A The link of code> does not need to know the specific number of B at the same time. A is nothing more than changing the predecessor, only need to eliminate the original predecessor H, and then use X to XOR, you can get X ^ B. That is, X ^ B = X ^ 0 ^ B = X ^ H ^ H ^ B = X ^ H ^ (H ^ B).
  3. The link of the head sentinel is set to X
template<typename T>
void XLinkedList<T>::insert_front(T data) {<!-- -->
    auto node = new XNode(data, (XNode *) ((uintptr_t) head ^ (uintptr_t) head->link));
    head->link->link = (XNode *) ((uintptr_t) node ^ (uintptr_t) head ^ (uintptr_t) head->link->link);
    head->link = node;
}

Delete

Consider deleting the first node A. The delete operation needs to update the head sentinel’s and link of A‘s successor.

------------ ----------- ----------- ----------- --- --------
|H||A||B||C||T|
| |<--->| DataA |<--->| DataB |<--->| DataC |<--->|
|A||H^B||A^C||B^T||C|
----------- ----------- ----------- ----------- ------ -----
 ----------- ----------- ----------- -----------
|H||B||C||T|
| |<--->| DataB |<--->| DataC |<--->| |
|B||H^C||B^T||C|
----------- ----------- ----------- -----------

The core operation of deleting the first node A is only two steps:

  1. According to the principle used in the insert operation, update the link of B from A ^ C to B ^ C
  2. The link of the head sentinel is set to B
template<typename T>
T XLinkedList<T>::delete_front() {<!-- -->
    XNode *node = head->link;
    auto succ = (XNode *) ((uintptr_t) head ^ (uintptr_t) node->link);
    succ->link = (XNode *) ((uintptr_t) head ^ (uintptr_t) node ^ (uintptr_t) succ->link);
    head->link = succ;
    T data = node->data;
    delete node;
    return data;
}

Traverse

Considering forward traversal, the entire traversal process needs to maintain two pointers: the current node and the predecessor of the current node. The next node to be visited can be obtained by XORing the link of the predecessor and the current node.

template<typename T>
void XLinkedList<T>::traverse_forwards(void (*visit)(T)) {<!-- -->
    XNode *pred = head;
    XNode *node = pred->link;
    while (node != tail) {<!-- -->
        visit(node->data);
        auto succ = (XNode *) ((uintptr_t) pred ^ (uintptr_t) node->link);
        pred = node;
        node = succ;
    }
}

Implementation

#ifndef X_LINKED_LIST_XLINKEDLIST_H
#define X_LINKED_LIST_XLINKEDLIST_H

template 
class XLinkedList {
private:
    class XNode {
    public:
        XNode();
        XNode(T data, XNode *link);
        T data;
        XNode *link; // predecessor xor successor
    };
    XNode *head;
    XNode *tail;
public:
    XLinkedList();
    void insert_front(T data);
    void insert_back(T data);
    T delete_front();
    T delete_back();
    void traverse_forwards(void (*visit)(T));
    void traverse_backwards(void (*visit)(T));
};

template<typename T>
XLinkedList<T>::XNode::XNode() = default;

template<typename T>
XLinkedList<T>::XNode::XNode(T data, XLinkedList::XNode *link) : data(data), link(link) {<!-- -->}

template<typename T>
XLinkedList<T>::XLinkedList() {<!-- -->
    head = new XNode;
    tail = new XNode;
    head->link = tail;
    tail->link = head;
}

template<typename T>
void XLinkedList<T>::insert_front(T data) {<!-- -->
    auto node = new XNode(data, (XNode *) ((uintptr_t) head ^ (uintptr_t) head->link));
    head->link->link = (XNode *) ((uintptr_t) node ^ (uintptr_t) head ^ (uintptr_t) head->link->link);
    head->link = node;
}

template
void XLinkedList::insert_back(T data) {
    auto node = new XNode(data, (XNode *) ((uintptr_t) tail ^ (uintptr_t) tail->link));
    tail->link->link = (XNode *) ((uintptr_t) tail->link->link ^ (uintptr_t) tail ^ (uintptr_t) node);
    tail->link = node;
}

template<typename T>
T XLinkedList<T>::delete_front() {<!-- -->
    XNode *node = head->link;
    auto succ = (XNode *) ((uintptr_t) head ^ (uintptr_t) node->link);
    succ->link = (XNode *) ((uintptr_t) head ^ (uintptr_t) node ^ (uintptr_t) succ->link);
    head->link = succ;
    T data = node->data;
    delete node;
    return data;
}

template
T XLinkedList::delete_back() {
    XNode *node = tail->link;
    auto pred = (XNode *) ((uintptr_t) node->link ^ (uintptr_t) tail);
    pred->link = (XNode *) ((uintptr_t) pred->link ^ (uintptr_t) node ^ (uintptr_t) tail);
    tail->link = pred;
    T data = node->data;
    delete node;
    return data;
}

template<typename T>
void XLinkedList<T>::traverse_forwards(void (*visit)(T)) {<!-- -->
    XNode *pred = head;
    XNode *node = pred->link;
    while (node != tail) {<!-- -->
        visit(node->data);
        auto succ = (XNode *) ((uintptr_t) pred ^ (uintptr_t) node->link);
        pred = node;
        node = succ;
    }
}

template
void XLinkedList::traverse_backwards(void (*visit)(T)) {
    XNode *succ = tail;
    XNode *node = succ->link;
    while (node != head) {
        visit(node->data);
        auto pred = (XNode *) ((uintptr_t) node->link ^ (uintptr_t) succ);
        succ = node;
        node = pred;
    }
}

#endif