Eager and lazy data structures are two different approaches to handling data manipulation and computation. The primary difference between the two is when the computation is performed.
Eager data structures, also known as strict data structures, compute their results immediately upon receiving input. This means that whenever a value is added or modified in the data structure, any relevant computations are performed right away. Eager data structures are useful when the amount of data is small, and there are no significant computational overheads to worry about.
Examples of eager data structures include arrays, linked lists, and binary search trees. When an element is added to an array, for instance, the size of the array increases immediately, and the new value is assigned to the appropriate index.
Lazy data structures, also known as non-strict data structures, defer computations until the results are needed. This approach is useful when the computation is expensive, and it is not necessary to compute all possible results upfront. Lazy data structures can be more efficient than eager data structures when dealing with large amounts of data because the computations are only performed when needed.
Examples of lazy data structures include lazy evaluation in functional programming, and lazy propagation in segment trees. In functional programming, expressions are not evaluated immediately but are instead stored as unevaluated thunks that are evaluated only when their results are needed. In segment trees, lazy propagation is used to defer updates to the tree until they are necessary, thus reducing the number of updates that need to be performed.
In summary, the choice between eager and lazy data structures depends on the specific requirements of the problem at hand. Eager data structures are useful when the data is small, and the computations are inexpensive, while lazy data structures are more efficient when dealing with large amounts of data and expensive computations.