Animation of Java Linked Lists Herbert L. Dershem and Ryan L. McFall Department of Computer Science Hope College Holland, MI 49423 {dershem mcfall}@cs.hope.edu} Ngozi Uti Northern Kentucky University Highland Heights, KY 41099 [email protected] Abstract Linked lists are an important component of the computer science curriculum. JVALL is a software package that provides an animation of linked list operations that is fully compatible with the Java LinkedList class. The animations are driven by a client program that can be either an applet or standalone application. It provides an effective way for students to learn, experiment with, and debug linked list based classes. 1 Introduction One of the most popular models for the implementation of data structures is the linked list. This model and its associated operations are an important topic in the traditional data structures course. The linked list operations are virtually always introduced through a visualization, both in textbooks and on chalkboards. This paper describes a useful tool that has been developed that enables linked list structures to be visualized through animations of the standard operations. The presentation of algorithm visualizations on the web has many advantages, particularly in distance education settings. This has been the focus of much recent work. [1] [3] [4] [5] Animations that can be generated and controlled by students have also been shown to be effective in instruction. [7] Another technique that has proven to be useful is the visualization of pre-existing code to enhance student understanding. [2] The present work is intended to provide an effective tool to support student learning and understanding of linked list operations as well as assist students in understanding applications that use linked lists. It is fully compatible with the Java LinkedList class and can be used by client programs that axe either Java standalone applications or applets. A general-purpose client program is included that provides an effective user interface for the visualization of all linked list operations under user control. Permission to make digital or hard copies of all or part of this work for pe~onal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGCSE'02, February 27- March 3, 2002, Covington, Kentucky, USA. Copyright 2002 ACM 1-58113.-473-8/02/0002...$5.00. 2 Design Objectives The objective of this project is to produce a linked list visualization tool with the following capabilities: User-controlled animation of basic linked list algorithms Operations are animated at a speed that is controlled by the user and allows the user to observe the construction and modification of nodes in the list. Likewise the user determines the implementation model for the linked list, the context where the operations are called, and the colors of the components of the animation. Animation of pre-existing code that uses linked lists The animation class provided is an extension of the Java LinkedList class. Therefore, any program that uses the Java class is easily modified to enable its linked list operations to be animated. Support for multiple linked list implementation models The present version supports both linear and circular singly-linked lists. Future versions will add support for doubly linked lists and header node lists as well. Animations within both Java applets and applications The tool is easily applied in both of these environments via a parameter passed when the animated linked list object is constructed. 3 Design and Features The package that provides the linked list animation is called JVALL (Java Visual Automated Linked List). Important features of this tool are described below. Visualization The JVALL animation '~rindow is shown in Figure I. The window is divided into three areas. The top area contains controls that allow the user to modify the colors, speed, and implementation model of the animation. The middle area is the animation display that contains the nodes in the list. List nodes contain data and reference components. The data component displays the String representation of the node 53data object as given by the application of the Java toString method. The reference component contains the source of a pointer from the node to the next node in the linked structure. The bottom area contains text reporting the animation status and buttons to undo and redo operations. Figure 3 is a snapshot taken in the midst of an insert animation. The inserted node ("Frank O") is moved into place after new references have been assigned. The discarded reference between the previous and succeeding nodes remains beneath the inserted node and is marked as such while the inserted node is being moved into place. This reference disappears upon completion of the animation. Similar animations exist for all Java LinkedList class operations. Due to the limitations on screen sizes, most animations restrict their users to input only digits or a limited number of characters for display. Instead of limiting user inputs, and in order to be consistent with the flexible nature of the linked list data structure, the "click, hold to expand" node was used. JVALL's node is capable of displaying lengthy values by displaying an abbreviated text with dots at the end to indicate that it contains more characters than can be displayed in the basic code rectangle. To view the entire text, the user can click and hold on a node with a lengthy value. • "" """ '- ....... "' ~' .,'"~'~, ~~".~ ~G:.-,'~ '.''g~g,-*~.-e~ ~'~' ~' .?t...h~ '.~.~Ei~..;."t..i~ ~ ~'~'..-;"..~.'. ~"... ~ .~r...--~%~?~,.~.:.. : .:......... ?.!! ~ ~. :i :.. ..-.~ .. .~.-~. ..-: i...".'~ ~ ~; ~ ..-.....! ..i. ...~._..-... !:... 2i &.:..i~i.--:, ,. ',:~...>_.-... ~