Abstractions, Collections & Data StructuresAbstractions and CollectionsCollections and Data StructuresCollectionLinear Data StructuresSlide 6Operations on listsAccessing elementsRestricted abstractionsQueueStackDouble ended queueGeneral list operationsList implementationsArray implementationsLinked implementationAbstractions,Collections &Data StructuresNelson Padua-PerezBill PughDepartment of Computer ScienceUniversity of Maryland, College ParkAbstractions and CollectionsPrograms represent and manipulate abstractions, 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 can perform on themCollections and Data StructuresA collection can typically implemented using several different data structuresa data structure is a way of implementing an abstraction and operations on itDifferent implementations or data structures for an abstraction will provide different efficiencies for 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 elements Each element has unique predecessorEach element has unique successorFor any two distinct elements x and y, either x comes 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 the listOperations 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 to manipulatefirst/headlast/tailby position (e.g, the 5th element)also a bad movieby walking/iterating through the next, and talking about relative positionthe next elementthe previous elementRestricted abstractionsRestricting the operations an abstraction supports can be a good thing efficiently supporting only a few operations efficiently is easierif a limited abstraction suits your needs, easily to reason about the limited abstraction than a more general 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 elements only at one endwhether the top of the stack is the front or beginning of the list doesn’t really matterExamples:keep track of pending calculations in a calculatorparsingDouble ended queueList/queue where you can add or remove at either endGeneral list operationsget/set/insert/remove value at a particular indexget/set/insert/remove value at head/tailiterate through list, and get/set/insert/remove values as you gouse a java.util.ListIteratorList implementationsTwo basic implementation techniques for any kind of liststore elements in an arraystore each element in a separate object, and link them together (a linked list representation)Array implementationsAdvantages:Space efficient (just space to hold reference to each element)Can efficiently access elements at any positionDisadvantagesHas to grow/shrink in spurtsCan’t efficiently insert/remove elements in the middleinserting/removing elements at both ends is trickyLinked implementationAdvantagescan efficiently insert/remove elements anywhereDisadvantagescan’t efficiently access elements at arbitrary positionsspace overhead (one or two additional pointers per
View Full Document
Unlocking...