Abstractions,Collections &Data StructuresNelson Padua-PerezBill PughDepartment of Computer ScienceUniversity of Maryland, College ParkAbstractions and CollectionsPrograms represent and manipulateabstractions, or chunks of informationa Sudoku boardthe moves legal for a particular squarea media playera deck of cardsThe most universal of these is a collectionlots of different kinds of collectionslist, set, ordered set, bag, mapFor each kind of collection, operations you canperform on themCollections and Data StructuresA collection can typically implemented usingseveral different data structuresa data structure is a way of implementing anabstraction and operations on itDifferent implementations or data structures foran abstraction will provide different efficienciesfor different operationswe will see more of this in a momentCollectionThe base interface of most collectionsOperations supported:add elementsremove elementsdetermine size of collection (# of elements)iterate through elementsLinear Data StructuresTotal order over elementsEach element has unique predecessorEach element has unique successorFor any two distinct elements x and y, either xcomes before y or y comes before xLinear Data StructuresCore operationsFind first element (head)Find next element (successor)Find last element (tail)TerminologyHead ⇒ no predecessorTail ⇒ no successorDuplicates allowedthe same value can appear at different places in thelistOperations on listsadd an elementwhere?at beginning/frontat rear/endafter a particular elementremove an elementremove first elementremove last elementremove the String value “Happy”what happens if “Happy” occurs more than onceAccessing elementsHow do you name an element you want tomanipulatefirst/headlast/tailby position (e.g, the 5th element)also a bad movieby walking/iterating through the next, and talkingabout relative positionthe next elementthe previous elementRestricted abstractionsRestricting the operations an abstractionsupports can be a good thing efficiently supporting only a few operationsefficiently is easierif a limited abstraction suits your needs, easily toreason about the limited abstraction than a moregeneral oneRestricted list abstractions:queue (aka FIFO queue)stack (aka LIFO queue)dequeue (aka double ended queue)QueueCan add items to the end of the queueremove them from the front of the queueFirst-in, first-out order (FIFO)Represented as a listtotal order over elementsBut no access to middle of the listExample use:songs to be playedjobs to be printedcustomers to be servedStackCan add an item to the top of the stackcan remove the item on top of the stackNo access to elements other than the topJust a list where you can add/remove elementsonly at one endwhether the top of the stack is the front or beginningof the list doesn’t really matterExamples:keep track of pending calculations in a calculatorparsingDouble ended queueList/queue where you can add or remove ateither endGeneral list operationsget/set/insert/remove value at a particular indexget/set/insert/remove value at head/tailiterate through list, and get/set/insert/removevalues as you gouse a java.util.ListIteratorList implementationsTwo basic implementation techniques for anykind of liststore elements in an arraystore each element in a separate object, and linkthem together (a linked list representation)Array implementationsAdvantages:Space efficient (just space to hold reference to eachelement)Can efficiently access elements at any positionDisadvantagesHas to grow/shrink in spurtsCan’t efficiently insert/remove elements in themiddleinserting/removing elements at both ends is trickyLinked implementationAdvantagescan efficiently insert/remove elements anywhereDisadvantagescan’t efficiently access elements at arbitrarypositionsspace overhead (one or two additional pointers
View Full Document