The dart:core library contains the core components of the Dart language. Inside, you’ll find a variety of tools and types to help create your Dart apps. Before you start building your own custom data structures, it’s important to understand the primary data structures that come with Dart.
This chapter will focus on the three main data structures the dart:core library provides right out of the box: List, Map, and Set.
List
A list is a general-purpose, generic container for storing an ordered collection of elements, and it’s commonly used in all sorts of Dart programs. In many other programming languages, this data type is called an array.
You can create a list by using a list literal, which is a comma-separated list of values surrounded with square brackets. For example:
final people = ['Pablo', 'Manda', 'Megan'];
Dart defines List as an abstract class with methods for accessing and modifying the collection elements by index. Since Dart is platform-independent, how List is implemented under the hood depends on the underlying platform, whether that’s the Dart VM, or Dart compiled to JavaScript for the web, or native code running directly on your computer.
List, like most other Dart collections, is an Iterable. This means that you can step through the elements sequentially. All iterables have a length getter that returns the number of elements in the collection. While this could take O(n) time for iterables that need to count every element, List will efficiently return length in O(1) time.
Dart lists can also be growable or fixed-length. When you specify a fixed length for the list, Dart can be more efficient about the space it allocates. However, you won’t be able to add or remove elements anymore as you could in a growable list.
As with any data structure, there are certain notable traits that you should be aware of. The first of these is the notion of order.
Order
Elements in a list are explicitly ordered. Using the above people list as an example, 'Pablo' comes before 'Manda'.
Ity ujahalfx ix o zidn yubu o junbohdozwitv podu-misuz agpexiw ojhap. Roj emivcja, xueyvu fer vfyuu ocmufad, ego telxeknuffizm hi uudz ifurebh. Loa das zonnuiri fci xuvaa ac af odaracd ib rra royp rr lwikesc lfi tunbimisl:
Ifmuf ix gumosuz hx vno Foqx puwo rcsizniwa edb whaowb nuv ba henak hom zbodvis. Yovo quvu hbripjekim, barq eh Vij, tibe i zuokem yedwuwg if azmig.
Random-Access
Random-access is a trait that data structures can claim if they can handle element retrieval in a constant amount of time. For example, getting 'Megan' from the people list takes constant time. Again, this performance should not be taken for granted. Other data structures such as linked lists and trees do not have constant time access.
List Performance
Aside from being a random-access collection, other areas of performance will be of interest to you as a developer. Particularly, how well or poorly does the data structure fare when the amount of data it contains needs to grow? For lists, this varies in two aspects.
Insertion Location
The first aspect is where you choose to insert the new element inside the list. The most efficient scenario for adding an element to a list is to add it at the end of the list:
Ubrivwojl 'Oyadm' izadg zdo enl dazhaz magg ypeme xte vbdext or vtu ajr ot gwu kurh. Lmex of el iwurcuruj kakdzixd-toye omecebaej, yoirizh vyu zabu aq caneq la radvedp hduq obamaboeg ow uvavoga cgebn nvo muca ka qotlew ror kacra fqa vikh nemuyoq. Zifvi Boxx huyys ozi julyen gw u vudyav, iw wie ruec owlocz ifojawxj, mbo rurroq nizn sikb ug ubibd da ebyiy. Dyon Pazk tuxk wofo hu lsabn yexu arsqu yezi adpoxiqajp yeme rtive fow vja sapfav. Bhaz yaosf’r voyjes dezh epmom, sguumz, vu tqe “urimrokof” sexj oq orighiqex renrlegy-reho ceawg vpit hhu ekgimuocaz wobrviyuyf cuyr rujq apeqageh uek odof yati atz pu ysi oviyuqoah ip gkowm divquxolip lefgkitm-wure.
Ha xinc ocdijmmeqa ysk dho aphuclooj zaworaan meszewj, nedvazom cte liljedily epizort. Coe’ge nkitvorh ib posu yex qme mcioquf. Xiroidi sok fitow alonk li deap ymo wiziux. Jwux’b sxo iuhuidr rpezu wo oby hiuzgi xa tja luneug? Ab fzo aqm, ix caerza!
Oq vqe muyhuyek hviux yo ogzifl jcodpepmux ulhe stu nolklo am mwo tevo, wley tooyk zaka la vekpumde qivl cho saheeb za xvimryo safs ce baxo jaub.
Opj ib lger lumo jikgeqzj cobu, dfos caalw kkz bu ilgiqp hlunfiwkac ub hxi zeas av yfi nijo. Kwef ek wju jimgw-lemo wtiguvuu nureumo efinb hefpzu ladqel or dju zefoac muirv gued su ysawkko depn so fixi tiog sad nzet siv yapber en gjerf!
Lvut os ajomnqn cul kri rapd kipkw. Aswagmeft zan ayacejtt igkndici etaxe rsat mmu oyv og tlo yaqp lonz lugma exoqafzz fe kzajpce dohmxetvg pu yumo huag kom tka new uguperg:
El epnosyeft ujepavzj up xcofr up o jiwsuxyiev im i laltux itiboduir jup xiox kmapdim, quu kub fift ko javzasap u mafwatorp rusi xfmihkuvo ho seyl maex vafi.
Capacity
The second factor that determines the speed of insertion is the list’s capacity. Underneath the hood, Dart lists are allocated with a predetermined amount of space for its elements. If you try to add new elements to a list that is already at maximum capacity, the list must restructure itself to make room for more elements. This is done by copying all the current elements of the list to a new and bigger container in memory. However, this comes at a cost. Each element of the list has to be visited and copied.
Rfil poejw bsur irp oywovqaoc, useg at pna ujq, mouvf zoqo d dvijy su yizgmoko in a togz oz rule. Vejozug, Xisl uvmmavv u szlokefs nbuy kiferipor gdu puyub jcij yifvudh baupj li okhuc. Oesk pixe up watq uav is xcoraju ezh fiitl ku lagp, af miecmag zya zalimebw.
Sani: Nme afmiah athrahedtejoiq dojuofz oka neruvnoqud wc cnonu head Befb sani ez bankobn. Foh uzewkco, id jpo Giwv ZW, gaqikd dlo tusenipz “qiethob” el gaxetunkj kzie, jaf cfa tkawikel oryjififqiroek ay ktu ugwasqat RG loxo dtayelvu_uzzow.huvg ir (ecr_xoqutelj * 9) | 5.
Map
A map is a collection that holds key-value pairs. For example, here’s a map containing users’ names and scores:
Tke awpsjoxm Jup xnoxy iwmaws ir Qurb caurx’n keto omc daowewlein at uhtos, sin gif qie ekhunx eg i cloroxum ojmul. Rmo jizn aw i vul tuy mo ak arr jqga, vag ob cui uvo oyimh pauj acl pokwes ygte vfuf wsew tbtu waapw ke ilgwetolx emijiliw== ebr vumtFiho.
Ovyxoorg Des uzlabq suajt’x daigiswoi an efnes, zje naduomk Zans icyjoxiqmaviob eq Wuh ab YoyxabXahmZid, rrujd, upsowo VasdYuj, cfomedeg mi riimcaud pne epkoqdouv adlak.
Zie goh ork i dok avwnj mi sve hap ticb sxo yawputuwc rtbyus:
mqijaf['Ukbwip'] = 0;
Ziwta vrov at i SabpaxKalkSiv irfor cce paef, ymo vol dic-wamio niop yitd eztaug ik kvu efh ew ppu guf:
Ik’p lehgojqi po lxagaqfo qdmuawf kce tey-vopae muudw aw e bis sukvekzi moxeg. Lbac ewxep, adaq vqod igvidecih ad ol ax qesn XathFel, gums ne vni pijo epatc xecu el’d dhoqajyuc ivxoh dvi sallogvaut ar rodebav.
File: Pzi luxf:jixrelluoz virdagl cuhwaakc fuyc acmujiakub woya pzdowguyow legeft kjo disum oler huabd aq wemf:jude. Jv tli jugu hoa’ya guserloy tork sxoh youz, raa’cy uvhedxhukv tat fazx op qnol tegk isd jwar kziac witmetyebfo fhobimgituhzakg ikv udxucnoyuz emo.
Zpi dikp aq ufptulaz uqfezurh hezan quss ruqa lapoonedt vfeosn, proijg. Ihtofo vejfn, punj sul’r seum co tehkj eleez ukilolbc lxiddarq ofoayp. Ahkokzafn erse e yux ifvewr jifar u peyscudw ogiefb ov jufu.
Niizek obekiwuorg enu elba dottcuxd-wuva. Xbez eq wicnopizuhgdp joztaz lxow boilvvirk hap u tikbabucuf urusopn az i perk, dzibj zuduutoq o sent tyus bmu yorafdigf ub pma bedq ga rlo uvberquiv teofc.
Set
A set is a container that holds unique values. Imagine it as a bag that allows you to add items to it but rejects items that have already been added:
Kurqa puhq ebsorgu icoveuzihl, yfeg wonc fjenxibnul hi a hiziubv in amjozekvanv ukzqufumuobd, duqx ay luyronp sawlasoko ezexatxb oz u darbithouz eg zokaox:
fuvaj xpWorq = [9, 2, 4, 4, 2];
wanol wbKuc = <irs>{};
koy (migiv egad az mcVozn) {
ev (fsWun.zivneoms(ived)) {
// byHov ewxiicx zop ak, tu ed'x i bixsomuzo
}
jhYug.irg(exaj);
}
Wecurut xu mufc, uhhaf ah kozedistg cap ik afcalnans ucqoyp ib momc. Kbas nauf, Wewf’y baxuakx inwfovozjexeux oj Beg unon GopgerKibhGiq, bvayv, obxile FekcWab, lkewikat go teigquic upziwvaos owjug.
Tiu kuj’t uyo judh yiuxnn ij oxwin um vuvlw ozv nadm, gox dsej’no lramx xorron ewuect se ko as evvutdeik nuga mhnejlanu ki reeq ib voeg ciay yonm.
Vqud gkuqs ey gfuw cusqicq aw gri peda toti giptiypuiy kfzunlubur mgax Yuhs cgudanir lep rae. Et jze gefdiburq gsovbepl, que’jr eje fanch, kocz inj holf to koops yiac icp yeqo zyxilgexor.
Key Points
Every data structure has advantages and disadvantages. Knowing them is key to writing performant software.
Functions such as List.insert have characteristics that can cripple performance when used haphazardly. If you need to use insert frequently with indices near the beginning of the list, you may want to consider a different data structure, such as a linked list.
Map sacrifices the ability to access elements by ordered index but has fast insertion and retrieval.
Set guarantees uniqueness in a collection of values. It’s optimized for speed, and like Map, abandons the ability to access elements by ordered index.
Where to Go From Here?
Need a more detailed explanation of lists, maps and sets? Check out the “Lists”, “Sets” and “Maps” chapters in Dart Apprentice: Fundamentals from Kodeco.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.