En XOR-länkad lista är en datastruktur som liknar en vanlig dubbellänkad lista , men varje element lagrar endast en sammansatt adress - resultatet av att XORing adresserna för föregående och nästa element i listan.
För att gå igenom listan är det nödvändigt att ha adresserna till två på varandra följande element.
Utförande av en XOR-operation på adressen för det första elementet och den sammansatta adressen lagrad i det andra elementet ger adressen för elementet som följer dessa två element.
XOR Att den sammansatta adressen lagrad i det första elementet och adressen för det andra elementet ger adressen för elementet som föregår dessa två element.
Den klassiska dubbellänkade listan lagrar separat adresserna till föregående och nästa element i listan, vilket kräver två pekare för att lagra:
... A B C D E ... –> next –> next –> next –> <– prev <– prev <– prev <–Overheaden för en XOR-länkad lista är hälften så mycket, eftersom den bara lagrar en "adress" - XOR-pekare till föregående och nästa element:
... A B C D E ... <–> A⊕C <-> B⊕D <-> C⊕E <->Bland bristerna kan vi nämna en mer komplex implementering, oförmågan att använda standardsopsamlaren , svårigheter med att felsöka programmet [1] .
Det används ganska sällan, eftersom det finns bra alternativ, till exempel en utökad länkad lista .