Deep C

개요

XOR 연결 리스트는 메모리를 절약하기 위해 고안된 특별한 이중 연결 리스트입니다. 일반적인 이중 연결 리스트와 달리 prev와 next를 별도로 저장하지 않고, 하나의 both 필드에 XOR 연산으로 저장합니다. 비트 연산, 포인터 개념, 순회 원리를 함께 묻는 자료구조 문제로, Google 인터뷰 계열로 알려져 있습니다.

both = 이전 노드 주소 XOR 다음 노드 주소

문제 설명

다음 기능을 구현하는 XOR 연결 리스트를 만들어야 합니다:

add(element): 원소를 리스트 맨 뒤에 추가
get(index): 해당 인덱스에 있는 노드를 반환

포인터가 없는 언어(파이썬 등)에서는 다음 함수들을 사용한다고 가정합니다:

get_pointer(node): 노드의 주소를 얻음
dereference_pointer(address): 주소로부터 노드를 얻음

작동 원리

XOR의 핵심 성질

A XOR B = C
C XOR A = B
C XOR B = A

현재 노드의 both 값과 이전 노드 주소를 알고 있으면, 다음 노드 주소를 계산할 수 있습니다.

핵심 아이디어: 이전에 어디에서 왔는지만 알고 있으면, 나머지 한쪽 주소를 복원할 수 있습니다.

구조 비교

일반 이중 연결 리스트:

[ prev | data | next ]

XOR 연결 리스트:

[ both | data ]

순회 시 "직전에 어느 노드에서 왔는지"를 기억해야 합니다.

순회 원리

현재 노드를 curr, 이전 주소를 prev_addr이라 하면:

next_addr = curr.both XOR prev_addr

처음 시작할 때는 prev_addr = 0으로 설정합니다.

정답 코드

class Node:
    def __init__(self, value):
        self.value = value
        self.both = 0


class XORLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.__nodes = {}

    def get_pointer(self, node):
        if node is None:
            return 0
        return id(node)

    def dereference_pointer(self, address):
        if address == 0:
            return None
        return self.__nodes[address]

    def add(self, element):
        new_node = Node(element)
        new_addr = self.get_pointer(new_node)
        self.__nodes[new_addr] = new_node

        if self.head is None:
            self.head = new_node
            self.tail = new_node
            return

        tail_addr = self.get_pointer(self.tail)

        # 기존 tail의 both는 prev XOR 0 상태였음
        # 새 노드를 뒤에 붙이면 prev XOR new_addr 가 되어야 함
        self.tail.both ^= new_addr

        # 새 노드의 both는 tail_addr XOR 0
        new_node.both = tail_addr
        self.tail = new_node

    def get(self, index):
        prev_addr = 0
        current = self.head
        current_index = 0

        while current is not None and current_index < index:
            next_addr = prev_addr ^ current.both
            prev_addr = self.get_pointer(current)
            current = self.dereference_pointer(next_addr)
            current_index += 1

        return current

실행 예시

xor_list = XORLinkedList()
xor_list.add(10)
xor_list.add(20)
xor_list.add(30)

print(xor_list.get(0).value)  # 10
print(xor_list.get(1).value)  # 20
print(xor_list.get(2).value)  # 30

add() 메서드 동작 방식

새 노드를 맨 뒤에 붙일 때는 기존 tail과 새 노드 둘 다 수정해야 합니다.

기존 tail 입장:

원래 tail의 다음 노드는 없으므로 both = prev XOR 0 상태
새 노드가 뒤에 붙으면 both = prev XOR new_addr로 변경

새 노드 입장:

이전은 기존 tail, 다음은 없음
both = tail_addr XOR 0

get() 메서드 동작 방식

get(index)는 순회하면서 이동합니다. 중요한 점은 이전 주소를 함께 관리해야 한다는 것입니다.

next_addr = prev_addr ^ current.both

이 계산으로 다음 노드 주소를 구하고, 한 칸 이동할 때마다 prev_addr를 현재 노드 주소로 갱신합니다.

시간 복잡도

연산	복잡도
`add(element)`	O(1)
`get(index)`	O(n)

뒤에 붙이기는 tail 포인터가 있어 빠르지만, 특정 인덱스 접근은 처음부터 순회해야 하므로 선형 시간이 걸립니다.

실무 관점

이 구조는 개념 확인용으로는 훌륭하지만, 가독성과 유지보수성이 떨어져 실제 서비스 코드에서는 거의 사용되지 않습니다.

파이썬에서의 구현 전략

파이썬은 진정한 포인터를 직접 다루지 않으므로, 다음과 같이 흉내냅니다:

id(node)를 포인터처럼 사용
딕셔너리에 주소: 노드 형태로 저장
필요할 때 주소로부터 노드 복원

핵심 요약

XOR 연결 리스트는 이전 정보와 현재 정보를 가지고 다음 정보를 복원하는 사고를 평가하는 문제입니다.

next_addr = prev_addr XOR current.both

이전 주소와 다음 주소를 하나의 필드에 XOR로 저장하는 구조이므로, 순회 시 이전 주소를 함께 관리해야 하며, 파이썬에서는 주소와 노드를 연결하는 별도 저장소를 두어 구현할 수 있습니다.

XOR 연결 리스트 — 메모리 절약형 이중 연결 리스트

개요