Topic 12SS CADTS, Data Structures, Java Collections and Generic Data Structures"Get your data structures correct fi t d th t f th illfirst, and the rest of the program will write itself."- David JonesCS 307 Fundamentals of Computer ScienceADTS and Generic Data Structures1Abstract Data Types88Abstract Data Types (aka ADTs) are descriptions of how a data type will work without implementation details8Example, Stack at NIST DADS– http://xw2k.nist.gov/dads/HTML/stack.html8Description can be a formal, mathematicalDescription can be a formal, mathematical description8Java interfaces are a form of ADTs8Java interfaces are a form of ADTs– some implementation details start to creep inCS 307 Fundamentals of Computer ScienceADTS and Generic Data Structures2Data Structures88A Data Structure is:– an implementation of an abstract data type and– "An organization of information, usually in computer memory", for better algorithm ffi i "efficiency."aListList ObjectaListsizemyElements5yACEBA0 1 2 3 4 5 6 7 8 9 10CS 307 Fundamentals of Computer Science ADTs and Data Structures3A C E B AData Structure Concepts8DS i8Data Structures are containers:– they hold other dataarra s are a data str ct re–arrays are a data structure– ... so are lists8Other types of data structures:8Other types of data structures:– stack, queue, tree, binary search tree, hash table,y,,dictionary or map, set, and on and on– www.nist.gov/dads/–en.wikipedia.org/wiki/List_of_data_structures8Different types of data structures are optimized for certain types of operationsCS 307 Fundamentals of Computer Science ADTs and Data Structures4certain types of operationsCore Operations88Data Structures will have 3 core operations– a way to add things– a way to remove things– a way to access things8Details of these operations depend on the data structure– Example: List, add at the end, access by location, remove by locationy8More operations added depending on what data structure is designed to doCS 307 Fundamentals of Computer Science ADTs and Data Structures5data structure is designed to doADTs and Data Structures in Programming LanguagesProgramming Languages8Modern programming languages usually h lib f d t t thave a library of data structures– Java collections framework– C++ standard template library– .Net framework (small portion of VERY large library)– Python lists and tuples– Lisp listsCS 307 Fundamentals of Computer Science ADTs and Data Structures6Data Structures in Java88Part of the Java Standard Library is the Collections Framework– In class we will create our own data structures and discuss the data structures that exist in Java8A library of data structures8Built on two interfaces– Collection–IteratorIterator8http://java.sun.com/j2se/1.5.0/docs/guide/collections/index htmlCS 307 Fundamentals of Computer Science ADTs and Data Structures7ections/index.htmlThe Java Collection interface88A generic collection8Can hold any object data type8Which type a particular collection will hold is specified when declaring an instance of a spec ed e dec a g a sta ce o aclass that implements the Collection interface8Helps guaranteetype safetyat compile timeHelps guarantee type safetyat compile timeCS 307 Fundamentals of Computer Science ADTs and Data Structures8Methods in the Collection interfacepublic interface Collection<E>public interface Collection<E>{ public boolean add(E o)public boolean addAll(Collection<? extends E> c)public voidclear()public void clear() public boolean contains(Object o) public boolean containsAll(Collection<?> c) public booleanequals(Objecto)public boolean equals(Objecto)public int hashCode() public boolean isEmpty() public Iterator<E>iterator()public Iterator<E> iterator()public boolean remove(Object o) public boolean removeAll(Collection<?> c) public boolean retainAll(Collection<?>c)pub c boo eaeta(Co ect oc)public int size() public Object[] toArray()public <T> T[] toArray(T[]a) CS 307 Fundamentals of Computer Science ADTs and Data Structures9p[]y([])}The Java ArrayList Class88Implements the List interface and uses an array as its internal storage container8It is a list, not an array8The array that actual stores the elements of e a ay t at actua sto es t e e e e ts othe list is hidden, not visible outside of the ArrayList classay s c ass8all actions on ArrayList objects are via the methodsmethods8ArrayLists are generic. Th h ld bj t f t !CS 307 Fundamentals of Computer Science ADTs and Data Structures10–They can hold objects of any type!ArrayList's (Partial) Class DiagramClass DiagramIterableObjectCollectionAbstractCollectionListAbstractListArrayListCS 307 Fundamentals of Computer Science ADTs and Data Structures11Back to our Array Based List 88Started with a list of ints8Don't want to have to write a new list class for every data type we want to store in lists8Moved to an array of Objects to store the yjelements of the list// from array based listyprivate Object[] myCon;CS 307 Fundamentals of Computer ScienceADTS and Generic Data Structures12Using Object88In Java, all classes inherit from exactly one other class except Object which is at the top of the class hierarchy8Object variables can point at objects of their declared type and any descendants–polymorphismpy p8Thus, if the internal storage container is of type Object it can hold anythingtype Object it can hold anything– primitives handled by wrapping them in objects.int –Integer, char - CharacterCS 307 Fundamentals of Computer ScienceADTS and Generic Data Structures13g,Difficulties with Object88Creating generic containers using the Object data type and polymorphism is relatively straight forward8Using these generic containers leads to some difficulties–Castingg– Type checking8Code examples on the following slidesCode examples on the following slidesCS 307 Fundamentals of Computer ScienceADTS and Generic Data Structures14Attendance Question 188What is output by the following code?ArrayList list = new ArrayList();String name = "Olivia";list.add(name);System out print(list get(0)charAt(2) );System.out.print( list.get(0).charAt(2) );A. iBB. OC. lD. No output due to syntax error.E No output due to runtime errorE. No output due to runtime error.CS 307 Fundamentals of Computer ScienceADTS and Generic Data Structures15Code Example - Casting88Assume a list classArrayList li = new ArrayList();li.add(“Hi”);System.out.println( li.get(0).charAt(0) );// previous line has syntax error// previous line
View Full Document
Unlocking...