In our September 10, 2005 newsletter, we provided a three-part tutorial that introduced Java generics and showed how to create your own generic methods. In this four-part tutorial, we present Java 5.0's List collections, which are now implemented as generic classes. Part 1 overviews the classes of the java.util package that implement the List interface-ArrayList, LinkedList and Vector. Parts 2, 3 and 4 present code examples that demonstrate each of these classes. We use various List capabilities and show how iterators can be used to traverse collections to access (and possibly modify) their elements. We also demonstrate Java 5.0's enhanced for statement, which uses a collection's iterator to traverse the collection. This tutorial is intended for students who are already familiar with Java and for Java developers.
[Note: This series of four tutorials (Part 1, Part 2, Part 3, Part 4) is an excerpt (Section 19.5) of Chapter 19, Collections, from our textbook Java How to Program, 6/e. These tutorials may refer to other chapters or sections of the book that are not included here. Permission Information: Deitel, Harvey M. and Paul J., JAVA HOW TO PROGRAM, ©2005, pp.911-922. Electronically reproduced by permission of Pearson Education, Inc., Upper Saddle River, New Jersey.]
19.5 Introduction to Lists
A List (sometimes called a sequence) is an ordered Collection that can contain duplicate elements. Like array indices, List indices are zero based (i.e., the first element’s index is zero). In addition to the methods inherited from Collection, List provides methods for manipulating elements via their indices, manipulating a specified range of elements, searching for elements and getting a ListIterator to access the elements. Interface List is implemented by several classes, including classes ArrayList, LinkedList and Vector. Autoboxing occurs when you add primitive-type values to objects of these classes, because they store only references to objects. Class ArrayList and Vector are resizable-array implementations of List. Class LinkedList is a linked-list implementation of interface List. Class ArrayList’s behavior and capabilities are similar to those of class Vector. The primary difference between Vector and ArrayList is that objects of class Vector are synchronized by default, whereas objects of class ArrayList are not. Also, class Vector is from Java 1.0, before the collections framework was added to Java. As such, Vector has several methods that are not part of interface List and are not implemented in class ArrayList, but perform identical tasks. For example, Vector methods addElement and add both append an element to a Vector, but only method add is specified in interface List and implemented by ArrayList. Unsynchronized collections provide better performance than synchronized ones. For this reason, ArrayList is typically preferred over Vector in programs that do not share a collection among threads.
Performance Tip 19.1
|ArrayLists behave like Vectors without synchronization and therefore execute faster than Vectors because ArrayLists do not have the overhead of thread synchronization.|
Software Engineering Observation19.3
|LinkedLists can be used to create stacks, queues, trees and deques (double-ended queues, pronounced “decks”). The collections framework provides implementations of some of these data structures.|
The following three subsections demonstrate the List and Collection capabilities with several examples. Section 19.5.1 focuses on removing elements from an ArrayList with an Iterator. Section 19.5.2 focuses on ListIterator and several List- and LinkedList-specific methods. Section 19.5.3 introduces more List methods and several Vector-specific methods.