Az XOR-kapcsolt lista egy olyan adatstruktúra , amely hasonló egy hagyományos , duplán linkelt listához , azonban minden elem csak egy összetett címet tárol - a lista előző és következő elemeinek XOR -címének az eredménye.
A listában való mozgáshoz két egymást követő elem címére van szükség.
Ha XOR műveletet hajtunk végre az első elem címén és a második elemben tárolt összetett címen, akkor megkapjuk a két elemet követő elem címét.
Az első elemben tárolt összetett cím és a második elem címének XOR-a megadása a két elemet megelőző elem címét eredményezi.
A klasszikus duplán linkelt lista külön tárolja a lista előző és következő elemének címét, amelyek tárolásához két mutató szükséges:
... A B C D E ... –> next –> next –> next –> <– prev <– prev <– prev <–Egy XOR-hoz kapcsolt lista rezsije feleannyi, mivel csak egy "címet" tárol - az XOR mutat az előző és a következő elemre:
... A B C D E ... <–> A⊕C <-> B⊕D <-> C⊕E <->A hiányosságok között megemlíthető egy bonyolultabb megvalósítás, a szabványos szemétgyűjtő használatának hiánya, a program hibakeresési nehézségei [1] .
Elég ritkán használják, mivel vannak jó alternatívák, például egy kiterjesztett linkelt lista .