Linear Data StructuresSlide 2Linked ListReference-based ImplementationArray vs. Reference-based Linked ListLinked List – Insert (After Cursor)Slide 7Linked List – Delete (Cursor)Slide 9Doubly Linked ListSlide 11Node Structures for Linked ListsDoubly Linked List – InsertionCircular Linked ListsCircular Linked Lists – ExamplesStackStack ImplementationsStack ApplicationsQueueQueue ImplementationsQueue – ArrayQueue – Circular ArraySlide 23Slide 24Slide 25Linear Data StructuresNelson Padua-PerezChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkLinear Data StructuresListsLinked listDoubly linked listCircular listStack QueueCircular queueLinked ListPropertiesElements in linked list are orderedElement has successorState of ListHeadTailCursor (current position)HeadTailCursorReference-based ImplementationNodes contain references to other nodesExampleIssuesEasy to find succeeding elementsStart from head of list for preceding elementsArray vs. Reference-based Linked ListReference-based linked listInsertion / deletion = O(1)Indexing = O(n)Easy to dynamically increase size of listArrayInsertion / deletion = O(n)Indexing = O(1)Compact, uses less spaceEasy to copy, mergeBetter cache localityLinked 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 ListPropertiesElements in linked list are orderedElement has predecessor & successorState of ListHeadTailCursor (current position)HeadTailCursorDoubly Linked ListExampleIssuesEasy to find preceding / succeeding elementsExtra work to maintain links (for insert / delete)More storage per nodeNode Structures for Linked ListsLinked listClass Node {Object data;Node next;}Doubly linked listClass Node {Object data;Node next;Node previous;}Doubly Linked List – InsertionExampleMust update references in both predecessor and successor nodesCircular Linked ListsLast element links to first elementPropertiesCan reach entire list from any nodeNeed special test for end of listRepresentBuffersNaturally circular dataHeadTailCircular Linked Lists – ExamplesCircular linked listCircular doubly linked listStackPropertiesElements removed in opposite order of insertionLast-in, First-out (LIFO)Must track position of Top (last element added)Stack operationsPush = add element (to top)Pop = remove element (from top)Stack ImplementationsLinked listAdd / remove from head of listArrayIncrement / decrement Top pointer after push / popX Y Z … TopStack ApplicationsRun-time procedure informationArithmetic computationsPostfix notationSimplified instruction setJava bytecodeQueuePropertiesElements removed in order of insertionFirst-in, First-out (FIFO)Must track Front (first in) and Back (last in)Queue operationsEnqueue = add element (to back)Dequeue = remove element (from front)Queue 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...