XOR Linked List

XOR Linked List

XOR Linked List는 메모리를 효율적으로 이용하는 Doubly Linked List이다.

원래 Doubly Linked List는 이전 노드와 다음 노드의 주소를 저장하기 위해 하나의 노드에 두 개의 공간을 필요로 한다.

그런데 XOR Linked List는 하나의 공간에 이전 노드와 다음 노드의 주소 둘 다 저장한다.
그러므로 메모리 사용이 줄어든다!

그러면 각 노드마다 저장된 npx로 이전 노드와 다음 노드의 주소를 어떻게 구할까?

이전 노드의 주소를 구하기 위해서는 npx와 다음 노드의 주소,
다음 노드의 주소를 구하기 위해서는 npx와 이전 노드의 주소가 필요하다.
(진행 방향 기준으로 이전 노드의 주소를 저장하면 됨)

예를 들어, 노드 B에서 C로 가는 주소를 구하고 싶다면 npx(B)와 addr(A)(이전 노드의 주소)를 사용한다.

npx(B) XOR addr(A)
= ( addr(A) XOR addr(C) ) XOR addr(A)
= addr(A) XOR addr(C) XOR addr(A)
= addr(C)

이렇게 C의 주소를 구할 수 있다.

.

.

.

(위 내용을 이용하여 XOR Binary Search Tree를 만들 수 있는가?)