DOC PREVIEW
USF CS 245 - Abstract Data Types and Lists

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS245-2014S-0 5 Abstract Data Types and Lists 105-0: Abstract Data Types• Recall that an Abstract Data Type is a definition of a type based on the operations that can be perform ed on it.• An ADT is an interface• Data in an ADT cannot be manipu la ted directly – only through operations d efined in the interface05-1: List ADT• A List is an ordered collection of elements• Each eleme nt in the list has a position• Element 0, Element 1, Element 2 , . . .• We can ac cess ele ments in the list through an iterator05-2: List ADT Operations• Create an empty list• Add (append) an element to the end of the list• Add (in sert) an element at a spectified index• Get the size (leng th) of the list• Remove an element at a specific index• Remove the first occurence of an element• Get an element at a specific index• Get an iterator to traverse the list05-3: Iterators• Think of an iter ator as a “smart bookmark” that is associated with a specific data struc ture• Often used to examine every element in a data structure05-4: IteratorsSome operation on iterators:• Retrieve the current element• Move the iterator forward, to the next element in the data structure• C++ has two different opera tions: “Get current” and “Move forward”• Java has a single operatio n: “Get current and move forward”• Move the iterator backwards, to the p revious element in th e data structure• Not all iteratrs can go backwards• Java also combines going backwards as “Get previous element and move iterator backwards”05-5: IteratorsSome operation on iterators:CS245-2014S-0 5 Abstract Data Types and Lists 2• Delete element a t current location (not always allowed)• Insert an elemen t at the current location (not always allowed)• Operations specific to the particular data structure05-6: List Iterator (first pass)• Get the next element (moving the iterator one forwad)• Check if their is a next element• Remove the object at the current position (current position == last element tha t was returned from a “next”)• Insert an elemen t at the current position (right b e fore the “next” element)05-7: Java Interfaces• A Java interface is a set o f methods.• Any class that im plements an interface must implement all of these me thods05-8: Java List Interfacepublic interface List{public void clear();public void add(Object o);public void add(int index, Object o);public void remove(int index);public void remove(Object o);public int size();public Object get(int index);public ListIterator listIterator();public ListIterator listIterator(int index);}05-9: Java List Iterator Interfacepublic interface ListIterator{public void add(Object o);public boolean hasNext();public Object next();public void remove();public void set(Object o);}05-10: Using Iterators• Print out a list L:CS245-2014S-0 5 Abstract Data Types and Lists 3List L;...ListIterator it = L.listIterator();for (it.hasNext()){System.out.println(it.next());}05-11: Array Implementation• Data is stored in an array• Iterator sto res index of next location• To add an element to the current position:• Shift all elements with index ¿ = current one to right• To remove and element fro m the midd le of the array:• Shift all elements with index ¿ = current to the r ight• List has a maximum size (unle ss we use growable arrays)05-12: Array Implementation Θ() Running Tim e for each operation:List Operations Iterator O perationsadd(ap pend) nextadd(insert) hasNextremove addlistIterator() removelistIterator(n) setsizeget05-13: Array Implementation Θ() Running Tim e for each operation:List Operations Iterator O perationsadd(ap pend) Θ(1) next Θ(1)add(insert) Θ(n) hasNext Θ(1)remove Θ(n) add Θ(n)listIterator() Θ(1) remove Θ(n)listIterator(n) Θ(1) set Θ(1)size Θ(1)get Θ(1)05-14: Linked-List Implementation• Data is stored in a linked list• Maintain a p ointer to first element in list• Iterator maintains a pointer to the next element• To find the ith eleme nt:• Start at the front of the list• Skip past i elementsCS245-2014S-0 5 Abstract Data Types and Lists 4How do we insert an element before the next element? How do we remove the “current” element?05-15: Linked-List Implementation• Data is stored in a linked list• Maintain a p ointer to first element in list• Iterator maintains a pointer to the element before the next element (“current” element) and a pointer to theelement be fore the current element.• To find the ith eleme nt:• Start at the front of the list• Skip past i elementsWhat should “current” p ointer be when the “next” element is the first element in the list?05-16: Linked-List Implementation• Data is stored in a linked list – with a dummy first element• Maintain a p ointer to first (dummy) element in list• Iterator maintains a pointer to the element before the next elemen t (“current” element) and the “previous” ele-ment (what sho uld “pr evious” be wh e n the first element of the list is the next element in the list?)• To find the ith elemen t:• Start at the front of the list• Skip past (i+1) elem e nts05-17: Linked-List Implementation Θ() Running Time for each opera tion:List Operations Iterator O perationsadd(ap pend) nextadd(insert) hasNextremove addlistIterator() removelistIterator(n) setsizeget05-18: Linked-List Implementation Θ() Running Time for each opera tion:List Operations Iterator O perationsadd(ap pend) Θ(1) next Θ(1)add(insert) Θ(n) hasNext Θ(1)remove Θ(n) add Θ(1)listIterator() Θ(1) remove Θ(1)listIterator(n) Θ(n) set Θ(1)size Θ(1)get Θ(n)05-19: Adding Previous• Add a new operation to the iterator : previous• Move the iterator back one element, retu rn the previous elememt• next() followed by previous(), both return same elementCS245-2014S-0 5 Abstract Data Types and Lists 5• How would we implement previous for an array implementation05-20: Adding Previous• Add a new operation to the iterator : previous• Move the iterator back one element, retu rn the previous elememt• next() followed by previous(), both return same element• How would we implement previous for an array implementation• Subtract one from the index of the current location05-21: Adding Previous• Add a new operation to the iterator : previous• Move the iterator back one element• How would we implement previous for a linked list implementation05-22: Adding Previous• Add a new operation to the


View Full Document

USF CS 245 - Abstract Data Types and Lists

Download Abstract Data Types and Lists
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Abstract Data Types and Lists and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Abstract Data Types and Lists 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?