异或链表

✍ dations ◷ 2025-02-23 19:37:01 #数据结构,二进制算术

异或链表（英语：XOR linked list）是数据结构里面的一种链式存储结构,可以在降低空间复杂度的情况下达到和双向链表一样的目的，使得在任何一个结点都能方便地访问它的前驱结点和后继结点。

普通双向链表的每个结点有三个域，分别存储着前一个结点的地址、后一个点的地址，以及数据

 ...  A       B         C         D         E  ...          –>  next –>  next  –>  next  –>          <–  prev <–  prev  <–  prev  <–

异或链表通过异或操作（这里用⊕表示）把前一个结点的地址和后一个结点的地址变成一个地址

 ...  A         B               C                D            E  ...          <–>  A⊕C     <->    B⊕D     <->      C⊕E  <->        link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), …

当从左往右遍历的时候，如果当前结点是C，指针域是内容是B⊕D,通过和前一个结点B的地址做异或操作就能得到下一个结点D的地址，如此重复便能遍历整个链表。

相关

肌肉卫星细胞肌卫星细胞（Myosatellite cell）是一种位于骨骼肌中的细胞。肌卫星细胞呈扁平形，有突起，通常附着在肌纤维表面。当肌纤维受损伤后，肌卫星细胞可增殖分化，参与肌纤维的修复，具有干细
区域地理学区域地理学（regional geography）是研究某一特定地区地理环境的特征、结构、发展变化，以及区域分异和区际联系的学科，是地理学的分支学科之一。不仅揭示特定区域的自然特征，而且区
社会资本实证主义 · 反实证主义（英语：Antipositivism）结构主义 · 冲突理论中层理论 · 形式理论批判理论人口 · 团体 · 组织（英语：Organizational theory） · 社会化社会性
氢氧基.mw-parser-output ruby>rt,.mw-parser-output ruby>rtc{font-feature-settings:"ruby"1}.mw-parser-output ruby.large{font-size:250%}.mw-parser-output ruby.larger{fon
赣粤高速公路赣粤高速公路江西段共分为樟树市至泰和、泰和至赣州、赣州至定南三段建设，全线按高速公路四车道标准设计，总投资30.08亿元。是赣粤高速公路向北的延伸路段，起于樟树市昌傅镇，经
儿童与青少年精神医学儿童与青少年精神医学或小儿精神医学是精神医学的一个分支。它主要专注于儿童与青少年及其家庭之心理疾患的诊断、治疗和预防。它主要主要研究心理与社会双重因素（英语：biopsy
ATC代码 (A04)A·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码A04（镇吐药和止呕药）是解剖学治疗学及化学分类系统的一个药物分组，这是由世界卫生组织药物统计方法整合中心（The WHO Coll
奥拉西奥·德·拉·科斯塔奥拉西奥·德·拉·科斯塔（Horacio de la Costa，（1916年5月9日－1977年3月20日））是耶稣会首位菲律宾人省级会长（Provincial superior），同时也是菲律宾史和亚洲史的权威。他是作家、学
裘树荣裘树荣（？－？），顺天府宛平（今属北京市）人，清朝政治人物。雍正五年（1727年）丁未科进士。雍正八年（1730年）接替邢文明任福建永安县知县一职，1732由田大玺接任。
广州地铁1号线.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:none