1150 Data Structures and (Web site builder) Collections Chapter 23 Performance
1150 Data Structures and Collections Chapter 23 Performance Tip 23.5 Insertion and deletion in a sorted array can be time consuming all the elements following the inserted or deleted element must be shifted appropriately. The program consists of four classes ListNode (Fig. 23.4, lines 9 52), List (Fig. 23.4, lines 55 193), EmptyListException (Fig. 23.4, lines 196 203) and class ListTest (Fig. 23.5). The classes in Fig. 23.4 create a linked-list library (defined in namespace LinkedListLibrary) that can be reused throughout this chapter. Encapsulated in each List object is a linked list of ListNode objects. Class List- Node (Fig. 23.4, lines 9 52) consists of two member variables data and next. Member data can refer to any object. Member next stores a reference to the next List- Nodeobject in the linked list. A List accesses the ListNodemember variables via the properties Data (lines 44 50) and Next (lines 30 41), respectively. Class List contains private members firstNode (a reference to the first ListNode in a List) and lastNode (a reference to the last ListNode in a List). The constructors (lines 62 66 and 69 71) initialize both references to null. InsertAt- Front (lines 76 87), InsertAtBack (lines 92 104), RemoveFromFront (lines 107 125) and RemoveFromBack (lines 128 156) are the primary methods of class List. Each method uses a lock block to ensure that List objects are multithread safe when used in a multithreaded program. If one thread is modifying the contents of a List object, no other thread can modify the same List object at the same time. Method IsEmpty (lines 159 165) is a predicate method that determines whether the list is empty (i.e., the reference to the first node of the list is null). Predicate methods typically test a condition and do not modify the object on which they are called. If the list is empty, method IsEmpty returns true; otherwise, it returns false. Method Print (lines 168 191) displays the list s contents. Both IsEmpty and Print also use lock blocks so that the state of the list does not change while those methods are performing their tasks. Class EmptyListException (lines 196 203) defines an exception class to handle illegal operations on an empty List. Class ListTest (Fig. 23.5) uses the linked-list library to create and manipulate a linked list. Line 14 creates a new instance of type List named list. Lines 17 20 create data to add to the list. Lines 23 30 use List insertion methods to insert these objects and use List method Print to output the contents of list after each insertion. The code inside the try block (lines 36 53) removes objects via List deletion methods, outputs the object removed and outputs list after every deletion. If there is an attempt to remove an object from an empty list, this try block catches the EmptyListException. Note that class ListTest uses namespace LinkedListLibrary (Fig. 23.4); thus, the solution for class ListTest must have a reference to the LinkedListLibraryclass library. Over the next several pages, we discuss each of the methods of class List in detail. Method InsertAtFront (Fig. 23.4, lines 76 87) places a new node at the front of the list. The method consists of three steps (illustrated in Fig. 23.6): 1. Call IsEmpty to determine whether the list is empty (line 80). 2. If the list is empty, set both firstNode and lastNode to refer to a new ListNode initialized with insertItem (lines 81 82). The ListNode constructor at lines 16 19 (Fig. 23.4) calls the ListNode constructor at lines 23 27
Note: In case you are looking for affordable and reliable webhost to host and run your business application check Vision ftp web hosting services