Previous Section
 < Free Open Study > 
Next Section


Summary

We have seen how stacks, queues, unsorted lists, and sorted lists may be represented in an array-based or a linked representation. The specification for each ADT didn't mention any of these design issues, so we were free to implement them in any way we chose. Nothing in these ADTs' specifications said that the structures should be array-based or linked, or that the elements were stored in statically or dynamically allocated storage.

We could specify a number of other operations for a List ADT. Some operations, such as finding the preceding node in a list, are easy to implement for an array-based list but would be difficult to implement using a list that is linked in one direction (like the lists described in this chapter). This operation would be simpler if the list had links going both forward and backward. We can think of many variations for representing a linked list to simplify the kinds of operations that are specified for the list: doubly linked lists, circular ists, lists that are accessed from both the beginning and the end. We look at some of these alternative implementation structures in Chapter 6.

The idea of linking the elements in a data structure is not specific to stacks, queues, and lists. We use this powerful tool to implement many other data structures in this book.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)