05Data Structures----Public and Private

1 . Public and Private public class Date { private int day; private int month; private void setMonth(int m) month = m; } public Date(int month, int day) { Implementation includes error-checking }   public class TamperMonkey { public void tamper() { Date d = new Date(9, 25); d.day = 75; // Will it work? d.setMonth(20); // Will it work         }                                                                     Will TamperMonkey compile? 

2 .Abstract Data Type The Interface of a class = A set of public methods + Descriptions of the methods' behaviors (but not how they are implemented). An Abstract Data Type (ADT) is a well-defined Interface without any details about its implementation. Treat this as a user-defined data-type. An ADT as a mathematical model of the data objects that make up a data type as well as functions that operate on these objects. Some examples are: • List • Stack • Queue • Tree • Heap 

3 .The List ADT Here is a sample list: Bread cheese, tea, coffee, milk, honey, pizza, Java defines a general interface java.util.List that includes the following index-based methods (since that provides more general support for addition or deletion of items) and many more Size () return the SIZE isEmpty() returns TRUE or FALSE get(i) returns element with index i Error occurs when index is outside the range set(i, e) updates element i to e Error occurs when index is outside the range add (i, e) inserts item e after element with index i Error occurs when index is outside the range remove (i) deletes the ith element Error occurs when index is outside the range 

4 .Stack ADT What is a stack? What are the invariants? 

5 .From abstract to concrete One way to implement the list ADT is to use an array. ArrayList creates the illusion of an unbounded array, by repeatedly copying fixed size arrays into a larger space when new elements are inserted. Public class ArrayList <E> implements list <E> There can be other implementations of the list ADT. Each ADT should have one or more invariants that are true, regardless of the implementation. What is the invariant of a list ADT? “There is always a tail “ (so no circular structure) 

6 .The Singly Linked List 

7 .Inserting at the Head Removing the Head Removing the tail : why is it slow? 

8 .Inserting at the tail Doubly Linked List Circular Linked Lists 

9 .Skip List Helps manage a list efficiently         Figures taken from Wikipedia