Kĩ thuật lập trình - Data structures

17Data Structures 1 Much that I bound, I could not free;Much that I freed returned to me. Lee Wilson Dodd‘Will you walk a little faster?’ said a whiting to a snail,‘There’s a porpoise close behind us, and he’s treading on my tail.’Lewis CarrollThere is always room at the top. Daniel WebsterPush on—keep moving. Thomas MortonI’ll turn over a new leaf. Miguel de Cervantes 2OBJECTIVESIn this chapter you will learn:To form linked data structures using references, self-referential classes and recursion.The type-wrapper classes that enable programs to process primitive data values as objects.To use autoboxing to convert a primitive value to an object of the corresponding type-wrapper class.To use auto-unboxing to convert an object of a type-wrapper class to a primitive value.To create and manipulate dynamic data structures, such as linked lists, queues, stacks and binary trees.Various important applications of linked data structures.How to create reusable data structures with classes, inheritance and composition.317.1   Introduction 17.2   Type-Wrapper Classes for Primitive Types 17.3   Autoboxing and Auto-Unboxing 17.4   Self-Referential Classes 17.5   Dynamic Memory Allocation 17.6   Linked Lists 17.7   Stacks 17.8   Queues 17.9   Trees 17.10   Wrap-Up 417.1  Introduction Dynamic data structuresLinear data structuresLinked listsStacksQueuesBinary trees517.2  Type-Wrapper Classes for Primitive Types Type-wrapper classesIn package java.langEnable programmers to manipulate primitive-type values as objectsBoolean, Byte, Character, Double, Float, Integer, Long and Short617.3  Autoboxing and Auto-Unboxing Boxing conversionConverts a value of a primitive type to an object of the corresponding type-wrapper classUnboxing conversionConverts an object of a type-wrapper class to a value of the corresponding primitive typeJava automatically performs these conversions (starting with Java SE 5)Called autoboxing and auto-unboxing717.4  Self-Referential Classes Self-referential classContains an instance variable that refers to another object of the same class typeThat instance variable is called a linkA null reference indicates that the link does not refer to another objectIllustrated by a backslash in diagrams8Fig. 17.1 | Self-referential-class objects linked together. 917.5  Dynamic Memory Allocation Dynamic memory allocationThe ability for a program to obtain more memory space at execution time to hold new nodes and to release space no longer neededJava performs automatic garbage collection of objects that are no longer referenced in a programNode nodeToAdd = new Node( 10 );Allocates the memory to store a Node object and returns a reference to the object, which is assigned to nodeToAddThrows an OutOfMemoryError if insufficient memory is available1017.6  Linked Lists Linked listLinear collection of nodesSelf-referential-class objects connected by reference linksCan contain data of any typeA program typically accesses a linked list via a reference to the first node in the listA program accesses each subsequent node via the link reference stored in the previous nodeAre dynamicThe length of a list can increase or decrease as necessaryBecome full only when the system has insufficient memory to satisfy dynamic storage allocation requests11Performance Tip 17.1An array can be declared to contain more elements than the number of items expected, but this wastes memory. Linked lists provide better memory utilization in these situations. Linked lists allow the program to adapt to storage needs at runtime. 12Performance Tip 17.2 Insertion into a linked list is fast—only two references have to be modified (after locating the insertion point). All existing node objects remain at their current locations in memory. 13Insertion and deletion in a sorted array can be time consuming—all the elements following the inserted or deleted element must be shifted appropriately. Performance Tip 17.3 1417.6  Linked Lists (Cont.)Singly linked listEach node contains one reference to the next node in the listDoubly linked listEach node contains a reference to the next node in the list and a reference to the previous node in the listjava.util’s LinkedList class is a doubly linked list implementation15Performance Tip 17.4 Normally, the elements of an array are contiguous in memory. This allows immediate access to any array element, because its address can be calculated directly as its offset from the beginning of the array. Linked lists do not afford such immediate access to their elements—an element can be accessed only by traversing the list from the front (or from the back in a doubly linked list). 16Fig. 17.2 | Linked list graphical representation. 17Field data can refer to any objectStores a reference to the next ListNode object in the linked list18References to the first and last ListNodes in a ListCall one-argument constructor19Initialize both references to null2021Predicate method that determines whether the list is empty22Display the list’s contentsDisplay a message indicating that the list is emptyOutput a string representation of current.dataMove to the next node in the list2324Insert objects at the beginning of the list using method insertAtFrontInsert objects at the end of the list using method insertAtBackJVM autoboxes each literal value in an Integer object25Deletes objects from the front of the list using method removeFromFrontDelete objects from the end of the list using method removeFromBackCall List method print to display the current list contentsException handler for EmptyListException262717.6  Linked Lists (Cont.)Method insertAtFront’s stepsCall isEmpty to determine whether the list is emptyIf the list is empty, assign firstNode and lastNode to the new ListNode that was initialized with insertItemThe ListNode constructor call sets data to refer to the insertItem passed as an argument and sets reference nextNode to nullIf the list is not empty, set firstNode to a new ListNode object and initialize that object with insertItem and firstNodeThe ListNode constructor call sets data to refer to the insertItem passed as an argument and sets reference nextNode to the ListNode passed as argument, which previously was the first node28Fig. 17.6 | Graphical representation of operation insertAtFront.2917.6  Linked Lists (Cont.)Method insertAtBack’s stepsCall isEmpty to determine whether the list is emptyIf the list is empty, assign firstNode and lastNode to the new ListNode that was initialized with insertItemThe ListNode constructor call sets data to refer to the insertItem passed as an argument and sets reference nextNode to nullIf the list is not empty, assign to lastNode and lastNode.nextNode the reference to the new ListNode that was initialized with insertItemThe ListNode constructor sets data to refer to the insertItem passed as an argument and sets reference nextNode to null30Fig. 17.7 | Graphical representation of operation insertAtBack.3117.6  Linked Lists (Cont.)Method removeFromFront’s stepsThrow an EmptyListException if the list is emptyAssign firstNode.data to reference removedItemIf firstNode and lastNode refer to the same object, set firstNode and lastNode to nullIf the list has more than one node, assign the value of firstNode.nextNode to firstNodeReturn the removedItem reference32Fig. 17.8 | Graphical representation of operation removeFromFront. 3317.6  Linked Lists (Cont.)Method removeFromBack’s stepsThrows an EmptyListException if the list is emptyAssign lastNode.data to removedItemIf the firstNode and lastNode refer to the same object, set firstNode and lastNode to nullIf the list has more than one node, create the ListNode reference current and assign it firstNode“Walk the list” with current until it references the node before the last nodeThe while loop assigns current.nextNode to current as long as current.nextNode is not lastNode3417.6  Linked Lists (Cont.)Assign current to lastNodeSet current.nextNode to nullReturn the removedItem reference35Fig. 17.9 | Graphical representation of operation removeFromBack. 3617.7  Stacks StacksLast-in, first-out (LIFO) data structureMethod push adds a new node to the top of the stackMethod pop removes a node from the top of the stack and returns the data from the popped nodeProgram execution stackHolds the return addresses of calling methodsAlso contains the local variables for called methodsUsed by the compiler to evaluate arithmetic expressions3717.7  Stacks (Cont.)Stack class that inherits from ListStack methods push, pop, isEmpty and print are performed by inherited methods insertAtFront, removeFromFront, isEmpty and printpush calls insertAtFrontpop calls removeFromFrontisEmpty and print can be called as inheritedOther List methods are also inheritedIncluding methods that should not be in the stack class’s public interface38Class StackInheritance extends class ListMethod push calls inherited method insertAtFrontMethod pop calls inherited method removeFromFront39Create a StackInheritenace objectPush integers onto the stack40Pop the objects from the stack in an infinite while loopImplicitly call inherited method printDisplay the exception’s stack trace414217.7  Stacks (Cont.)Stack class that contains a reference to a ListEnables us to hide the List methods that should not be in our stack’s public interfaceEach stack method invoked delegates the call to the appropriate List methodmethod push delegates to List method insertAtFrontmethod pop delegates to List method removeFromFrontmethod isEmpty delegates to List method isEmptymethod print delegates to List method print43OutlineStackComposition.java(1 of 2)private List referencepush method delegates call to List method insertAtFront44Method pop delegates call to List method removeFromFrontMethod isEmpty delegates call to List method isEmptyMethod print delegates call to List method print4517.8  Queues QueueSimilar to a checkout line in a supermarketFirst-in, first-out (FIFO) data structureEnqueue inserts nodes at the tail (or end)Dequeue removes nodes from the head (or front)Used to support print spoolingA spooler program manages the queue of printing jobs 4617.8  Queues (Cont.)Queue class that contains a reference to a ListMethod enqueue calls List method insertAtBackMethod dequeue calls List method removeFromFrontMethod isEmpty calls List method isEmptyMethod print calls List method print47An object of class ListMethod enqueue calls List method insertAtBack48Method dequeue calls List method removeFromFrontMethod isEmpty calls List method isEmptyMethod print calls List method print49Create a Queue objectEnqueue four integers50Dequeue the objects in first-in, first-out orderDisplay the exception’s stack trace515217.9  Trees TreesThe root node is the first node in a treeEach link refers to a childLeft child is the root of the left subtreeRight child is the root of the right subtreeSiblings are the children of a specific nodeA leaf node has no children5317.9  Trees (Cont.)Binary search treesValues in the left subtree are less than the value in that subtree’s parent node and values in the right subtree are greater than the value in that subtree’s parent nodeTraversing a treeInorder - traverse left subtree, then process root, then traverse right subtreePreorder - process root, then traverse left subtree, then traverse right subtreePostorder - traverse left subtree, then traverse right subtree, then process root54Fig. 17.15 | Binary tree graphical representation. 55Fig. 17.16 | Binary search tree containing 12 values. 5657OutlineTree.java(2 of 5)Allocate a new TreeNode and assign it to reference leftNodeAllocate a new TreeNode and assign it to reference rightNode58TreeNode reference to the root node of the treeAllocate a new TreeNode and assign it to reference rootCall TreeNode method insertCall Tree helper method preorderHelper to begin traversal 59Call Tree helper method inorderHelper to begin traversal 60Call Tree helper method postorderHelper to begin traversal 61Create a Tree objectInsert values into tree626317.9  Trees (Cont.)Inorder traversal stepsReturn immediately if the reference parameter is nullTraverse the left subtree with a call to inorderHelperProcess the value in the nodeTraverse the right subtree with a call to inorderHelperBinary tree sortThe inorder traversal of a binary search tree prints the node values in ascending order6417.9  Trees (Cont.)Preorder traversal stepsReturn immediately if the reference parameter is nullProcess the value in the nodeTraverse the left subtree with a call to preorderHelperTraverse the right subtree with a call to preorderHelper6517.9  Trees (Cont.)Postorder traversal stepsReturn immediately if the reference parameter is nullTraverse the left subtree with a call to postorderHelperTraverse the right subtree with a call to postorderHelperProcess the value in the node6617.9  Trees (Cont.)Duplicate eliminationBecause duplicate values follow the same “go left” or “go right” decisions, the insertion operation eventually compares the duplicate with a same-valued nodeThe duplicate can then be ignoredTightly packed (or balanced) treesEach level contains about twice as many elements as the previous levelFinding a match or determining that no match exists among n elements requires at most log2n comparisonsLevel-order traversal of a binary treeVisits the nodes of the tree row by row, starting at the root node level67Fig. 17.19 | Binary search tree with seven values. 68