Chapter 4Abstract Data TypesSlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Specifying ADTsThe ADT ListSlide 12Slide 13The ADT Sorted ListDesigning an ADTAxioms (Optional)Slide 17Implementing ADTsSlide 19Slide 20Java Classes RevisitedSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Java InterfacesSlide 30Java ExceptionsSlide 32Slide 33Slide 34Slide 35Slide 36An Array-Based Implementation of the ADT ListSlide 38SummarySlide 40© 2006 Pearson Addison-Wesley. All rights reserved 4-1 Chapter 4Data Abstraction: The Walls CS102 Sections 51 and 52Marc Smith and Jim Ten EyckSpring 2008© 2006 Pearson Addison-Wesley. All rights reserved 4-2Abstract Data Types•Modularity–Keeps the complexity of a large program manageable by systematically controlling the interaction of its components–Isolates errors–Eliminates redundancies–A modular program is•Easier to write•Easier to read•Easier to modify© 2006 Pearson Addison-Wesley. All rights reserved 4-3Abstract Data Types•Procedural abstraction–Separates the purpose and use of a module from its implementation–A module’s specifications should•Detail how the module behaves•Identify details that can be hidden within the module•Information hiding–Hides certain implementation details within a module–Makes these details inaccessible from outside the module© 2006 Pearson Addison-Wesley. All rights reserved 4-4Abstract Data TypesFigure 4-1Figure 4-1Isolated tasks: the implementation of task T does not affect task Q© 2006 Pearson Addison-Wesley. All rights reserved 4-5Abstract Data Types•The isolation of modules is not total–Methods’ specifications, or contracts, govern how they interact with each otherFigure 4-2Figure 4-2A slit in the wall© 2006 Pearson Addison-Wesley. All rights reserved 4-6Abstract Data Types•Typical operations on data–Add data to a data collection–Remove data from a data collection–Ask questions about the data in a data collection•Data abstraction–Asks you to think what you can do to a collection of data independently of how you do it–Allows you to develop each data structure in relative isolation from the rest of the solution–A natural extension of procedural abstraction© 2006 Pearson Addison-Wesley. All rights reserved 4-7Abstract Data Types•Abstract data type (ADT)–An ADT is composed of•A collection of data•A set of operations on that data–Specifications of an ADT indicate•What the ADT operations do, not how to implement them–Implementation of an ADT•Includes choosing a particular data structure© 2006 Pearson Addison-Wesley. All rights reserved 4-8Abstract Data Types•Data structure–A construct that is defined within a programming language to store a collection of data–Example: arrays•ADTs and data structures are not the same•Data abstraction–Results in a wall of ADT operations between data structures and the program that accesses the data within these data structures© 2006 Pearson Addison-Wesley. All rights reserved 4-9Abstract Data TypesFigure 4-4Figure 4-4A wall of ADT operations isolates a data structure from the program that uses it© 2006 Pearson Addison-Wesley. All rights reserved 4-10Specifying ADTs•In a list–Except for the first and last items, each item has•A unique predecessor•A unique successor–Head or front•Does not have a predecessor–Tail or end•Does not have a successorFigure 4-5Figure 4-5list A grocery© 2006 Pearson Addison-Wesley. All rights reserved 4-11The ADT List•ADT List operations–Create an empty list–Determine whether a list is empty–Determine the number of items in a list–Add an item at a given position in the list–Remove the item at a given position in the list–Remove all the items from the list–Retrieve (get) the item at a given position in the list•Items are referenced by their position within the list© 2006 Pearson Addison-Wesley. All rights reserved 4-12The ADT List•Specifications of the ADT operations–Define the contract for the ADT list–Do not specify how to store the list or how to perform the operations•ADT operations can be used in an application without the knowledge of how the operations will be implemented© 2006 Pearson Addison-Wesley. All rights reserved 4-13The ADT ListFigure 4-7Figure 4-7The wall between displayList and the implementation of the ADT list© 2006 Pearson Addison-Wesley. All rights reserved 4-14The ADT Sorted List•The ADT sorted list–Maintains items in sorted order–Inserts and deletes items by their values, not their positions© 2006 Pearson Addison-Wesley. All rights reserved 4-15Designing an ADT•The design of an ADT should evolve naturally during the problem-solving process•Questions to ask when designing an ADT–What data does a problem require?–What operations does a problem require?© 2006 Pearson Addison-Wesley. All rights reserved 4-16Axioms (Optional)•For complex abstract data types, the behavior of the operations must be specified using axioms–Axiom: A mathematical rule© 2006 Pearson Addison-Wesley. All rights reserved 4-17Axioms (Optional)•Axioms for the ADT List–(aList.createList()).size() = 0–(aList.add(i, x)).size() = aList.size() + 1–(aList.remove(i)).size() = aList.size() – 1–(aList.createList()).isEmpty() = true–(aList.add(i, item)).isEmpty() = false–(aList.createList()).remove(i) = error–(aList.add(i, x)).remove(i) = aList–(aList.createList()).get(i) = error–(aList.add(i, x)).get(i) = x–aList.get(i) = (aList.add(i, x).get(i+1)–aList.get(i+1) = (aList.remove(i)).get(i)© 2006 Pearson Addison-Wesley. All rights reserved 4-18Implementing ADTs•Choosing the data structure to represent the ADT’s data is a part of implementation–Choice of a data structure depends on•Details of the ADT’s operations•Context in which the operations will be used•Implementation details should be hidden behind a wall of ADT operations–A program would only be able to access the data structure using the ADT operations© 2006 Pearson Addison-Wesley. All rights reserved 4-19Implementing ADTsFigure 4-8Figure 4-8ADT operations provide access to a data structure© 2006 Pearson Addison-Wesley. All rights reserved 4-20Implementing ADTsFigure 4-9Figure 4-9Violating the wall of ADT operations© 2006 Pearson Addison-Wesley. All rights reserved 4-21Java Classes Revisited•Object-oriented programming (OOP) views a program as a collection of objects•Encapsulation–A principle of OOP–Can be used to