XOR 연결 리스트 계산기
이중연결리스트에서 앞·뒤 포인터를 따로 두지 않고 두 이웃 주소의 XOR 값 하나만 저장해 메모리를 절반으로 줄이는 기법입니다. 가상의 주소를 배정해 링크 값이 실제로 계산되는 과정과, 그 값만으로 순회가 되는 과정을 보여줍니다.
쉼표나 공백으로 구분합니다.
노드 수
5개
포인터를 하나만 저장해 이중연결리스트보다 메모리를 절반으로 줄입니다
노드마다 배정된 가상 주소와 link
| 값 | 주소 | link (=이웃 주소들의 XOR) |
|---|---|---|
| 가 | 1000 | 1008 |
| 나 | 1008 | 16 |
| 다 | 1016 | 2032 |
| 라 | 1024 | 2032 |
| 마 | 1032 | 1024 |
정방향 순회 (첫 노드에서 시작)
| 값 | 온 주소 | link ⊕ 온 주소 = 다음 |
|---|---|---|
| 가 | 0 | 1008 |
| 나 | 1000 | 1016 |
| 다 | 1008 | 1024 |
| 라 | 1016 | 1032 |
| 마 | 1024 | 0 (끝) |
역방향 순회 (마지막 노드에서 시작)
마 → 라 → 다 → 나 → 가
사용 방법
- 1리스트에 넣을 값들을 순서대로 입력합니다.
- 2각 노드에 배정된 가상 주소와 link(=이웃 주소들의 XOR) 값을 확인합니다.
- 3정방향(첫 노드부터)·역방향(마지막 노드부터) 순회가 link 값만으로 이뤄지는 과정을 봅니다.
자주 묻는 질문
보통의 이중연결리스트는 노드마다 prev·next 주소 두 개를 저장합니다. XOR 연결 리스트는 그 대신 link = prev ⊕ next 하나만 저장해 포인터에 드는 메모리를 절반으로 줄입니다.
XOR은 자기 자신을 두 번 적용하면 원래대로 돌아옵니다(a⊕b⊕b=a). 그래서 "지금 어디서 왔는지"(cameFrom)만 따로 들고 있으면, 다음 주소 = 지금 노드의 link ⊕ cameFrom으로 정확히 복원됩니다. link 하나에 두 주소의 정보가 접혀 들어가 있고, cameFrom이 그것을 펼치는 열쇠인 셈입니다.
리스트의 양 끝(첫 노드나 마지막 노드)에서 cameFrom=0(=null)으로 시작합니다. 그러면 첫 노드의 link(=0⊕next)를 0과 XOR한 결과가 그대로 next가 되어 자연스럽게 다음 자리로 넘어갑니다. 중간 노드에서 cameFrom 없이 시작하면 두 이웃 주소가 뒤섞인 값이 나와 순회가 무너집니다 — 그래서 반드시 한쪽 끝에서 시작해야 합니다.
이 트릭이 성립하려면 주소를 고정된 정수 하나로 다룰 수 있어야 합니다. 가비지 컬렉터가 객체를 옮겨 다니며 회수하는 자바스크립트 같은 언어에서는 "주소"가 고정되어 있지 않아 그대로 쓸 수 없습니다. 그래서 임베디드 시스템처럼 메모리를 직접 다루는 저수준 환경에서나 실제로 쓰이는, 교육적 의미가 큰 고전 기법입니다.
전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 정방향 순회가 원래 넣은 순서와, 역방향 순회가 그 뒤집힌 순서와 정확히 같은지 리스트 길이 1~20에서 확인했습니다.
- 중간 노드에서 cameFrom 없이 시작하면 실제로 존재하지 않는 뒤섞인 주소가 나와 순회가 무너지는지 확인했습니다 — 양 끝에서만 시작해야 한다는 성질을 직접 검증한 것입니다.
- 단일 노드 리스트(양 끝이 곧 자기 자신인 경우)도 한 걸음만에 올바르게 끝나는지 확인했습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.