XOR linked lists are a data structure used in computer programming. They take advantage of the bitwise exclusive disjunction (XOR) operation, here denoted by ⊕, to decrease storage requirements for doubly-linked lists. An ordinary doubly-linked list stores addresses of the previous and next list items in each list node, requiring two address fields: ... A B C D E ...

PropertyValue
dbpprop:abstract
  • XOR linked lists are a data structure used in computer programming. They take advantage of the bitwise exclusive disjunction (XOR) operation, here denoted by ⊕, to decrease storage requirements for doubly-linked lists. An ordinary doubly-linked list stores addresses of the previous and next list items in each list node, requiring two address fields: ... A B C D E ... –> next –> next –> next –> An XOR linked list compresses the same information into one address field by storing the bitwise XOR of the address for previous and the address for next in one field: ... A B C D E ... <–> A⊕C <-> B⊕D <-> C⊕E <-> When you traverse the list from left to right: supposing you are at C, you can take the address of the previous item, B, and XOR it with the value in the link field (B⊕D). You will then have the address for D and you can continue traversing the list. The same pattern applies in the other direction. To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one. If the addresses of the two consecutive items are reversed, you will end up traversing the list in the opposite direction. This form of linked list may be inadvisable: General-purpose debugging tools cannot follow the XOR chain, making debugging more difficult; The price for the decrease in memory usage is an increase in code complexity, making maintenance more expensive; Most garbage collection schemes do not work with data structures that do not contain literal pointers; XOR of pointers is not defined in some contexts (e.g. , the C language), although many languages provide some kind of type conversion between pointers and integers; The pointers will be unreadable if one isn't traversing the list — for example, if the pointer to a list item was contained in another data structure; While traversing the list you need to remember the address of the previously accessed node in order to calculate the next node's address. Computer systems have increasingly cheap and plentiful memory, and storage overhead is not generally an overriding issue outside specialized embedded systems. Where it is still desirable to reduce the overhead of a linked list, unrolling provides a more practical approach (as well as other advantages, such as increasing cache performance and speeding random access).
  • On nomme chaînage XOR un procédé permettant de parcourir une liste chaînée dans un sens comme dans l'autre en ne gardant dans chaque bloc qu'un seul pointeur au lieu de deux. La contrepartie est qu'on ne peut cheminer dans la liste qu'en partant de l'une de ses deux extrémités, restriction inexistante dans les listes à double pointeur.
  • XOR連結リスト（英: XOR linked list）は、プログラミングにおけるデータ構造の一種。ビット毎の排他的論理和 (XOR) の特徴を生かして、双方向連結リストに必要なメモリ量を削減する。なお、以下ではXOR演算を ⊕ と記述する。
  • XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • XOR linked lists are a data structure used in computer programming. They take advantage of the bitwise exclusive disjunction (XOR) operation, here denoted by ⊕, to decrease storage requirements for doubly-linked lists. An ordinary doubly-linked list stores addresses of the previous and next list items in each list node, requiring two address fields: ... A B C D E ...
  • On nomme chaînage XOR un procédé permettant de parcourir une liste chaînée dans un sens comme dans l'autre en ne gardant dans chaque bloc qu'un seul pointeur au lieu de deux. La contrepartie est qu'on ne peut cheminer dans la liste qu'en partant de l'une de ses deux extrémités, restriction inexistante dans les listes à double pointeur.
  • XOR連結リスト（英: XOR linked list）は、プログラミングにおけるデータ構造の一種。ビット毎の排他的論理和 (XOR) の特徴を生かして、双方向連結リストに必要なメモリ量を削減する。なお、以下ではXOR演算を ⊕ と記述する。
  • XOR-связный список — структура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка.
rdfs:label
  • XOR linked list
  • Chaînage XOR
  • XOR連結リスト
  • XOR-связный список
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of