Lists and the Collection InterfaceChapter ObjectivesChapter Objective (continued)The List Interface and ArrayList ClassThe List Interface and ArrayList Class (continued)Slide 6The ArrayList ClassThe ArrayList Class (continued)Generic CollectionsCreating a Generic CollectionSpecification of the ArrayList ClassApplication of ArrayListImplementation of an ArrayList ClassImplementation of an ArrayList Class (continued)Performance of KWArrayList and the Vector ClassSingle-Linked Lists and Double-Linked ListsA List NodeSingle-Linked ListsDouble-Linked ListsDouble-Linked Lists (continued)Inserting into a Double-Linked ListInserting into a Double-Linked List (continued)Removing from a Double-Linked ListCircular ListsCircular Lists ContinuedThe LinkedList<E> ClassThe Iterator<E> InterfaceThe Iterator<E> Interface (continued)The ListIterator<E> InterfaceThe ListIterator<E> Interface (continued)Slide 31Comparison of Iterator and ListIteratorConversion between a ListIterator and an IndexThe Enhanced for StatementThe Iterable InterfaceImplementation of a Double-Linked ListImplementation of a Double-Linked List (continued)Slide 38Slide 39Slide 40Slide 41Slide 42Application of the LinkedList ClassApplication of the LinkedList Class (continued)Slide 45The Collection HierarchyThe Collection Hierarchy (continued)Common Features of CollectionsChapter ReviewChapter Review (continued)Lists and the Collection InterfaceChapter 4Chapter 4: Lists and the Collection Interface 2Chapter Objectives•To become familiar with the List interface•To understand how to write an array-based implementation of the List interface•To study the difference between single-, double-, and circular linked list data structures•To learn how to implement the List interface using a linked-list•To understand the Iterator interfaceChapter 4: Lists and the Collection Interface 3Chapter Objective (continued)•To learn how to implement the iterator for a linked list•To become familiar with the Java Collection frameworkChapter 4: Lists and the Collection Interface 4The List Interface and ArrayList Class•An array is an indexed structure: can select its elements in arbitrary order using a subscript value•Elements may be accessed in sequence using a loop that increments the subscript•You cannot•Increase or decrease the length•Add an element at a specified position without shifting the other elements to make room•Remove an element at a specified position without shifting other elements to fill in the resulting gapChapter 4: Lists and the Collection Interface 5The List Interface and ArrayList Class (continued)•Allowed operations on the List interface include:•Finding a specified target•Adding an element to either end•Removing an item from either end•Traversing the list structure without a subscript•Not all classes perform the allowed operations with the same degree of efficiency•An array provides the ability to store primitive-type data whereas the List classes all store references to Objects. Autoboxing facilitates this.Chapter 4: Lists and the Collection Interface 6The List Interface and ArrayList Class (continued)Chapter 4: Lists and the Collection Interface 7The ArrayList Class•Simplest class that implements the List interface•Improvement over an array object•Used when a programmer wants to add new elements to the end of a list but still needs the capability to access the elements stored in the list in arbitrary orderChapter 4: Lists and the Collection Interface 8The ArrayList Class (continued)Chapter 4: Lists and the Collection Interface 9Generic Collections•Language feature introduced in Java 5.0 called generic collections (or generics)•Generics allow you to define a collection that contains references to objects of a specific type• List<String> myList = new ArrayList<String>(); specifies that myList is a List of String where String is a type parameter•Only references to objects of type String can be stored in myList, and all items retrieved would be of type String. •A type parameter is analogous to a method parameter.Chapter 4: Lists and the Collection Interface 10Creating a Generic CollectionChapter 4: Lists and the Collection Interface 11Specification of the ArrayList ClassChapter 4: Lists and the Collection Interface 12Application of ArrayList•The ArrayList gives you additional capability beyond what an array provides•Combining Autoboxing with Generic Collections you can store and retrieve primitive data types when working with an ArrayListChapter 4: Lists and the Collection Interface 13Implementation of an ArrayList Class•KWArrayList: simple implementation of a ArrayList class•Physical size of array indicated by data field capacity•Number of data items indicated by the data field sizeChapter 4: Lists and the Collection Interface 14Implementation of an ArrayList Class (continued)Chapter 4: Lists and the Collection Interface 15Performance of KWArrayList and the Vector Class•Set and get methods execute in constant time•Inserting or removing elements is linear time•Initial release of Java API contained the Vector class which has similar functionality to the ArrayList•Both contain the same methods•New applications should use ArrayList rather than Vector•Stack is a subclass of VectorChapter 4: Lists and the Collection Interface 16Single-Linked Lists and Double-Linked Lists•The ArrayList: add and remove methods operate in linear time because they require a loop to shift elements in the underlying array•Linked list overcomes this by providing ability to add or remove items anywhere in the list in constant time•Each element (node) in a linked list stores information and a link to the next, and optionally previous, nodeChapter 4: Lists and the Collection Interface 17A List Node•A node contains a data item and one or more links•A link is a reference to a node•A node is generally defined inside of another class, making it an inner class•The details of a node should be kept privateChapter 4: Lists and the Collection Interface 18Single-Linked ListsChapter 4: Lists and the Collection Interface 19Double-Linked Lists•Limitations of a single-linked list include:•Insertion at the front of the list is O(1). •Insertion at other positions is O(n) where n is the size of the list.•Can insert a node only after a referenced node•Can remove a node only if we have a reference to its predecessor node•Can traverse the list only in the forward