quicklyin ( timebut searching takes slow (ntime in an ordered array you can search quicklyin (logntimebut insertion takes (ntime for both kinds of arraysdeletion takes (ntime because half the items (on the averagemust be moved to fill in the hole it would be nice if there were data structures that could do everything--insertiondeletionand searching--quicklyideally in ( timebut if not thatthen in (logntime in the aheadwe'll see how closely this ideal can be approachedand the price that must be paid in complexity another problem with arrays is that their size is fixed when they are first created with new usuallywhen the program first startsyou don' know exactly how many items will be placed in the array laterso you guess how big it should be if your guess is too largeyou'll waste memory by having cells in the array that are never filled if your guess is too smallyou'll overflow the arraycausing at best message to the program' userand at worst program crash other data structures are more flexible and can expand to hold the number of items inserted in them the linked listdiscussed in "linked lists,is such structure we should mention that java includes class called vector that acts much like an array but is expandable this added capability comes at the expense of some loss of efficiency you might want to try creating your own vector class if the class user is about to overflow the internal array in this classthe insertion algorithm creates new array of larger sizecopies the old array contents to the new arrayand then inserts the new item this whole process would be invisible to the class user summary arrays in java are objectscreated with the new operator unordered arrays offer fast insertion but slow searching and deletion wrapping an array in class protects the array from being inadvertently altered class interface is composed of the methods (and occasionally fieldsthat the class user can access class interface can be designed to make things simple for the class user binary search can be applied to an ordered array the logarithm to the base of number is (roughlythe number of times you can divide by before the result is less than linear searches require time proportional to the number of items in an array