Lists - IList ADTGeneric Operations on a ListSimple Array Implementation of a ListSimple Linked List ImplementationLinked List Implementation of a ListThe List ADT in Java CollectionsMethods from the Collections List ADTThe Iterator<E> InterfaceUsing an Iterator to Traverse a CollectionThe Enhanced for LoopThe ListIterator<E> InterfaceConcrete Implementations of the List ADT in the Java Collections APIList Operations on an ArrayList<E>List Operations on an ArrayList<E> (cont.)List Operations on a LinkedList<E>Slide 17Slide 18Example 1 –ArrayList vs. LinkedListExample 2 –ArrayList vs. LinkedListExample 3 –ArrayList vs. LinkedListExample 4 –ArrayList vs. LinkedListImplementing Your Own ArrayList3. Ability to change capacity of the array4. get and set Methods5. size, isEmpty, and clear Methods6. add Methods7. remove and iterator Method8. Iterator classThe Iterator and Java Inner classesSorted ListsLists - IThe List ADT8/3/2007UMBC CMSC 341 Lists12List ADTA list is a dynamic ordered tuple of homogeneous elementsAo, A1, A2, …, AN-1where Ai is the i-th element of the listThe position of element Ai is i; positions range from 0 to N-1 inclusiveThe size of a list is N ( a list with no elements is called an “empty list”)8/3/2007UMBC CMSC 341 Lists13Generic Operations on a Listcreate an empty listprintList() – prints all elements in the listconstruct a (deep) copy of a listfind(x) – returns the position of the first occurrence of x remove(x) – removes x from the list if presentinsert(x, position) – inserts x into the list at the specified positionisEmpty( ) – returns true if the list has no elementsmakeEmpty( ) – removes all elements from the listfindKth(int k) – returns the element in the specified position8/3/2007UMBC CMSC 341 Lists14Simple Array Implementation of a ListUse an array to store the elements of the listprintList is O(n)findkth,get and set are constant timeInsert and delete?Also, arrays have a fixed capacity, but can fix with implementation.int []arr = new int arr[10];int []newArr = new int[arr.length *2];for(int i = 0;I < arr.length; i++)newArr[i] = arr[i];arr = newArr;8/3/2007UMBC CMSC 341 Lists15Simple Linked List ImplementationLinked ListDeletion8/3/2007UMBC CMSC 341 Lists16Linked List Implementation of a ListInsertionNotice insert and delete can be constant time if node is inserted at beginning of List; however, findkth is now O(i).8/3/2007UMBC CMSC 341 Lists17The List ADT in Java CollectionsThe List ADT is one of the data structures implemented in the Java Collections API. A list is abstracted using an inheritance hierarchy that stems from the Collection<E> interface , List<E>Interface in the java.util package and from the Iterable<E> interface in the java.lang package.The combination of these interfaces provides a uniform public interface for all Lists in Java8/3/2007UMBC CMSC 341 Lists18Methods from the Collections List ADT//from Collection interfaceint size( );boolean isEmpty( );void clear( );boolean contains( AnyType x );boolean add( AnyType x );boolean remove( AnyType x );java.util.Iterator<AnyType> iterator( );//from List interface AnyType get( int idx ); AnyType set( int idx, AnyType newVal ); void add( int idx, AnyType x ); void remove( int idx ); ListIterator<AnyType> listIterator(int pos);8/3/2007UMBC CMSC 341 Lists19The Iterator<E> InterfaceThe Collections framework provides two very useful interfaces for traversing a Co lle ction. The first is the Iterator<E> interface. When the iterator method is called on a Collection, it returns an Iterator object which has the following methods for traversing the Collection. boolean hasNext( ); AnyType next( ); void remove( );8/3/2007UMBC CMSC 341 Lists110Using an Iterator to Traverse a CollectionExample of using an Iterator object to traverse a Collection.public static <AnyType>void print( Collection<AnyType> coll ) { Iterator<AnyType> itr = coll.iterator( ); while( itr.hasNext( ) ){ AnyType item = itr.next( ); System.out.println( item ); } }8/3/2007UMBC CMSC 341 Lists111The Enhanced for LoopThe enhanced for loop in Java actually calls the iterator method when traversing a Collection and uses the Iterator to traverse the Collection when translated into byte code.public static <AnyType> void print( Collection<AnyType> coll ) { for( AnyType item : coll ) System.out.println( item ); }8/3/2007UMBC CMSC 341 Lists112The ListIterator<E> InterfaceThe second interface for traversing a Co llection is the ListIterator<E> interface. It allows for the bidirectional traversal of a List. boolean hasPrevious( ); AnyType previous( ); void add( AnyType x ); void set( AnyType newVal );A ListIterator object is returned by invoking the lis tIterator method on a Lis t.8/3/2007UMBC CMSC 341 Lists113Concrete Implementations of the List ADT in the Java Collections APITwo concrete implementations of the List API in the Java Collections API with which you are already familiar are:java.util.ArrayListjava.util.LinkedListLet’s examine the methods of these concrete classes that were developed at Sun.8/3/2007UMBC CMSC 341 Lists114List Operations on an ArrayList<E> Supports constant time forinsertion at the “end” of the list usingvoid add(int index, E element) deletion from the “end” of the list usingE remove(int index) access to any element of the list usingE get(int index) changing value of any element of the list using E set(int index, E element)8/3/2007UMBC CMSC 341 Lists115List Operations on an ArrayList<E> (cont.) What is the growth rate for the following?insertion at the “beginning” of the list usingvoid add(int index, E element) deletion from the “beginning” of the list usingE remove(int index)8/3/2007UMBC CMSC 341 Lists116List Operations on a LinkedList<E> Provides doubly linked list implementation8/3/2007UMBC CMSC 341 Lists117List Operations on a LinkedList<E> Supports constant time forinsertion at the “beginning” of the list usingvoid addFirst(E o) insertion at the “end” of the list usingvoid addLast(E o) deletion from the “beginning” of the list usingE removeFirst()deletion from the “end” of the list usingE removeLast()Accessing first element of the list usingE getFirst()Accessing first element of the list using E getLast()8/3/2007UMBC CMSC 341 Lists118List
View Full Document