Data Structure Visualizations

A useful aid to understand complex data structures is to see them in action. We've developed interactive animations for a variety of data structures and algorithms. Our visualization tool is written in Javascript using the HTML5 canvas element, and run in just about any modern browser – including iOS devices like the iPhone and iPad, and even the web browser in the Kindle! (The frame rate is low enough in the Kindle that the visualizations aren't terribly useful, but the tree-based visualizations – BSTs and AVL Trees – seem to work well enough)

History

The code was originally developed by David Galles, University of San Francisco, in Java and then ported to Javascript in 2011. Some updates were made by Kostas Chatzikokolakis, and this current repository is maintained by Peter Ljunglöf, University of Gothenburg & Chalmers University of Technology.

Source code

All source code is available at the GitHub repository. Everything is licensed under FreeBSD, and you can use it for whatever you like.

Algorithm Specific Controls

At the top of the screen (boxed in red in the above screenshot) are the algorithm specific controls -- these will change depending upon what algorithm you are visualizing. For example, in a BST (binary search tree) you can insert, delete, or find an element in the BST by entering text in the appropriate field and either pressing return or clicking the relevant button. The tree can be printed by clicking the print button. Once you give a command, the visualiztion will start, and can be controlled by the general animation controls at the bottom of the screen.

General Animation Controls

• (Skip back): If you are in the middle of an animation, this button will completly undo the current command. If you are not in the middle of an animation, this button will undo the previous command.
• (Step back): This button is only active if you have paused the current animation (using the play/pause button). Step back one step in the current animation. If you are not currently animating, step back into the previous command. You could use this button (with sufficient keypresses) to back up through the entire history of everything you've done.
• (Play/pause): Toggle between play mode (in which the algorithm runs free until it completes) and paused mode (where you need to press the Step Forward or Step back button to advance the animation).
• (Step forward): This button is only active if you have paused the current animation (using the play/pause button), and the current animation has not yet completed. Step forward one step in the current animation.
• (Skip forward): This button is only active if the current animation has not completed. Skip to the end of the current animation.
• Animation speed: Change the speed of the animation. The value of this select box is saved in a cookie, so you should only need to set it once if you have a preferred speed.
• Canvas size: Change the percieved size of the display area. This will often clear out the current animation, but the new size is also saved in a cookie, so you should only need to change this field once.

Note that it can be easy to confuse yourself by stepping forward an backwards through an animation – you can confuse the next step in the animation with the previous step, and misunderstand how the algorithm works. You may wish to only step forward when you are first delving into a particular algorithm.

1. Can I use these materials in my classes?
   • Certainly! We'd prefer that you just link to these pages rather than cache anything locally so that your students will get the most up-to-date version of everything. If you do use this in your class, please drop us a line to let us know about it, we're curious to see who else will find this useful.
2. I think I've found a bug...
   • Please create an issue in the GitHub repository. Try to be specific – that is, exactly what sequence of operations lead to the undesired behavior.
3. How are elements ordered, e.g., when inserting elements into ordered search trees?
• Numbers are ordered numerically and strings are ordered lexicographically. Furthermore, Furthermore, we decided that all numbers are smaller than all strings.
4. How can I get this to work on my cellphone, which has a very small screen?
• If you change the canvas size to something that seems reasonable for your device, we will use a cookie to remember your preferred size. However, some visualizations (e.g., sorting and graphs) require that the canvas size is large, which makes them difficult to work with on a cellphone.
5. Wait ... you are using cookies?
• Only for remembering your preferred animation speed and canvas size. Everything will still work if you disable cookies. We aren't doing tracking of any kind.
6. Can I use this material as a base for my own visualizations?
• Yes! See the GitHub repository for a simple tutorial and links to the source code. If you do use the code, please leave in the copyright information at the beginning of each source file, and put a link to these pages from the page where your visualizations are located. If you create something really cool, please let us know.