jdc tech tips body_216095411795471888hermessuncom imagehttpdeveloperjavasuncomimagespixelgif imagehttpdeveloperjavasuncomimagespixelgif core java technologies technical tipshttpdeveloperjavasuncomimagesheaderscore_ttips_hdrjpg imagehttpdeveloperjavasuncomimagespixelgif view issue simple text september 10 2002 issue welcome core javatm technologies tech tips september 10 2002 youll get tips using core java technologies apis java 2 platform standard edition j2setm httpdeveloperjavasuncomimagesanchorgifusing arraylist linkedlist httpdeveloperjavasuncomimagesanchorgifusing zerolength arrays tips developed using java 2 sdk standard edition v 14 issue jdc tech tips written glen mccluskey pixelhttpdeveloperjavasuncomimagespixelgif using arraylist linkedlist arraylist linkedlist two collections classes used storing lists object references example could arraylist strings linkedlist integers tip compares performance arraylist linkedlist offers suggestions classes right choice given situation first key point arraylist backed primitive object array arraylist much faster linkedlist random access accessing arbitrary list elements using get method note get method implemented linkedlists requires sequential scan front back list scan slow linkedlist theres fast way access nth element list consider following example suppose large list sorted elements either arraylist linkedlist suppose binary search list standard binary search algorithm starts checking search key value middle list middle value high upper half list eliminated however middle value low lower half list ignored process continues key found list lower bound search becomes greater upper bound heres program binary search elements arraylist linkedlist import javautil public class listdemo1 static final int n 10000 static list values make list increasing integer values static integer vals new integern random rn new random int 0 currval 0 n valsi new integercurrval currval rnnextint100 1 values arraysaslistvals iterate across list look every value list using binary search static long timelistlist lst long start systemcurrenttimemillis int 0 n look value list using binary search int indx collectionsbinarysearch lst valuesgeti sanity check result binary search indx systemoutprintln error n return systemcurrenttimemillis start public static void mainstring args lookups arraylist systemoutprintlntime arraylist timelistnew arraylistvalues lookups linkedlist systemoutprintln time linkedlist timelistnew linkedlistvalues listdemo1 program sets list sorted integer values adds values arraylist linkedlist collectionsbinarysearch used search value list run program see result looks something like time arraylist 31 time linkedlist 4640 arraylist 150 times faster linkedlist results might differ depending machine characteristics see distinct difference result arraylist compared linkedlist true programs tip clearly linkedlist bad choice situation binary search algorithm inherently uses random access linkedlist support fast random access time random access linkedlist proportional size list comparison random access arraylist fixed time use randomaccess marker interface check whether list supports fast random access void flist lst lst instanceof randomaccess supports fast random access arraylist implements randomaccess interface linkedlist note collectionsbinarysearch take advantage randomaccess property optimize searches results prove arraylist always better choice necessarily many cases linkedlist better also note many situations algorithm implemented efficiently linkedlist example reversing linkedlist using collectionsreverse internal algorithm gets reasonable performance using forward backward iterators lets look another example suppose list elements lot element inserting deleting list case linkedlist better choice demonstrate consider following worst case scenario demo program repeatedly inserts elements beginning list code looks like import javautil public class listdemo2 static final int n 50000 time long takes add n objects list static long timelistlist lst long start systemcurrenttimemillis object obj new object int 0 n lstadd0 obj return systemcurrenttimemillis start public static void mainstring args timing arraylist systemoutprintln time arraylist timelistnew arraylist timing linkedlist systemoutprintln time linkedlist timelistnew linkedlist run program result look something like time arraylist 4859 time linkedlist 125 results pretty much reverse previous example element added beginning arraylist existing elements must pushed back means lot expensive data movement copying contrast adding element beginning linkedlist simply means allocating internal record element adjusting couple links adding beginning linkedlist fixed cost adding beginning arraylist cost thats proportional list size far tip looked speed issues space lets look internal details arraylist linkedlist implemented java 2 sdk standard edition v 14 details part external specification classes illustrative classes work internally linkedlist class private internal class defined like private static class entry object element entry next entry previous entry object references list element along next previous elements linkedlist words doublylinked list linkedlist 1000 elements 1000 entry objects linked together referencing actual list elements significant space overhead linkedlist structure given entry objects arraylist backing object array store elements array starts capacity 10 array needs grow new capacity computed newcapacity oldcapacity 3 2 1 notice array capacity grows time 50 means arraylist large number elements significant amount space wasted end waste intrinsic way arraylist works spare capacity array would reallocated new element performance would suffer dramatically changing growth strategy aggressive doubling size reallocation would result slightly better performance would waste space know many elements arraylist specify capacity constructor also call trimtosize method fact reallocate internal array gets rid wasted space far discussion assumed either arraylist linkedlist right given application sometimes choices make sense example consider common situation list keyvalue pairs would like retrieve value given key could store pairs n x 2 object array find right pair could sequential search key values approach works useful choice small lists say 10 elements less doesnt scale big lists another approach sort keyvalue pairs ascending key value store result pair arraylists binary search keys list approach also works fast yet another approach use list structure instead use map structure hash table form hashmap faster binary search arraylist hashmap heres final example compares two import javautil public class listdemo3 static final int n 500000 lists keys values static list keys static list values fill keys list ascending order key values fill values list corresponding values key static integer keyvec new integern integer valuevec new integern random rn new random int 0 currval 0 n keyveci new integercurrval valueveci new integercurrval currval rnnextint100 1 keys arraysaslistkeyvec values arraysaslistvaluevec fill map keyvalue pairs static map map new hashmap static int 0 n mapputkeysgeti valuesgeti binary search lookup keys static long timelist long start systemcurrenttimemillis int 0 n int indx collectionsbinarysearch keys keysgeti sanity check returned value binary search indx systemoutprintln error n return systemcurrenttimemillis start map lookup keys static long timemap long start systemcurrenttimemillis int 0 n integer value integermapget keysgeti sanity check value returned map lookup value valuesgeti systemoutprintln error n return systemcurrenttimemillis start public static void mainstring args timing list implementation systemoutprintlnlist time timelist timing map implementation systemoutprintlnmap time timemap program sets lists keys values uses two different techniques map keys values one approach uses binary search list hash table run listdemo3 program get result looks something like arraylist time 1000 hashmap time 281 example n value 500000 approximately log2n 1 comparisons required average successful binary search binary search lookup arraylist take 18 comparisons contrast properly implemented hash table typically requires 13 comparisons expect hash table faster case however binary search still useful example might want lookup sorted list find keys close value key used lookup easy binary search impossible hash table keys hash table stored apparent random order also concerned worstcase performance binary search algorithm offers much stronger performance guarantee hash table scheme might also consider using treemap lookups sorted collections keyvalue pairs lets summarize key points presented tip appending elements end list fixed averaged cost arraylist linkedlist arraylist appending typically involves setting internal array location element reference occasionally results array reallocated linkedlist cost uniform involves allocating internal entry object inserting deleting elements middle arraylist implies rest list must moved inserting deleting elements middle linkedlist fixed cost linkedlist support efficient random access arraylist space overhead form reserve capacity end list linkedlist significant space overhead per element sometimes map structure better choice list information using arraylist linkedlists see section 166 list section 167 map sortedmap javatm programming language third edition arnold gosling holmes also see collections trail java tutorial third edition back toppixelhttpdeveloperjavasuncomimagesback_to_topgif pixelhttpdeveloperjavasuncomimagespixelgif pixelhttpdeveloperjavasuncomimagespixelgif using zerolength arrays suppose writing java application involves sort data filtering raw data want clean process various ways one methods youve written takes array integers along minimum maximum values method goes array eliminates outliers values small big result filtering process new array cleanedup data could implement kind filtering method heres one approach import javautil public class zerodemo1 filter input array throw away values less minval greater maxval static int filterdata int indata int minval int maxval check parameters errors indata null throw new nullpointerexception indata null maxval minval throw new illegalargumentexception maxval minval count number valid values input array int validcnt 0 int 0 indatalength indatai minval indatai maxval validcnt valid values return null validcnt 0 return null copy valid values new array return int outdata new intvalidcnt int 0 j 0 indatalength indatai minval indatai maxval outdataj indatai return outdata public static void mainstring args set test array integers int indata new int1 3 17 8 59 filter values range 110 int outdata1 filterdataindata 1 10 int 0 outdata1length systemoutprintlnoutdata1i filter values range 100200 int outdata2 filterdata indata 100 200 int 0 outdata2length systemoutprintlnoutdata2i filterdata method two scans input array first scan counts number valid data values method allocates new array appropriate size copies good values good values method returns null value array reference result running zerodemo1 program 1 3 8 exception thread main javalangnullpointerexception zerodemo1mainzerodemo1java72 problem program rather basic one second call filterdata returns null value program fails take possibility account better approach example would comment block code tests possibility valid data values validcnt 0 return null valid data code fall next line zerolength array allocated int outdata new int0 perfectly legal java usage representation java arrays includes length array therefore possible tell array zero length zerodemo1 example anticipate validcnt often zero data filtering often eliminate values input could optimize away second input scan adding code like int outdata new intvalidcnt validcnt 0 return outdata note usage int outdata new int also legal initialize array zerolength set integer constants general best return null method returns array type always returning array even array zero length greatly improves generality algorithms anticipate methods often return zerolength arrays might concerned performance implications allocating many arrays case allocate single array always return one follows private static final int zero_length_array new int0 array immutable cant changed shared throughout application theres another way zerolength arrays used illustrated following example import javautil public class zerodemo2 public static void mainstring args set arraylist add strings list stringlist new arraylist stringlistaddstring 1 stringlistaddstring 2 stringlistaddstring 3 convert string array string stringstringlisttoarray new string0 int 0 outlength systemoutprintlnouti result running zerodemo2 program string 1 string 2 string 3 zerodemo2 program sets arraylist adds three strings program calls toarray get string array three elements arraylist example argument toarray new string0 argument serves couple purposes first string array thats big enough hold elements arraylist specify argument toarray method use string array array big enough toarray method allocates array return elements uses type array passed determine type allocated array arraylist stores element references object array toarray method needs told type string used returning array elements method uses reflection javalangreflectarraynewinstance create array appropriate type information using zerolength arrays see item 27 return zero length arrays nulls effective java programming language guide joshua bloch back toppixelhttpdeveloperjavasuncomimagesback_to_topgif pixelhttpdeveloperjavasuncomimagespixelgif pixelhttpdeveloperjavasuncomimagespixelgif important please read terms use privacy licensing policies httpwwwsuncomsharetexttermsofusehtml httpwwwsuncomprivacy httpdeveloperjavasuncomberkeley_licensehtml comments send feedback javatm technology fundamentals newsletter jdcwebmastersuncom subscribe following newsletters latest information technologies products java platforms enterprise java technologies tech tips get tips using enterprise java technologies apis java 2 platform enterprise edition j2eetm wireless developer tech tips get tips using wireless java technologies apis java 2 platform micro edition j2metm subscribe jdc publications go jdc newsletters publications page choose newsletters want subscribe click update unsubscribe go subscriptions page uncheck appropriate checkbox click update archives youll find core java technologies tech tips archives httpjavasuncomjdctechtipsindexhtml copyright 2002 sun microsystems inc rights reserved 901 san antonio road palo alto california 94303 usa sun sun microsystems java java developer connection j2se j2ee j2me trademarks registered trademarks sun microsystems inc united states countries sun microsystems inchttpdeveloperjavasuncomimageslgsungif httpdeveloperjavasuncomimagespixelgif httpdeveloperjavasuncomimagespixelgif please send newsletters text please unsubscribe newsletterhttpbulkmail2suncomotservletid216095411795471888 10 sep 2002 082412 0800 core java technologies tech tips september 10 2002 arraylist vs linkedlist zerolength arrays