{small lecturenumber - heblocknumber :} Abstract Data Typesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} List ADTaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} List ADT Operationsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Iteratorsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Iteratorsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Iteratorsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} List Iterator (first pass)addtocounter{blocknumber}{1}{small lecturenumber - heblocknumber :} Java Interfacesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Java List Interfaceaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Java List Iterator Interfaceaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Using Iteratorsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Array Implementationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Array Implementationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Array Implementationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Linked-List Implementationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Linked-List Implementationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Linked-List Implementationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Linked-List Implementationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Linked-List Implementationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Adding Previousaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Adding Previousaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Adding Previousaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Adding Previousaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Doubly-Linked Listsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Multiple Iteratorsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Multiple Iteratorsaddtocounter {blocknumber}{1}Data Structures and AlgorithmsCS245-2014S-05Abstract Data Types and ListsDavid GallesDepartment of Computer ScienceUniversity of San Francisco05-0: Abstract Data TypesRecall that an Abstract Data Type is a definition ofa type based on t he operations that can beperformed on it.An ADT is an interfaceData in an ADT cannot be manipulated directly –only through operations defined in the interface05-1: List ADTA List is an ordered collecti on of elementsEach element in the li st has a positionElement 0, Element 1, Element 2, . . .We can access elements in the list through aniterator05-2: List ADT OperationsCreate an empty listAdd (append) an element t o the end of the listAdd (insert) an element at a spectified i ndexGet the size (length) of t he listRemove an el ement at a specific indexRemove the first occurence of an elementGet an element at a specific indexGet an iterator to traverse the list05-3: IteratorsThink of an iterator as a “smart bookmark” that i sassociated with a specific data structureOften used to examine every element in a datastructure05-4: IteratorsSome operation on iterators:Retrieve the current elementMove t he iterator forward, to the next element inthe data structureC++ has two different operations: “Get current”and “Move forward”Java has a si ngle operation: “Get current andmove forward”Move t he iterator backwards, to the previouselement in the data structureNot all iteratrs can go backwardsJava also combines going backwards as “Getprevious element and move iterator backwards”05-5: IteratorsSome operation on iterators:Delete element at current location (not alwaysallowed)Insert an element at the current location (notalways allowed)Operations specific to the particular data structure05-6: List Iterator (first pass)Get the next element (moving t he iterator oneforwad)Check if their is a next elementRemove the object at the current positi on (currentposition == last element that was returned from a“next”)Insert an element at the current position (rightbefore the “next” element)05-7: Java I nterfacesA Java interface is a set of methods.Any class that implements an interface mustimplement all of these methods05-8: Java List I nterfacepublic 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 I t erator 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 IteratorsPrint out a list L:List L;...ListIterator it = L.listIterator();for (it.hasNext()){System.out.println(it.next());}05-11: Array ImplementationData is stored in an arrayIterator stores index of next locationTo add an element to the current position:Shift all elements with index >= current one torightTo remove and element from the middle of thearray:Shift all elements with index >= current to therightList has a maximum size (unless we use growablearrays)05-12: Array ImplementationΘ() Running Ti m e for each operation:List Operations Iterator Operationsadd(append) nextadd(insert) hasNextremove addlistIterator() removelistIterator(n) setsizeget05-13: Array ImplementationΘ() Running Ti m e for each operation:List Operations Iterator Operationsadd(append) Θ(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 ImplementationData is stored in a l inked listMaintain a pointer to first element in listIterator maintai ns a pointer t o the next elementTo find the ith el ement:Start at the f ront of the listSkip past i elementsHow do we insert an element before the next element?How do we remove the “current” element?05-15: Linked-List ImplementationData is stored in a l inked listMaintain a pointer to first element in listIterator maintai ns a pointer t o the element beforethe next element (“current” element) and a pointerto the element before the current element.To find the