Java™ How to Program, Sixth Edition - Part17

Few weeks back i started reading Java™ How to Program, Sixth Edition By H. M. Deitel - Deitel & Associates, Inc., P. J. Deitel - Deitel & Associates, Inc.

Nice book written By H. M. Deitel - Deitel & Associates, Inc., P. J. Deitel - Deitel & Associates, Inc.

I wanted to share few quotations found the book from the 17th chapter.

1) Dynamic data structures can grow and shrink at execution time.

2) Linked lists are collections of data items "linked up in a chain"insertions and deletions can be made anywhere in a linked list.

3) Stacks are important in compilers and operating systemsinsertions and deletions are made only at one end of a stack, its top.

4) Queues represent waiting lines; insertions are made at the tail of a queue and deletions are made from the head.

5) Binary trees facilitate high-speed searching and sorting of data, eliminating duplicate data items efficiently, representing file-system directories and compiling expressions into machine language.

6) Type-wrapper classes (e.g., Integer, Double, Boolean) enable programmers to manipulate primitive-type values as objects. Objects of these classes can be used in collections and data structures that can store only references to objectsnot primitive-type values.

7) J2SE 5.0 introduces two new conversions, the boxing conversion and the unboxing conversion. A boxing conversion converts a value of a primitive type to an object of the corresponding type-wrapper class. An unboxing conversion converts an object of a type-wrapper class to a value of the corresponding primitive type.

8) J2SE 5.0 performs boxing conversions and unboxing conversions automatically (called autoboxing and auto-unboxing).

9) A self-referential class contains a reference that refers to another object of the same class type. Self-referential objects can be linked together to form dynamic data structures.

10) The limit for dynamic memory allocation can be as large as the available physical memory in the computer or the amount of available disk space in a virtual-memory system. Often, the limits are much smaller because the computer's available memory must be shared among many users.

11) If no memory is available, an OutOfMemoryError is thrown.

12) A linked list is accessed via a reference to the first node of the list. Each subsequent node is accessed via the link-reference member stored in the previous node.

13) By convention, the link reference in the last node of a list is set to null to mark the end of the list.

14) A node can contain data of any type, including objects of other classes.

15) A linked list is appropriate when the number of data elements to be stored is unpredictable. Linked lists are dynamic, so the length of a list can increase or decrease as necessary.

16) The size of a "conventional" Java array cannot be alteredit is fixed at creation time.

17) Linked lists can be maintained in sorted order simply by inserting each new element at the proper point in the list.

18) List nodes normally are not stored contiguously in memory. Rather, they are logically contiguous.

19) A stack is a last-in, first-out (LIFO) data structure. The primary methods used to manipulate a stack are push and pop. Method push adds a new node to the top of the stack. Method pop removes a node from the top of the stack and returns the data object from the popped node.

20) Stacks have many interesting applications. When a method call is made, the called method must know how to return to its caller, so the return address is pushed onto the program execution stack. If a series of method calls occurs, the successive return values are pushed onto the stack in last-in, first-out order so that each method can return to its caller. The program execution stack contains the space created for local variables on each invocation of a method. When the method returns to its caller, the space for that method's local variables is popped off the stack, and those variables are no longer available to the program.

21) Stacks are used by compilers to evaluate arithmetic expressions and generate machine-language code to process the expressions.

22) The technique of implementing each stack method as a call to a List method is called delegationthe stack method invoked delegates the call to the appropriate List method.

23) A queue is similar to a checkout line in a supermarketthe first person in line is serviced first, and other customers enter the line only at the end and wait to be serviced.

24) Queue nodes are removed only from the head of the queue and are inserted only at the tail. For this reason, a queue is referred to as a first-in, first-out (FIFO) data structure.

25) The insert and remove operations for a queue are known as enqueue and dequeue.

26) Queues have many uses in computer systems. Most computers have only a single processor, so only one application at a time can be serviced. Entries for the other applications are placed in a queue. The entry at the front of the queue is the next to receive service. Each entry gradually advances to the front of the queue as applications receive service.

27) A tree is a nonlinear, two-dimensional data structure. Tree nodes contain two or more links.

28) A binary tree is a tree whose nodes all contain two links. The root node is the first node in a tree.

29) Each link in the root node refers to a child. The left child is the first node in the left subtree, and the right child is the first node in the right subtree.

30) The children of a node are called siblings. A node with no children is called a leaf node.

31) A binary search tree (with no duplicate node values) has the characteristic that the values in any left subtree are less than the value in the subtree's parent node, and the values in any right subtree are greater than the value in the subtree's parent node. A node can be inserted only as a leaf node in a binary search tree.

32) An inorder traversal of a binary search tree processes the node values in ascending order.

33) In a preorder traversal, the value in each node is processed as the node is visited. Then the values in the left subtree are processed, and then the values in the right subtree.

34) In a postorder traversal, the value in each node is processed after the values of its children.

35) The binary search tree facilitates duplicate elimination. As the tree is created, attempts to insert a duplicate value are recognized, because a duplicate follows the same "go left" or "go right" decisions on each comparison as the original value did. Thus, the duplicate eventually is compared with a node containing the same value. The duplicate value can be discarded at this point.

36) Searching a binary tree for a value that matches a key value is also fast, especially for tightly packed trees. In a tightly packed tree, each level contains about twice as many elements as the previous one. So a tightly packed binary search tree with n elements has log2n levels, and thus at most log2n comparisons would have to be made either to find a match or to determine that no match exists. Searching a (tightly packed) 1000-element binary search tree requires at most 10 comparisons, because 210 > 1000. Searching a (tightly packed) 1,000,000-element binary search tree requires at most 20 comparisons, because 220 > 1,000,000.

About the Authors

Dr. Harvey M. Deitel, Chairman and Chief Strategy Officer of Deitel & Associates, Inc., has 43 years experience in the computing field, including extensive industry and academic experience. Dr. Deitel earned B.S. and M.S. degrees from the Massachusetts Institute of Technology and a Ph.D. from Boston University. He worked on the pioneering virtual-memory operating-systems projects at IBM and MIT that developed techniques now widely implemented in systems such as UNIX, Linux and Windows XP. He has 20 years of college teaching experience, including earning tenure and serving as the Chairman of the Computer Science Department at Boston College before founding Deitel & Associates, Inc., with his son, Paul J. Deitel. He and Paul are the co-authors of several dozen books and multimedia packages and they are writing many more. With translations published in Japanese, German, Russian, Spanish, Traditional Chinese, Simplified Chinese, Korean, French, Polish, Italian, Portuguese, Greek, Urdu and Turkish, the Deitels' texts have earned international recognition. Dr. Deitel has delivered hundreds of professional seminars to major corporations, academic institutions, government organizations and the military.

Paul J. Deitel, CEO and Chief Technical Officer of Deitel & Associates, Inc., is a graduate of the MIT's Sloan School of Management, where he studied Information Technology. Through Deitel & Associates, Inc., he has delivered Java, C, C++, Internet and World Wide Web courses to industry clients, including IBM, Sun Microsystems, Dell, Lucent Technologies, Fidelity, NASA at the Kennedy Space Center, the National Severe Storm Laboratory, Compaq, White Sands Missile Range, Rogue Wave Software, Boeing, Stratus, Cambridge Technology Partners, Open Environment Corporation, One Wave, Hyperion Software, Adra Systems, Entergy, CableData Systems and many other organizations. Paul is one of the most experienced Java corporate trainers having taught about 100 professional Java training courses. He has also lectured on C++ and Java for the Boston Chapter of the Association for Computing Machinery. He and his father, Dr. Harvey M. Deitel, are the world's best-selling Computer Science textbook authors.