CMSC 132: Object-Oriented Programming IILinear Data StructuresDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewLinear data structuresGeneral propertiesImplementationsArrayLinked listRestricted abstractionsStackQueueLinear Data Structures1-to-1 relationship between elements Each element has unique predecessor & successorResults in total ordering over elements For any two distinct elements x and y, either x comes before y or y comes before xLinear Data StructuresTerminologyHead (first element in list) ⇒⇒⇒⇒no predecessorTail (last element in list) ⇒⇒⇒⇒no successorOperationsAdd element Remove elementFind elementAdd & Remove ElementsAdd an elementWhere?At head (front) of listAt tail (end) of listAfter a particular elementRemove an elementRemove first elementRemove last elementRemove a particular element (e.g., String “Happy”)What if “Happy” occurs more than once in list?Accessing ElementsHow do you find an element?At head (front) of listAt tail (end) of listBy position Example: the 5th elementBy iterating through the list, and using relative positionNext element (successor)Previous element (predecessor)List ImplementationsTwo basic implementation techniques for listsStore elements in an arrayStore as a linked listPlace each element in a separate object (node)Node contains reference to other node(s)Link nodes togetherLinked ListPropertiesElements in linked list are orderedElement has successorState of ListHeadTailCursor (current position)HeadTailCursorArray ImplementationsAdvantagesCan efficiently access element at any positionEfficient use of spaceSpace to hold reference to each elementDisadvantagesExpensive to grow / shrink arrayCan amortize cost (grow / shrink in spurts)Expensive to insert / remove elements in middleTricky to insert / remove elements at both endsLinked ImplementationAdvantagesCan efficiently insert / remove elements anywhereDisadvantagesCannot efficiently access element at any positionNeed to traverse list to find elementLess efficient use of space1-2 additional references per elementEfficiency of OperationsArrayInsertion / deletion = O(n)Indexing = O(1)Linked listInsertion / deletion = O(1)Indexing = O(n)Linked List – Insert (After Cursor)1.Original list & new element temp2.Modify temp.next →→→→ cursor.nextLinked List – Insert (After Cursor)3.Modify cursor.next →→→→ temp4.Modify cursor →→→→ tempLinked List – Delete (Cursor)1.Find before such that before.next = cursor2.Modify before.next →→→→ cursor.nextLinked List – Delete (Cursor)3.Delete cursor4.Modify cursor →→→→ before.nextDoubly Linked ListLinked list whereElement has predecessor & successorIssuesEasy to find preceding / succeeding elementsExtra work to maintain links (for insert / delete)More storage per nodeDoubly Linked List – InsertionExampleMust update references in both predecessor and successor nodesNode Structures for Linked ListsLinked listClass Node {Object data;Node next;}Doubly linked listClass Node {Object data;Node next;Node previous;}Restricted AbstractionsRestricting the operations an abstraction supports can be a good thingEfficiently supporting only a few operations efficiently is easierIf limited abstraction is sufficient, easier to reason about limited abstraction than a more general oneRestricted list abstractionsStack (aka LIFO queue)Queue (aka FIFO queue)Dequeue (aka double ended queue)StackStack operationsPush = add element (to top)Pop = remove element (from top)ExampleStackPropertiesElements removed in opposite order of insertionLast-in, First-out (LIFO)A restricted list whereAccess only to elements at one endCan add / remove elements only at one endStack ApplicationsRun-time procedure informationArithmetic computationsPostfix notationSimplified instruction setJava bytecodeStack ImplementationsLinked listAdd / remove from head of listArrayIncrement / decrement Top pointer after push / popX Y Z …TopQueueQueue operationsEnqueue = add element (to back)Dequeue = remove element (from front)ExampleQueuePropertiesElements removed in order of insertionFirst-in, First-out (FIFO)A restricted list whereAccess only to elements at beginning / end of listAdd elements only to beginning of listRemove elements only from end of listQueue ApplicationsExamplesSongs to be playedJobs to be printedCustomers to be servedCitizens to cast votesSouth Africa, 2004Queue ImplementationsLinked listAdd to tail (back) of listRemove from head (front) of listArrayCircular arrayQueue – ArrayStore queue as elements in arrayProblemQueue contents move (“inchworm effect”)As result, can not add to back of queue, even though queue is not fullQueue – Circular ArrayCircular array (ring)q[ 0 ] follows q[ MAX – 1 ]Index using q[ i % MAX ]ProblemDetecting difference between empty and nonempty queueQueue – Circular ArrayApproach 1Keep Front at first inKeep Back at last inProblemEmpty queue identical to queue with 1 elementQueue – Circular ArrayApproach 2Keep Front at first inKeep Back at last in – 1ProblemEmpty queue identical to full queueQueue – Circular ArrayInherent problem for queue of size NOnly N possible (Front – Back) pointer locationsN+1 possible queue configurations Queue with 0, 1, … N elementsSolutionsMaintain additional state informationUse state to recognize empty / full queueExamplesRecord SizeRecord QueueEmpty flagLeave empty element in queueStore marker in
View Full Document
Unlocking...