CSE 326 Data Structures Part Two Lists Henry Kautz Autumn Quarter 2002 Today Abstract versus Concrete Data Types List ADT Iterators Comparing implementations Sparse vectors Nested lists Sparse arrays Expressions Abstract 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 A1 A2 An 1 An length n 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 What other operations might be useful List ADT A1 A2 An 1 An length n 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 What other operations might be useful Kth integer item SetKth item integer Find item position Specialization Hierarchy List Property Sequence First pos Value pos item Next pos pos Length integer Insert item pos Delete pos Kth integer item SetKth item integer Find item position Stack Queue Vector Property LIFO Property FIFO Push item Pop item IsEmpty true false Enqueue item Dequeue item IsEmpty true false Property random access Kth int item SetKth item integer Implementation Hierarchy List Complexity Unspecified First pos Value pos item Next pos pos Length integer Insert item pos Delete pos Kth integer item SetKth item integer Find item position Linked List Array 1 for 1 for n for n for Specialization and Implementation Hierarchies List Stack Queue Vector Sorted Vector Linked List Concrete Data Types List Linked List Linked List using References nodeB value b nodeC value c list nodeB nodeB next nodeC b c What s an alternative implementation Concrete Data Types List b Linked List Linked List using References nodeB value b nodeC value c list nodeB nodeB next nodeC Linked List using Arrays 1 list 4 c b 0 2 2 c 3 4 5 Linked Lists in C L a b c struct node Object element struct node next Everything else is a pointer to a node typedef stuct node List typedef struct node Position Linked 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 List Abstract 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 Lists 1 7 3 4 5 6 Data F O A R N R T Next 3 8 6 4 1 10 5 First 2 How do we implement Delete position Insert element position 8 9 2 10 Free Cell Management 1 Data Next First 2 7 2 3 4 5 6 F O A R N 3 8 6 4 1 7 8 9 R 9 10 10 T 0 5 Free 1 When an item is removed from the list must reclaim the unused cell for later use Can use same array to manage a second list of unused cells Memory Management Keeping a free cell list is an example of a memory management strategy How is memory managed in C C Java Summary Complexity Linked list Kth int Find e Insert e pos Next pos InsertAnywhere e Array Sorted array 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 Method x a a b c b c Reverse ListNode x last tmp x head last null while x next null tmp x next x next last last x x tmp head x x Faster in practice Asymptotically faster Slow Reverse List reverse List x y new List for i 1 i x length i y Push x Kth i return y List ADT Polynomial ADT Possible linked list implementation Ai is the coefficient of the xi 1 term 5 2x 3x2 7 8x 3 x2 5 2 3 7 8 3 0 2 Problem 4 3x2001 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 …