#XorLinkedList

#🚀 Core Features

#📥 Installation

moon add SupremeHuaji/XorLinkedList

#🚀 Usage Guide

#🔨 Creating a List

    // Create an empty list
    let list = new()

    // Add elements
    list.push_front(1)    // Add to the front
    list.push_back(3)     // Add to the back
    list.push_front(0)    // Result: [0, 1, 3]

    // Check basic information
    println("List length: \{list.len()}")        // Output: 3
    println("Is list empty: \{list.is_empty()}") // Output: false

#➕ Adding and Removing Elements

    let list = new()

    // Add elements
    list.push_back(10)
    list.push_back(20)
    list.push_front(5)    // [5, 10, 20]

    // Remove elements
    let first = list.pop_front()  // first = Some(5), list = [10, 20]
    println("Removed first element: \{first}")

    let last = list.pop_back()    // last = Some(20), list = [10]
    println("Removed last element: \{last}")

    // Clear the list
    list.clear()
    println("Length after clearing: \{list.len()}")  // Output: 0

#🔍 Accessing Elements

    let list = new()

    // Add test data
    list.push_back(10)
    list.push_back(20)
    list.push_back(30)
    list.push_back(40)

    // Access by index
    let element = list.get(2)
    println("Element at index 2: \{element}")  // Output: Some(30)

    // Get first and last elements
    let first = list.head()
    let last = list.last()
    println("First element: \{first}, Last element: \{last}")  // Output: Some(10), Some(40)

    // Find elements
    let index = list.index_of(30)
    println("Index of element 30: \{index}")  // Output: Some(2)

    // Check if an element exists
    if list.contains(20) {
    println("List contains element 20")
    }

#🎯 Traversal and Transformation

    let list = new()

    // Add test data
    list.push_back(1)
    list.push_back(2)
    list.push_back(3)

    // Forward traversal
    println("Forward traversal:")
    list.each(fn(val) {
    println("  \{val}")
    })

    // Reverse traversal
    println("Reverse traversal:")
    list.each_reverse(fn(val) {
    println("  \{val}")
    })

    // Convert to array
    let array = list.to_array()
    println("List converted to array: \{array}")  // Output: [1, 2, 3]

#🔄 Functional Operations

    let list = new()

    // Add test data
    list.push_back(1)
    list.push_back(2)
    list.push_back(3)
    list.push_back(4)
    list.push_back(5)

    // Map operation: double each element
    let doubled = list.map(fn(x) { x * 2 })
    println("After doubling: \{doubled.to_array()}")  // Output: [2, 4, 6, 8, 10]

    // Filter operation: keep only even numbers
    let evens = list.filter(fn(x) { x % 2 == 0 })
    println("Even elements: \{evens.to_array()}")  // Output: [2, 4]

    // Fold operation: calculate sum
    let sum = list.fold(0, fn(acc, x) { acc + x })
    println("Sum of elements: \{sum}")  // Output: 15

    // Take first N elements
    let first_three = list.take(3)
    println("First three elements: \{first_three.to_array()}")  // Output: [1, 2, 3]

#🛠️ Structure Modification

    let list = new()

    // Add unsorted data
    list.push_back(3)
    list.push_back(1)
    list.push_back(4)
    list.push_back(2)

    // Sort the list
    list.sort()
    println("After sorting: \{list.to_array()}")  // Output: [1, 2, 3, 4]

    // Reverse the list
    list.reverse()
    println("After reversing: \{list.to_array()}")  // Output: [4, 3, 2, 1]

    // Insert separator values between elements
    let separated = list.intersperse(0)
    println("After inserting separators: \{separated.to_array()}")  // Output: [4, 0, 3, 0, 2, 0, 1]

    // Remove an element at a specific position
    let removed = list.remove_at(1)
    println("Removed element at index 1: \{removed}")  // Output: Some(3)
    println("After removal: \{list.to_array()}")    // Output: [4, 2, 1]

#🔗 Merging Operations

    let list1 = new()
    list1.push_back(1)
    list1.push_back(2)

    let list2 = new()
    list2.push_back("a")
    list2.push_back("b")

    // Zip two lists into a tuple list
    let zipped = list1.zip(list2)
    println("Zip result:")
    zipped.each(fn(pair) {
    println("  \{pair.0} - \{pair.1}")
    })
    // Output:
    // 1 - a
    // 2 - b

#📊 Performance Characteristics

• n = Number of elements in the list

#🏗️ Implementation Details

#📦 Core Data Structures

1. Node Structure (Node)
   • Content: Stores the actual value and a link field
   • Link Field: XOR of predecessor node ID and successor node ID
   • Advantage: Implements bidirectional linking with a single pointer

2. List Structure (T)
   • Head and Tail Pointers: Track the first and last nodes of the list
   • Node Array: Stores all nodes
   • Free ID List: Tracks reusable node positions
   • Size Counter: Current number of list elements

#🔄 XOR Linked List Working Principle

// XOR Linked List Basic Principle
// Assuming nodes A, B, C are linked in sequence:

// Regular Doubly Linked List:
// A.prev = null, A.next = &B
// B.prev = &A,   B.next = &C
// C.prev = &B,   C.next = null
// Total of 6 pointer fields required

// XOR Linked List:
// A.link = null XOR &B = &B
// B.link = &A XOR &C
// C.link = &B XOR null = &B
// Total of 3 pointer fields required, saving 50% memory

// Traversal Method:
// Starting from A, knowing prev=null:
//   next = prev XOR A.link = null XOR &B = &B
//   Move to B, and remember prev=&A
// Continue from B, knowing prev=&A:
//   next = prev XOR B.link = &A XOR (&A XOR &C) = &C
//   Move to C, and remember prev=&B
// And so on...

#📈 Node ID Reuse Mechanism

// When a node is deleted:
1. Disconnect the node from the list
2. Add the node ID to the free ID list
3. Set the corresponding position in the node array to None

// When a new node is created:
1. Preferentially get an ID from the free ID list
2. If the free list is empty, add a new node at the end of the node array

#🆚 XorLinkedList vs Traditional Linked Lists

#🤝 Contributing

1. Fork this repository
2. Create a feature branch (git checkout -b feature/AmazingFeature)
3. Commit your changes (git commit -m 'Add some AmazingFeature')
4. Push to the branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

#📜 License

#🔗 Related Resources

• XOR Linked List Principle Introduction
• MoonBit Language Documentation