Questions
3 of 16
1How do you merge two sorted Linked Lists?
2What is a Sentinel Node/Dummy Node? Why is it useful?
3What is an XOR Linked List? Why is it rarely used?
4Why is insertion/deletion at the head of a Linked List O(1)?
5How do you find the middle of a Linked List in one pass?
6Explain the difference between a Linked List and an Unrolled Linked List.
7How do you detect a cycle in a Linked List? (Floyd's Tortoise and Hare)
8How do you reverse a Linked List? (Iterative and Recursive)
9Why does the standard library (Java/C#) not heavily feature Linked Lists? (Cache locality issues)
10How do you copy a Linked List with random pointers? (Deep Copy)
11Explain why QuickSort is preferred over MergeSort for Arrays, but MergeSort is preferred for Linked Lists.
12What are the types of Linked Lists? (Singly, Doubly, Circular)
13Why is accessing an element in a Linked List O(n)?
14What is a Linked List? How does it differ from an Array?
15When would you choose a Linked List over an Array?
16What is a Skip List? How does it improve search time?
Data-StructuresData-Structures
Basics
Complexity Analysis
Arrays and Strings
Linked Lists
Stacks and Queues
Hash Tables
03 / 16

What is an XOR Linked List? Why is it rarely used?

XOR Linked List

javascript
  1. 1

    It can reduce the memory used for two link fields to one XOR field.

  2. 2

    It requires pointer/address arithmetic that is unsafe or unavailable in many managed languages.

  3. 3

    It complicates debugging and memory management.

  4. 4

    Garbage collectors generally do not work naturally with XOR-encoded references.

  5. 5

    It can be difficult to reason about, maintain, and integrate with modern runtimes.

  6. 6

    The small memory saving rarely justifies the complexity in modern application software.

Difficulty: 5/10

Follow-up Questions

  • ❓Why does XOR allow reconstruction of the neighboring address?
  • ❓Why is this unsuitable for Java?
  • ❓What are safer alternatives for reducing node overhead?