All Courses
AI Career Planner
1:1 Coaching/Mentoring
Job Board
SQL
HTML/CSS/JS
Coding
Settings
LogoutA Memory Efficient Doubly Linked List is an XOR linked list. In a standard Doubly Linked List, two address fields are required to hold the addresses of previous and next nodes. With each node, a memory efficient version of Doubly Linked List may be built by utilizing only one space for the address field. Because the list employs the bitwise XOR operation to conserve space for one address, it is known as the XOR Linked List or Memory Efficient.
Instead of storing real memory locations, each node in the XOR linked list stores the XOR of the addresses of the preceding and next nodes.
XOR linked lists are doubly linked lists which store addresses in just one field instead of two in traditional doubly linked lists.
XOR has a very special property about it, namely, given a XOR b = c, only two (any two) of the variable are required to compute the the third, with some restrictions.
In this case the previous (or next) pointer must still be carried, but only through traversal calculations and not as a separate member.