List Labeling Array (LLA)

This is a C implementation of a List Labeling Array data structure. I originally built it to understand the classical online list labeling problem more concretely, and it now serves as useful background for my interest in algorithms with predictions.

The data structure maintains a sorted array with O(log²n) insertion time and O(log²n) amortized elements moved per insertion.

Key Features

• O(log²n) insertion time
• O(log²n) amortized elements moved per insertion
• Density-based rebalancing strategy
• Memory-efficient implementation
• Configurable parameters for balancing

Implementation Details

Data Structure

The LLA consists of two main components:

1. A sorted array storing the elements
2. A balancing tree that manages the density of array segments

Key Parameters

• N: Size of the array
• C: Capacity factor
• TAU_0: Initial density threshold
• TAU_D: Maximum density threshold

Core Operations

• create_lla(N, C, TAU_0, TAU_D): Creates a new LLA instance
• insert(lla, x): Inserts element x while maintaining sorted order
• cleanup_lla(lla): Frees all allocated memory

Building and Running

Prerequisites

• GCC compiler
• Make
• entr (for auto-rebuild feature)

Building

make

Running

./program

Auto-Rebuild and Run

To automatically rebuild and run when source files change:

./watch.sh

Cleaning

make clean

Performance Testing

The project includes a performance test suite that:

• Measures insertion time complexity
• Verifies O(log²n) amortized time
• Provides correlation analysis with theoretical complexity
• Reports detailed timing statistics

Project Structure

.
├── lla.h          # Header file with declarations
├── lla.c          # Implementation file
├── main.c         # Test driver and performance measurements
├── Makefile       # Build configuration
└── watch.sh       # Auto-rebuild script

Dependencies

• entr for auto-rebuild feature:
  • macOS: brew install entr
  • Ubuntu/Debian: sudo apt-get install entr
  • Fedora: sudo dnf install entr

Usage Example

#include "lla.h"

int main() {
    // Create LLA with N=1024, C=8, TAU_0=0.5, TAU_D=0.75
    lla *my_lla = create_lla(1024, 8, 0.5, 0.75);
    
    // Insert elements
    insert(my_lla, 10);
    insert(my_lla, 5);
    insert(my_lla, 15);
    
    // Print current state
    print_lla(my_lla);
    
    // Cleanup
    cleanup_lla(&my_lla);
    return 0;
}

References

1. McCauley, S., Moseley, B., Niaparast, A., & Singh, S. (2023). Online List Labeling with Predictions. arXiv:2305.10536

2. Bender, M. A., & Hu, H. (2007). An adaptive packed-memory array. ACM Transactions on Database Systems, 32(4), 26-es. https://doi.org/10.1145/1292609.1292616