Original Project Repository
Single Header Project Repository

Summary

As the final project for the Data Structures course at UFC, I implemented a sparse matrix in C++ using orthogonal circular singly-linked lists. The original requirement included an interactive interface to manipulate the matrices via commands (as seen in the showcase GIF). Later, I refactored the core data structure code into a single header file, allowing straightforward integration into any C++ project.

Lessons Learned

The exercise consolidated theoretical concepts and demonstrated the importance of creating custom abstractions beyond the language’s standard library, particularly when managing complex pointer structures and sentinels.

Application and Efficiency

Sparse matrices are ideal for scenarios with a high density of default (or empty) values. The memory efficiency is significant:

  • Scenario: \(10,000 \times 10,000\) matrix (integers) with 10% fill.
  • Standard Matrix: Takes ~400 MB.
  • Sparse Matrix: Takes ~320 MB.
  • Space Saved: ~80 MB.