Blazingly Fast Linked Lists

Linked lists are taught as fundamental data structures in programming courses, but they are more commonly encountered in tech interviews than in real-world projects.

In this post, I'll demonstrate a practical use case where a linked list significantly outperforms Vec. We will build a simple data validation library that shows the exact error location within invalid input, showcasing how a linked list can be used in graph traversals.

Starting with a naive approach, we’ll progressively implement various optimizations and observe their impact on performance.

Readers are expected to have a basic understanding of Rust, common data structures, and the concept of memory allocations (stack vs. heap).

The validation process boils down to graph traversal. The input instance is traversed based on rules defined in the schema. At any traversal step, we should know the current location within the JSON instance to potentially report a meaningful error.

Without diving too deep into the Validator and Node implementations, let's see a simplified version of the validation process without location tracking:

Leave a Comment