Unformatted text preview:

CSE 326: Data Structures Part Two: ListsTodayAbstract vs. Concrete Data TypesList ADTSlide 5Specialization HierarchyImplementation HierarchySpecialization and Implementation HierarchiesConcrete Data TypesSlide 10Linked Lists in CLinked Lists in Java – version 1Data HidingIteratorsAbstract IteratorsAbstract IteratorArray Implementation of Linked ListsFree Cell ManagementMemory ManagementSummary: ComplexityTo ADT or NOT to ADT?Destructive MethodSlow ReversePolynomial ADT4 + 3x2001Sparse Vector Data Structure: 4 + 3x2001Addition of Two Polynomials?Addition of Two PolynomialsSparse MatricesSlide 30Nested Polymorphic Lists“Universal” Data StructurePrograms As Lists-LispListsRead/Eval/Print LoopReading ExpressionsReadListEvaluating ExpressionsEvalListApplyThat’s It!Adding VariablesEval with VariablesControl FlowComing UpCSE 326: Data Structures Part Two: ListsHenry KautzAutumn Quarter 2002Today•Abstract versus Concrete Data Types•List ADT•Iterators•Comparing implementations•Sparse vectors•Nested lists–Sparse arrays–ExpressionsAbstract vs. Concrete Data Types•Abstract Data Type (ADT)–Mathematical description of an object and the set of operations on the object•List, Stack, Tree, Heap, Graph, …–One ADT may specialize another ADT–One ADT may implement another ADT•Concrete Data Type–Implementation of an ADT using some set of primitive data types and operations of known complexity•Primitives: integers, arrays, pointers or references–Object-oriented programming languages (Java, C++) let you explicitly define new concrete data types that correspond to ADT’s.List ADT•Mathematical description: a sequence of items–Ai precedes Ai+1 for 1  i < n•Operations–First() = position–Value(position) = item–Next(position) = position–Length() = integer–Insert(item,position)–Delete(position)( A1 A2 … An-1 An )length = nWhat other operations might be useful?List ADT•Mathematical description: a sequence of items–Ai precedes Ai+1 for 1  i < n•Operations–First() = position–Value(position) = item–Next(position) = position–Length() = integer–Insert(item,position)–Delete(position)( A1 A2 … An-1 An )length = nWhat other operations might be useful?Kth(integer)=itemSetKth(item,integer)Find(item)=positionSpecialization HierarchyListProperty: SequenceFirst()=pos Value(pos)=item Kth(integer)=itemNext(pos)=pos Length()=integer SetKth(item,integer)Insert(item,pos) Delete(pos) Find(item)=positionStackProperty: LIFOPush(item)Pop()=itemIsEmpty()=true/falseQueueProperty: FIFOEnqueue(item)Dequeue()=itemIsEmpty()=true/falseVectorProperty: random accessKth(int) = itemSetKth(item,integer)Implementation HierarchyListComplexity: UnspecifiedFirst()=pos Value(pos)=item Kth(integer)=itemNext(pos)=pos Length()=integer SetKth(item,integer)Insert(item,pos) Delete(pos) Find(item)=positionLinked List(1) for:(n) for:Array(1) for:(n) for:Specialization and Implementation HierarchiesListStack Queue VectorLinked ListSorted VectorConcrete Data TypesListLinked ListLinked List using ReferencesWhat’s an alternative implementation?nodeB.value = “b”;nodeC.value = “c”;list = nodeB;nodeB.next = nodeCb cConcrete Data TypesListLinked ListLinked List using ReferencesnodeB.value = “b”;nodeC.value = “c”;list = nodeB;nodeB.next = nodeCb cLinked List using Arrays“c” “b”0 2list = 4;1 2 3 4 5Linked Lists in Cstruct node{Object element;struct node * next; }Everything else is a pointer to a node!typedef stuct node * List;typedef struct node * Position;a b cLLinked Lists in Java – version 1•References to objects are implicit pointers class ListNode{Object element;ListNode next; } class List{Listnode head;Listnode find(Object item) {Listnode n = head;while (n != null) {if (n.element == item)return n; }return null; }Data Hiding•Good programming style hides internal details of an object from the rest of the program–Guarantees that data structure always works as expected – cannot easily be corrupted•Here, must make details of ListNode and List public –Type returned by find–For iterating through a list: ListNode n; for (n = mylist.head; n!= null; n = n.next){v = n.element;do something on each v }Iterators•Introduce a new public class to explicitly represent a position in a list public class LinkedListItr {ListNode current;public Object retrieve() {return current.element; }public void advance() {current = current.next; }•Then: LinkedListItr i; for (i = mylist.first(); !i.pastEnd(); i.advance){do something on each v.retrieve() }Abstract Iterators•Iterators can also be defined for an array implementation of lists:public class ArrayListItr {Object [] data;integer current;public Object retrieve() {return data[current]; }public void advance() {current = current+1; }•We can create an abstract iterator that works for both linked list and array implements of ListAbstract Iterator abstract class ListItr {abstract Object retrieve();abstract void advance();… } class LinkedListItr extends ListItr { … } class ArrayListItr extends ListItr { … }•Why do this?Array Implementation of Linked ListsHow do we implementDelete(position) ?Insert(element, position)?F O A R N R T3 8 6 4 -1 10 5DataNext1 7 92 3 4 5 6 8 10First = 2Free Cell ManagementWhen an item is removed from the list, must “reclaim” the unused cell for later useCan use same array to manage a second list of unused cellsF O A R N R T7 9 03 8 6 4 -1 10 5DataNext1 7 92 3 4 5 6 8 10First = 2 Free = 1Memory Management•Keeping a free cell list is an example of a memory management strategy•How is memory managed in C?•C++?•Java?Summary: ComplexityLinked list Array SortedarrayKth(int)Find(e)Insert(e,pos)Next(pos)InsertAnywhere(e)To ADT or NOT to ADT?•Issue: when to bypass / expand List ADT?•Using general list (stack) operations: List reverse(List x) {y = new List;while (! x.isEmpty()) y.Push( x.Pop() )return y; }Disadvantages?Destructive MethodReverse() { ListNode x, last, tmp;x = head; last = null;while (x.next != null){ tmp = x.next; x.next = last; last = x; x = tmp;}head = x; }a b cxab cxFaster in practice?Asymptotically faster?Slow ReverseList reverse(List x) {y = new List;for (i=1; i<=x.length(); i++){y.Push( x.Kth(i) )}return y; }Polynomial ADTPossible linked list implementation: Ai is the coefficient of the xi-1 term:5 + 2x + 3x2( 5 2 3 )7 + 8x( 7 8 )3 + x2( 3 0 2 )Problem?List ADT4 +


View Full Document

UW CSE 326 - Part Two - Lists

Download Part Two - Lists
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Part Two - Lists and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Part Two - Lists 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?