Chapter 10OverviewVectorsUsing VectorsInitial Capacity and Efficiency:a Classic Engineering TradeoffVector SyntaxVector MethodsA little Detail about setElementAtBase Type of VectorsDetail: One Consequence of the Base Type of Vectors Being ObjectArrays Versus VectorsOne More Detail:Size Versus CapacityProgramming Tip: Adding to a VectorProgramming Tip:Increasing Storage Efficiency of VectorsDeclaring a VectorAnd Another Detail:Correcting the Return Type of cloneLinked ListsListNode Class:Instance Variables and ConstructorStepping through a ListAdding a NodeDeleting a NodeGotcha: Null Pointer ExceptionNode Inner ClassesIteratorsgoToNextOther Methods in the Linked List with IteratorAdding a NodeStep 1Adding a NodeStep 2Adding a NodeDeleting a NodeStep 1Deleting a NodeStep 2FAQ: What Happens to a Deleted Node?A Doubly Linked ListOther Linked Data StructuresSummaryChapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch1Chapter 10Dynamic Data Structuresz Vectorsz Linked Data StructuresChapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch2Overviewz This chapter is about data structures that are dynamic:They can grow and shrink while your program is runningz Vectors are similar to arrays but are more flexible.z Linked lists are a dynamic data structure commonly used in many programming languages.Chapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch3Vectors"Well, I'll eat it," said Alice, "and if it makes me grow larger, I can reach the key; and if it makes me grow smaller, I can creep under the door; so either way I'll get into the garden…"Lewis Carroll, Alice's Adventures in WonderlandVECTORSThink of them as arrays that can get larger or smallerwhen a program is running.Chapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch4Using Vectorsz Vectors are not automatically part of Java» they are in the util library» you must import java.util.*z Create a vector with an initial capacity of 20 elements:Vector v = new Vector(20);Chapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch5Initial Capacity and Efficiency:a Classic Engineering Tradeoffz Engineering involves making difficult tradeoffs» "There's no such thing as a free lunch."– an American saying» Usually, if you gain something you lose something somewhere elsez Choosing the initial capacity of a vector is an example of a tradeoff» making it too large wastes allocated memory space» making it too small slows execution– it takes time to resize vectors dynamically z Solution?» optimize one at the expense of the other» or make good compromises– choose a size that is not too big and not too smallChapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch6Vector Syntaxz The idea is the same as for arrays, but the syntax is differentz As with arrays, the index must be in the range 0 to (size-of-the-vector – 1)Array: a is a String arraya[i] = "Hi, Mom!";String temp = a[i];Vector:v is a vectorv.setElementAt("Hi, Mom!", i);String temp = (String)v.elementAt(i);Use vector method elementAt(int index) to retrieve the value of an elementNote: the cast to String is required because the base type of vector elements is ObjectInstead of the index in brackets and = for assignment, use vector method setElementAtwith two arguments, the value and the indexChapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch7Vector Methodsz The vector class includes many useful methods:» constructors» array-like methods, e.g. setElementAt & elementAt» methods to add elements» methods to remove elements» search methods» methods to work with the vector's size and capacity, e.g. to find its size and check if it is empty»a clone method to copy a vectorz See the text for more informationChapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch8A little Detail about setElementAt"The devil's in the details."– an American engineering sayingz Vectors put values in successive indexes» addElement is used to put initial values in a vector» new values can be added only at the next higher indexz You cannot use setElementAt to put a value at just any index» setElementAt can be used to assign the value of an indexed variable only if it has been previously assigned a value with addElementChapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch9Base Type of Vectorsz The base type of an array is specified when the array is declared» all elements of arrays must be of the same typez The base type of a vector is Object» elements of a vector can be of any classtype»in fact,elements of a vector can be of differentclass types!» to store primitive types in a vector they must be converted to acorresponding wrapper classGood Programming PracticeAlthough vectors allow elements in the same vector to be of different class types, it is best not to have a mix of classes in the same vector -– it is best to have all elements in a vector be the same class type.Chapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch10Detail: One Consequence of the Base Type of Vectors Being Objectz The following code looks very reasonable but will produce an error saying that the class Object does not have a method named length:Vector v = new Vector(10);String greeting = "Hi, Mom!";v.addElement(greeting);System.out.println("Length is " + (v.elementAt(0)).length());z String, of course, does have a length method, but Java sees the type of v.elementAt(0) as Object, not Stringz Solution? Cast v.elementAt(0) to String:System.out.println("Length is " + (String)(v.elementAt(0)).length());Chapter 10 Java: an Introduction to Computer Science & Programming - Walter Savitch11Arrays Versus VectorsArraysBad:z Size is fixed when declaredz Inefficient storage: can use a partially full array, but space has been allocated for the full sizez If one more value needs to be added past the maximum size, the array needs to be redeclaredGood:z More efficient (faster) executionz Allows primitive type elementsVectorsGood :z Size is not fixedz Better storage efficiency: a partially full vector may be allocated just the space it needsz If one more value needs to be added past the maximum size, the vector size increases automaticallyBad:z Less efficient (slower) executionz Elements must be class types (primitive types not allowed)Chapter 10