In Part 1 we learned the basic principals behind building a virtual scroll mechanism, the math behind it, and saw some psuedo-code and some real code.

If you haven't read it yet, I suggest you start from there to get to know the terminology: part I

In Part 1 we assumed the row height is always fixed, which made our lives much easier. But how can we support dynamic height, and do we have to let the user supply the height or can we figure it out automatically?

Automatic Height?

Let's answer the second question first. Figuring out the height of unrendered nodes is not a trivial task, and a costly one. It requires rendering them offscreen and handling some potential edgecases, and is a big problem on its own. We won't be discussing this problem in this tutorial.

Dynamic Height

Nevertheless, we can support a dynamic height by allowing the user to supply a function that returns the height per row. This is something the user can calculate offline by rendering different types of rows per row type.

This makes our calculations more complex since we can't just multiply or divide by rowHeight.

Calculating the Nodes' Positions

When we initialize the component, we will calculate each node's position, which will help us with all the calculation steps that we had in Part 1.

We also need to react to changes in the array of items and recalculate the positions of the entire array if it changed. This is usually achievable in modern FE frameworks.

To calculate a node's position, we take the position of the previous node and add the height of the previous node.

We have to make a full pass when we start

The Container Height

Now that we have the nodes' positions, it's a very straightforward step. We simply take the last node's position and add its height.

Figuring Out the Visible Nodes

To figure this out, we need to start with the first visible node. Now that we have the node's positions calculated, this is basically finding the bottom-most node that is above the scroll position.
Sounds simple, but since the positions are dynamic, we cannot simply locate that node with a math calculation.

Naive Solution

The naive solution would be to iterate over the nodes from the start until we find a node whose position is larger than scrollTop. But this is obviously a bad strategy. This calculation will be done very frequently as the user scrolls and must be extremely performant.

Binary Search

Because our nodes are already sorted, we can do a binary search.

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. https://www.geeksforgeeks.org/binary-search/

The advantage is that the complexity is O(log n). Meaning that even if you have a million nodes, you will make only around 20 comparisons.

Usually, in binary search, we look for a specific value. Here, we look for a node that is above the scroll position, while the next node's position is below it.

After we find the first node we reduce the node padding as we did in Part 1.

Now to figure out the number of visible nodes, we simply add nodes until we reach a node position that's greater than scrollTop + viewport height and add the padding as well.

Shifting the nodes down

Since we have the node's positions, our offsetY is simply the first node's position.

Et voila

That's it, this gets us the same numbers we had in Part I, and we can render the visible nodes and shift them down.

Performance Optimizations

You probably realize that doing all of these calculations can be costly.
Scroll events can fire very rapidly as the user scrolls, and we want to make sure we don't make too many extra calculations otherwise the UI might be sluggish.
Most displays use 60fps, and recalculating faster than that is just a waste of resources.

Throttling

One way to accomplish that is by throttling.

Throttling gives us control over the rate at which a function is called. For example, if an event fires every millisecond, and we want the callback to handle events only every 17ms and ignore the events in between.

So you can throttle the scroll event callback to 17ms, and make sure the last event (tail) is also handled.

requestAnimationFrame

My preferred way is using requestAnimationFrame.

The window.requestAnimationFrame() method tells the browser that you wish to perform an animation and requests that the browser shall call a specified function to update an animation before the next repaint. The method takes a callback as an argument to be invoked before the repaint. More info: https://developer.mozilla.org/en-US/docs/Web/API/window/requestAnimationFrame

This will guarantee your calculations will run at 60fps. It means that the scroll event needs to run the calculations in requestAnimationFrame. But how can you prevent registering multiple callbacks in one animation frame? You can simply cancel the previous callback (if it exists), and request another one.

Example

Here is an example with dynamic heights using React, binary search, and virtual scrolling, using React and hooks:
https://codesandbox.io/s/virtual-scroll-dynamic-heights-using-hooks-6gmgu

Virtual scroll on a tree

One of the more complex things I've developed was virtual scrolling on a tree. The tree adds another complexity that each level might be expanded or collapsed, and the traversal on the tree is nested.

One way to overcome this is to flatten the tree. Meaning every time you expand or collapse a node you insert or remove nodes from the flat array, and recalculate the nodes' positions. Then, the virtual scroll behaves like a regular virtual scroll on a list.

The other way (which I took), is to calculate the node positions based on the current status of the tree (which one is expanded and which one is collapsed). Traversing the tree to find the visible nodes is done recursively on the tree.

You can check out the source code for that here:
https://github.com/500tech/angular-tree-component/blob/master/lib/models/tree-virtual-scroll.model.ts

Thanks and I hoped you enjoyed the 2 part blog!