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

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

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

문제

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

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

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

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

왜 이 문제가 어렵게 느껴질까

일반 연결 리스트는 보통 현재 노드에서 next를 바로 따라가면 됩니다. 하지만 XOR 연결 리스트는 다음 노드 주소를 바로 저장하지 않습니다.

즉, 현재 노드 하나만 보고는 다음으로 어디로 가야 하는지 알 수 없습니다. 반드시 이전 노드 주소까지 같이 알고 있어야 다음 주소를 계산할 수 있습니다.

그래서 이 문제는 연결 리스트 문제이면서도, 동시에 이전 상태를 들고 이동하는 사고를 묻습니다.

핵심 아이디어

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으로 설정합니다.

순회 흐름을 한 번 따라가 보기

아래처럼 세 노드가 있다고 가정해 보겠습니다.

10 <-> 20 <-> 30

처음에는 10에서 시작하고, 이전 주소는 없으므로 prev_addr = 0입니다.

현재 노드	prev_addr	current.both	계산 결과
10	0	`0 XOR addr(20)`	다음은 `addr(20)`
20	`addr(10)`	`addr(10) XOR addr(30)`	다음은 `addr(30)`
30	`addr(20)`	`addr(20) XOR 0`	다음은 `0`

핵심은 매 단계마다 직전 주소를 기억한 채 both와 XOR하는 것입니다. 이전 주소를 잊어버리면 다음 노드를 복원할 수 없습니다.

코드

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

코드에서 특히 봐야 하는 부분

이 구현에서 가장 중요한 부분은 사실 add()보다 get()입니다. get() 안에 XOR 연결 리스트의 핵심 원리가 그대로 들어 있기 때문입니다.

next_addr = prev_addr ^ current.both

이 한 줄이 현재 노드의 both와 이전 주소를 이용해 다음 주소를 복원합니다. 즉, 이 문제는 XOR 성질을 이해했는지와, 순회 중 이전 상태를 어떻게 유지하는지까지 함께 묻는 문제입니다.

실행 예시

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

인덱스가 범위를 벗어나면 None이 반환됩니다.

print(xor_list.get(5))  # None

코드 해설

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를 현재 노드 주소로 갱신합니다.

실수하기 쉬운 부분

`prev_addr` 갱신 순서를 바꾸는 실수

다음 주소를 계산하기 전에 prev_addr를 먼저 바꿔버리면 계산이 깨집니다.

next_addr = prev_addr ^ current.both
prev_addr = self.get_pointer(current)

이 순서를 유지해야 지금 노드 기준으로 올바른 다음 주소를 얻을 수 있습니다.

파이썬에서 진짜 포인터처럼 착각하는 실수

이 구현은 파이썬에서 실제 메모리 포인터를 직접 다루는 것이 아닙니다. id(node)와 딕셔너리를 이용해 포인터처럼 흉내 내는 방식입니다.

즉, 개념 설명용 구현으로 보는 편이 맞습니다.

범위를 벗어난 인덱스를 바로 예외로 생각하는 실수

현재 코드는 인덱스가 너무 크면 None을 반환합니다. 문제 요구에 따라 예외를 던지도록 바꿀 수도 있지만, 지금 구현은 안전하게 None으로 끝나는 형태입니다.

복잡도

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

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

파이썬에서의 구현 전략

파이썬은 진정한 포인터를 직접 다루지 않으므로, 다음과 같이 흉내 내서 구현합니다.

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

왜 개념 문제로 더 자주 나오나

XOR 연결 리스트는 아이디어 자체는 흥미롭지만, 구현과 디버깅이 쉽지 않습니다. 특히 일반 이중 연결 리스트보다 코드가 직관적이지 않아서 읽기와 수정이 더 어렵습니다.

그래서 보통은 자료구조 원리나 비트 연산 이해를 확인하는 문제로 더 자주 다뤄집니다.

정리

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

next_addr = prev_addr XOR current.both

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