< Free Open Study > |
This chapter is a collection of theoretical material and implementation techniques. The idea of linking the elements in a list has been extended to include lists with header and trailer nodes, circular lists, and doubly linked lists. The idea of linking the elements is a possibility to consider in the design of many types of data structures. In addition to using dynamically allocated nodes to implement a linked structure, we looked at a technique for implementing linked structures in an array of records. In this technique, the links are not pointers into the free store but rather indexes into the array of records. Systems software makes extensive use of this type of linking.
While a linked list can be used to implement almost any list application, its real strength emerges in applications that largely process the list elements in order. This is not to say that we cannot do "random access" operations on a linked list. Our specifications include operations that logically access elements in random order-for instance, the member functions RetrieveItem and DeleteItem manipulate an arbitrary element in the list. Nevertheless, at the implementation level the only way to find an element is to search the list, beginning at the first element and continuing sequentially by examining element after element. From Chapter 3, we know that a linear search is O(N), because the amount of work required is directly proportional to the number of elements in the list. A particular element in a sequentially sorted list in an array, in contrast, can be found with a binary search, decreasing the search algorithm to O(log_{2}N). For a large list, the O(N) sequential search can prove quite time-consuming. One linked structure does support O(log_{2}N) searches: the binary search tree. We discuss this data structure in detail in Chapter 8.
We revisited polymorphism in this chapter by examining an example of how to use the C++ virtual function construct to implement dynamic binding. We also examined the concept of deep versus shallow copying and assignment operator overloading.
The Case Study designed a Large Integer ADT. The number of digits is bounded only by the size of memory. Several relational and arithmetic operators were overloaded to work with objects of this type.
< Free Open Study > |
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) |