Lists I The List ADT List ADT A list is a dynamic ordered tuple of homogeneous elements Ao A1 A2 AN 1 where Ai is the i th element of the list The position of element Ai is i positions range from 0 to N 1 inclusive The size of a list is N a list with no elements is called an empty list 8 3 2007 UMBC CMSC 341 Lists1 2 Generic Operations on a List create an empty list printList prints all elements in the list construct a deep copy of a list find x returns the position of the first occurrence of x remove x removes x from the list if present insert x position inserts x into the list at the specified position isEmpty returns true if the list has no elements makeEmpty removes all elements from the list findKth int k returns the element in the specified position 8 3 2007 UMBC CMSC 341 Lists1 3 Simple Array Implementation of a List Use an array to store the elements of the list printList is O n findkth get and set are constant time Insert 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 2007 UMBC CMSC 341 Lists1 4 Simple Linked List Implementation Linked List Deletion 8 3 2007 UMBC CMSC 341 Lists1 5 Linked List Implementation of a List Insertion Notice insert and delete can be constant time if node is inserted at beginning of List however findkth is now O i 8 3 2007 UMBC CMSC 341 Lists1 6 The List ADT in Java The List ADT is one of the data structures Collections 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 Java 8 3 2007 UMBC CMSC 341 Lists1 7 Methods from the Collections from ADT Collection interface List int 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 2007 UMBC CMSC 341 Lists1 8 The Iterator E Interface The Collections framework provides two very useful interfaces for traversing a Collection 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 2007 UMBC CMSC 341 Lists1 9 Using an Iterator to Traverse a Collection Example 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 2007 UMBC CMSC 341 Lists1 10 The Enhanced for Loop The 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 2007 UMBC CMSC 341 Lists1 11 The ListIterator E Interface The second interface for traversing a Collection 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 listIterator method on a List 8 3 2007 UMBC CMSC 341 Lists1 12 Concrete Implementations of the List ADT in the Java Collections API Two concrete implementations of the List API in the Java Collections API with which you are already familiar are java util ArrayList java util LinkedList Let s examine the methods of these concrete classes that were developed at Sun 8 3 2007 UMBC CMSC 341 Lists1 13 List Operations on an ArrayList E Supports constant time for insertion at the end of the list using void add int index E element deletion from the end of the list using E remove int index access to any element of the list using E get int index changing value of any element of the list using E set int index E element 8 3 2007 UMBC CMSC 341 Lists1 14 List Operations on an ArrayList E cont What is the growth rate for the following 8 3 2007 insertion at the beginning of the list using void add int index E element deletion from the beginning of the list using E remove int index UMBC CMSC 341 Lists1 15 List Operations on a LinkedList E Provides doubly linked list implementation 8 3 2007 UMBC CMSC 341 Lists1 16 List Operations on a LinkedList E Supports constant time for insertion at the beginning of the list using void addFirst E o insertion at the end of the list using void addLast E o deletion from the beginning of the list using E removeFirst deletion from the end of the list using E removeLast Accessing first element of the list using E getFirst 8 3 2007 Accessing first element of the list using E getLast UMBC CMSC 341 Lists1 17 List Operations on a LinkedList E What is the growth rate for the following 8 3 2007 access to the middle element of the list using E get int index UMBC CMSC 341 Lists1 18 Example 1 ArrayList vs LinkedList What is the running time for an ArrayList versus a LinkedList public static void makeList1 List Integer list int N list clear example of autoboxing for int i 0 i N i list add i 8 3 2007 UMBC CMSC 341 Lists1 19 Example 2 ArrayList vs LinkedList What is the running time for an ArrayList versus a LinkedList public static void makeList2 List Integer list int N list clear l for int i 0 i N i list add 0 i 8 3 2007 UMBC CMSC 341 Lists1 20 Example 3 ArrayList vs LinkedList What is the running time for an ArrayList versus a LinkedList public static int sum List Integer list int N int total 0 for int i 0 i N i total list get i return total How can we change this code so the running time for both is the same 8 3 2007 UMBC CMSC 341 Lists1 21 Example 4 ArrayList vs LinkedList What is the running time for an ArrayList versus a LinkedList public static void removeEvensVer3 List Integer lst Iterator Integer itr lst iterator while itr hasNext if itr next 2 0 itr remove 8 3 2007 UMBC CMSC 341 Lists1 22 Implementing Your Own ArrayList What do you need Store elements in a parametrized array 2 Track number of elements in array size and capacity of …