4

私は XOR リンク リストについて読んでいて、1 つの疑問が頭に浮かびIs it possible to have a circular XOR linked list?ました。どうにかしてそのようなリストを作成したとしても、リストのヘッド ノードが与えられた場合、それをトラバースすることは不可能であるように思われます。たとえば、リンクされたリストに A、B、C の 3 つのノードが含まれているとします。

|
v
A ---> B ---> C

A->xor = B ^ C
B->xor = A ^ C
C->xor = A ^ B

headリストが与えられているため、つまりこの場合は、移動するためにorAの少なくとも 1 つを知る必要があるため、前後に移動することはできません。トラバースできないため、ビルドもできません。BC

私の考えは正しいですか？または、何か不足していますか？

4

4 に答える 4

0

非循環 XOR リストでは、firstノード ポインターはノードをリストlastに追加する役割を果たし、ノード ポインターはノードをリストに追加する役割を果たします。ポインタを 1 つだけ持つ非循環 XOR リストをトラバースできます。しかし、循環 XOR リストではなく、どこfirstにリンクする必要がありますlast。firstしたがって、いずれかまたはノードから循環 XOR リストをトラバースし、lastノードをリストに追加するには、両方へのポインターが必要です。

于 2022-01-04T09:41:40.990 に答える