XOR 연결 리스트

XOR 연결 리스트 또는 XOR 링크드 리스트(XOR linked list)는 컴퓨터 프로그래밍에서 사용되는 자료 구조의 한 종류이다. 이는 이중 연결 리스트의 저장 공간 요구 사항을 줄이기 위해 비트 XOR 연산을 활용하여 두 주소의 구성을 하나의 필드에 저장한다. 구성된 주소는 그 자체로는 의미가 없지만, 순회 시 이전에 방문한 노드 주소에 대한 지식과 결합하여 다음 노드의 주소를 추론할 수 있다.

설명

일반적인 이중 연결 리스트는 각 리스트 노드에 이전 및 다음 리스트 항목의 주소를 저장하므로 두 개의 주소 필드가 필요하다.

 ... A        B        C         D         E ...
         –>  next –>  next  –>  next  –>
         <–  prev <–  prev  <–  prev  <–

XOR 연결 리스트는 이전 주소와 다음 주소의 비트 XOR(여기서는 ⊕로 표시)을 하나의 필드에 저장하여 동일한 정보를 하나의 주소 필드로 압축한다.

 ... A        B          C          D         E ...
         ⇌   A⊕C   ⇌   B⊕D   ⇌   C⊕E   ⇌

더 공식적으로는:

  link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), ...

리스트를 왼쪽에서 오른쪽으로 순회할 때: 커서가 C에 있고 이전 항목이 B라고 가정하면, B는 링크 필드(B⊕D)의 값과 XOR될 수 있다. 그러면 D의 주소를 얻게 되고 리스트 순회를 재개할 수 있다. 동일한 패턴이 다른 방향에도 적용된다.

즉, addr(D) = link(C) ⊕ addr(B) 여기서

      link(C) = addr(B)⊕addr(D)

따라서

      addr(D) = addr(B)⊕addr(D) ⊕ addr(B)

      addr(D) = addr(B)⊕addr(B) ⊕ addr(D)

왜냐하면

       X⊕X = 0
       => addr(D) = 0 ⊕ addr(D)

왜냐하면

       X⊕0 = X
       => addr(D) = addr(D)

XOR 연산은 식에 두 번 나타나는 addr(B)를 상쇄하고 남는 것은 addr(D)뿐이다.

어떤 지점부터 리스트를 양방향으로 순회하려면 연속된 두 항목의 주소가 필요하다. 연속된 두 항목의 주소가 역전되면 리스트 순회는 반대 방향으로 발생한다.

작동 원리

핵심은 첫 번째 연산과 XOR의 속성이다.

• X⊕X = 0
• X⊕0 = X
• X⊕Y = Y⊕X
• (X⊕Y)⊕Z = X⊕(Y⊕Z)

R2 레지스터는 항상 현재 항목 C의 주소와 선행 항목 P의 주소의 XOR 값인 C⊕P를 포함한다. 레코드의 링크 필드에는 왼쪽 및 오른쪽 후속 주소의 XOR 값, 예를 들어 L⊕R이 포함된다. R2(C⊕P)와 현재 링크 필드(L⊕R)의 XOR 연산은 C⊕P⊕L⊕R을 생성한다.

• 선행 항목이 L이었다면 P(=L)와 L은 상쇄되어 C⊕R이 남는다.
• 선행 항목이 R이었다면 P(=R)와 R은 상쇄되어 C⊕L이 남는다.

각 경우에 결과는 현재 주소와 다음 주소의 XOR 값이다. 이 값을 R1의 현재 주소와 XOR하면 다음 주소가 남는다. R2에는 (이제) 현재 주소와 선행 주소의 필수 XOR 쌍이 남는다.

특징

• 두 번의 XOR 연산으로 한 항목에서 다음 항목으로의 순회가 충분하며, 두 경우 모두 동일한 명령이 충분하다. {…B C D…} 항목이 있는 리스트를 고려하고, R1과 R2는 각각 현재(예: C) 리스트 항목의 주소와 이전 주소(예: C⊕D)의 XOR을 포함하는 작업 레지스터를 포함한다고 가정하자. System/360 명령으로 구성하면 다음과 같다.

X  R2,Link    R2 <- C⊕D ⊕ B⊕D (즉, B⊕C, "Link"는 현재 레코드의
                                  링크 필드이며 B⊕D를 포함한다)
XR R1,R2      R1 <- C ⊕ B⊕C    (즉, B, 바로 다음 레코드)

• 리스트의 끝은 {0 A B C…}처럼 주소 0에 있는 리스트 항목이 끝점에 인접하게 배치된 것으로 상상하여 나타낸다. A의 링크 필드는 0⊕B가 될 것이다. 현재 항목의 주소를 개발할 때 0 결과를 감지하기 위해 위의 두 XOR 연산 시퀀스 후에 추가 명령이 필요하다.
• 리스트 끝점은 링크 포인터를 0으로 만들어 반사적으로 만들 수 있다. 0 포인터는 거울이다. (왼쪽 및 오른쪽 이웃 주소의 XOR이 동일하면 0이다.)

단점

• 일반적인 디버깅 도구는 XOR 체인을 따라갈 수 없어 디버깅이 더 어려워진다.
• 메모리 사용량 감소의 대가는 코드 복잡성 증가로, 유지보수 비용이 더 많이 든다.
• 대부분의 쓰레기 수집 방식은 리터럴 포인터를 포함하지 않는 자료 구조에서는 작동하지 않는다.
• 모든 언어가 포인터와 정수 간의 형 변환을 지원하는 것은 아니며, 포인터에 대한 XOR은 일부 컨텍스트에서 정의되지 않는다.
• 리스트를 순회하는 동안 다음 노드의 주소를 계산하기 위해 이전에 접근한 노드의 주소가 필요하며, 리스트를 순회하지 않으면 포인터를 읽을 수 없다. 예를 들어, 리스트 항목에 대한 포인터가 다른 자료 구조에 포함된 경우.
• XOR 연결 리스트는 이중 연결 리스트의 중요한 장점 중 일부를 제공하지 않는다. 예를 들어, 노드의 주소만 알고 노드를 리스트에서 삭제하는 기능이나, 기존 노드의 주소만 알고 기존 노드 앞이나 뒤에 새 노드를 삽입하는 기능 등.

컴퓨터 시스템은 점점 더 저렴하고 풍부한 메모리를 가지므로, 임베디드 시스템과 같은 특수 분야를 제외하고는 저장 공간 오버헤드가 일반적으로 최우선 문제는 아니다. 연결 리스트의 오버헤드를 줄이는 것이 여전히 바람직한 경우, 풀림은 더 실용적인 접근 방식을 제공한다(캐시 성능 향상 및 임의 접근 속도 향상과 같은 다른 이점도 있음).

변형

XOR 연결 리스트의 기본 원리는 모든 가역 이진 연산에 적용할 수 있다. XOR를 덧셈이나 뺄셈으로 바꾸면 약간 다르지만 대체로 동일한 형태가 된다.

덧셈 연결 리스트

 ...  A        B         C         D         E  ...
          ⇌   A+C   ⇌   B+D   ⇌   C+E   ⇌

이러한 종류의 리스트는 XOR 연결 리스트와 정확히 동일한 속성을 가지며, 0 링크 필드가 "거울"이 아니라는 점만 다르다. 리스트의 다음 노드 주소는 이전 노드의 주소를 현재 노드의 링크 필드에서 빼서 얻는다.

뺄셈 연결 리스트

 ...  A        B         C         D         E  ...
          ⇌   C-A   ⇌   D-B   ⇌   E-C   ⇌

이러한 종류의 리스트는 표준 "전통적인" XOR 연결 리스트와 달리 리스트를 앞으로 순회하는 데 필요한 명령 시퀀스가 리스트를 역방향으로 순회하는 데 필요한 시퀀스와 다르다. 앞으로 나아갈 때 다음 노드의 주소는 링크 필드를 이전 노드의 주소에 더하여 얻는다. 이전 노드의 주소는 링크 필드를 다음 노드의 주소에서 빼서 얻는다.

뺄셈 연결 리스트는 리스트의 각 주소에 일정한 오프셋을 더해도 링크 필드에 저장된 값을 변경할 필요가 없으므로, 포인터 값의 패치 없이 전체 리스트를 메모리에서 재배치할 수 있다는 점에서도 특별하다. (직렬화 참조.) 이는 XOR 연결 리스트와 전통적인 연결 리스트 모두에 비해 장점이다.

이진 탐색 트리

XOR 연결 리스트 개념은 XOR 이진 탐색 트리로 일반화될 수 있다.

같이 보기

• XOR 교체 알고리즘

외부 링크

• Prokash Sinha (2004년 12월 1일). “A Memory-Efficient Doubly Linked List”. 《Linux Journal》. 
• XORList: 효율적인 C++ 연결 리스트 (MIT 라이선스)
• 라이브러리 Listes에서 Xor 리스트의 C++ 구현.