Data Structure Visualization:Introduction and Value of Data Structure Rendering

Introduction

Important advances in programming languages have occurred since the early days of assembly languages and op codes, and modern programming languages have significantly simplified the task of writing computer programs. Unfortunately, tools for understanding programs have not achieved the accompanying levels of improvement. Software developers still face difficulties in understanding, analyzing, debugging, and improving code.

As an example of the difficulties still evident, consider a developer who has just implemented a new algorithm and is now ready to examine the program’s behavior. After issuing a command to begin program execution, the developer examines output data and/or inter- active behavior, attempting to ascertain if the program functioned correctly, and if not, the reasons for the program’s failure. This task can be laborious and usually requires the use of a debugger or perhaps even the addition of explicit checking code, usually through output statements. Furthermore, the process can be quite challenging and the average developer may not be that skilled in fault diagnosis and correction. It would be extremely advanta- geous to have a tool that allows programmers to “look inside” programs as they execute, examining the changes to data and data structures that occur over time. Such a tool also could provide helpful context by identifying the current execution line, the active program unit, and the set of activations that have occurred to reach this configuration.

Tools, such as the one described above, are one form of software visualization [1]. Price, Baecker, and Small describe software visualization as, “the use of the crafts of typography, graphic design, animation, and cinematography with modern human-computer interaction and computer graphics technology to facilitate both the human understanding and effec- tive use of computer software [2].” Fundamentally, software visualization seeks to take advantage of the visual perception and pattern matching skills of people to assist software development and software understanding. Human beings have very sophisticated visual perception systems that we constantly use to help us think [3]. Software visualization is a subfield in the larger area of information visualization [4, 5] that studies how visualizations serve as external cognition aids.

Software visualization research and systems fall into two primary categories, program visualization and algorithm visualization.

Program visualization systems present data about and attributes of some existing soft- ware system. Typically, program visualizations are used in a software engineering context, that is, to help design, implement, optimize, test, or debug software. Thus, program visu- alization systems often illustrate source code, program data, execution statistics, program analysis information, or program objects such as data structures. The imagery in program visualization systems also is usually displayed with little or no input from the user/viewer. That is, a program (source code or executable) is analyzed by the system, which then automatically produces the graphics when the user requests them.

Algorithm visualization, conversely, strives to capture the abstractions and semantics of an algorithm or program primarily for pedagogical purposes. One often thinks of algorithm visualization as being more “high-level” as compared to program visualization being more “low level.” The term algorithm animation is used interchangeably for this area simply because the displays are so dynamic and algorithm operations appear to animate over time. More specifically, Brown states, “Algorithm animation displays are, essentially, dynamic displays showing a program’s fundamental operations—not merely its data or code [6].” Algorithm visualizations typically are hand-crafted, user-conceptualized views of what is “important” about a program. These types of views usually require some person, often the system developer or the program’s creator, design and implement the graphics that accompany the program. The highly abstract, artificial nature of algorithm animations makes their automatic generation exceptionally difficult.

This chapter focuses on one specific subarea of software visualization, the visualization of data structures. By displaying pictures of data structures, one seeks to help people better understand the characteristics and the use of those structures.

How the data in computer programs are manipulated and organized by groups is a key aspect of successful programming. Understanding how elements of the data relate to other elements is a vital component in being able to comprehend and create sophisticated algorithms and programs. The word “structure” in “data structure” simply reinforces this point.

A person learning a new piece of software and seeking to modify it for some added functionality will likely ask a number of different questions. How are data elements organized? Is some kind of sequential structure used or is a more complicated organization present? Which items reference which other items? Understanding the answers to questions such as these helps a person to understand the utility and value of data structures. Providing pictures to express the relationships of data elements clearly then is one of the most useful ways to answer those questions.

Value of Data Structure Rendering

The graphical display of data structures can benefit a number of different activities, and one key role is as an aid for computer science education. It is not uncommon for students to have difficulty learning to understand and use non-trivial data structures such as arrays, lists, stacks, queues (Chapter 2), and trees (Chapter 3).

One common problem occurs in the mapping back-and-forth between the pseudo code or programming language implementation of a structure and its conceptual model. In current educational methods, to foster understanding, the conceptual model (abstraction) is often presented in some graphical representation or picture—an interesting challenge is to find a book about data structures that does not make liberal use of pictures.

Systems for visualizing data structures typically provide or operate in an environment containing both the structures’ programming language implementation and their graphical display, which facilitates students making connections between the two. This allows an instructor to prepare a collection of “interesting” data structures for students to interact with and learn from. By examining the accompanying displays, students can make the connection from a structure’s abstract properties to its concrete implementation.

Another activity in which data structure visualization systems can provide significant help is program debugging. When a data structure display tool is used in conjunction with a traditional textual debugger, it allows the active data structures to be displayed and examined in some graphical format as program execution occurs and units of code are examined. When the program’s data change, the accompanying visualizations change too, reflecting the new program state.

The graphical display of data structures adds many advantages to strict textual debugging. Because a human’s visual perception system is a highly-tuned information processing machine, the sheer amount of information that can be transmitted to the user is much greater using graphics. With a textual debugger, people usually need to issue queries variable-by-variable to discover values. One glance at a computer display showing simultaneous representations of multiple structures may convey as much information as several minutes of the “query-reply” loop in a conventional debugger.

In addition to discovering data values, programmers use debuggers to access the relationships and connections between different pieces of data. This is a particular area in which graphical display is much more beneficial than textual interpreters. For example, to check the structure of a linked list in a language such as C++ or Java, a programmer must print out a list item’s values and references to other list items. By carefully examining the resulting values, the programmer can determine if the list is in the desired configuration. A data structure visualization tool that could display a linked list as a series of rectangular nodes with arrows acting as the references or pointers connecting the different nodes would tremendously simplify the programmer’s task of determining relationships among the data. Data structure visualization tools also can aid the acquisition of contextual information about the state of a debugging session. For instance, a display could show a simple persistent view of the call stack and current execution line number in addition to the data pictures.

In most debuggers, a user must often make repeated explicit queries to determine this information.

For these reasons and many more, data structure visualization systems remain a relatively untapped source of value to programmers. It is quite surprising that, given these benefits, more attention and research have not been devoted to the area, and data structure visualization systems have yet to achieve widespread use and adoption.