Abstract Data TypesAbstract Data Types1111Cpt S 223. School of EECS, WSUTopics Abstract Data Types (ADTs)Some basic ADTs: Lists Stacks Queues222Cpt S 223. School of EECS, WSUPrimitive Data Type vs. Abstract Data TypesPrimitive DT:ammerADT:programmerprograInterface (API)e.g., int, floatImplementation(methods)Dt33DataCpt S 223. School of EECS, WSUAbstract Data Types (ADTs) ADT is a set of objects together with a set of operations.“Abstract”in that implementation of operations not specifiedAbstract in that implementation of operations not specified in ADT definition E.g., ListInsert, delete, search, sortInsert, delete, search, sort C++ classes are perfect for ADTs Can change ADT implementation details without breaking code using ADT444Cpt S 223. School of EECS, WSUSpecifications of basic ADTsSpecifications of basic ADTsList, Stack, QueueCpt S 223. School of EECS, WSU 5The List ADT List of size N: A0, A1, …, AN-1Each element Ahas a unique position kEach element Akhas a unique position k in the listElements can be arbitrarily complexElements can be arbitrarily complex Operations insert(X,k), remove(k), find(X), findKth(k), printList()66Cpt S 223. School of EECS, WSUStack ADT Stack = a list where insert and remove take place only at the “top”at the “top” Operations Push (insert) element on top of us ( se ) e e e o op ostack Pop (remove) element from top of stackp Top: return element at top of stackLIFO (Last In First Out)7LIFO (Last In First Out)7Cpt S 223. School of EECS, WSUQueue ADT Queue = a list where insert takes place at the back, but remove takes place at the front Operations Enqueue (insert) element at the back of the queue Dequeue (remove and return) element from the front of the queueFIFO (First In First Out)FIFO (First In First Out)5726328Enque hereDequeue here8front backq8Cpt S 223. School of EECS, WSUIl ttifbiImplementation for basic ADTsADTsCpt S 223. School of EECS, WSU 9List ADT using ArraysA0A1A2A3… Operations• Read as “order N” (thttii insert(X,k) : O(N) remove(k) : O(N)(means that runtime is proportional to N) find(X) : O(N) findKth(k) : O(1)• Read as “order 1” (means that runtime is a 1010()() printList() : O(N)(constant – i.e., not dependent on N)Cpt S 223. School of EECS, WSUList ADT using Linked Lists Elements not stored in contiguous memorymemory Nodes in list consist of data element and next pointerand next pointernode1111datanextnullpointerCpt S 223. School of EECS, WSULinked Lists OperationsInsert(X A)–O(1)Insert(X,A) O(1)  Remove(A) – O(1) 1212Cpt S 223. School of EECS, WSULinked Lists Operationsfind(X)–O(N)find(X) O(N) findKth(k) – O(N)printList()–O(N)printList() O(N)1313Cpt S 223. School of EECS, WSUDoubly-Linked List Singly-linked listinsert(X A) and remove(X) require pointerinsert(X,A) and remove(X) require pointer to node just before XDoubly-linked listDoublylinked list Also keep pointer to previous node1414prevnextCpt S 223. School of EECS, WSUDoubly-Linked List Insert(X,A)newA = new Node(A);newA->prev = X->prev;newA->next = X;()X->prev->next = newA;X->prev = newA; Remove(X)X->prev->next = X->next;X->next->prev = X->prev; Problems with operations at ends of list1515Cpt S 223. School of EECS, WSUSentinel Nodes Dummy head and tail nodes to avoid special cases at ends of listDoublylinked list with sentinel nodesDoubly-linked list with sentinel nodesEtdblli k d li t ith ti l dEmpty doubly-linked list with sentinel nodes1616Cpt S 223. School of EECS, WSUC++ Standard Template Library (STL) Implementation of common data structuresstructures List, stack, queue, …Generally calledcontainersGenerally called containers WWW references for STLwww sgi com/tech/stl/www.sgi.com/tech/stl/ http://www.cplusplus.com/reference/stl/f/tlhtl17 www.cppreference.com/cppstl.html17Cpt S 223. School of EECS, WSUImplementing Lists using STL vector<Object> Array-based implementationfi dKthO(1)findKth–O(1) insert and remove –O(N) Unless change at end of vector list<Object> Doubly-linked list with sentinel nodesfindKth–O(N)findKthO(N) insert and remove –O(1) If position of change is knownh i O( ) f h18 Both require O(N) for search18Cpt S 223. School of EECS, WSUContainer Methods int size() constReturn number of elements in containerReturn number of elements in container void clear()Remove all elements from containerRemove all elements from container bool empty() Return true is container has no elements, otherwise returns false1919Cpt S 223. School of EECS, WSUVector and List Methods void push_back (const Object & x) Add x to end of list void pop_back () Remove object at end of list const Object & back () const Return object at end of list const Object & front () const Return object at front of list2020Cpt S 223. School of EECS, WSUList-only Methods void push_front (const Object & x) Add x to front of list void pop_front () Remove object at front of list2121Cpt S 223. School of EECS, WSUVector-only Methods Object & operator[] (int idx) Return object at index idx in vector with no bounds-checking Object & at (int idx) Return object at index idx in vector with bounds-checkingint capacity () constint capacity () const Return internal capacity of vectorvoid reserve (int newCapacity)22void reserve (int newCapacity) Set new capacity for vector (avoid expansion)22Cpt S 223. School of EECS, WSUIterators Represents position in containerGetting an iteratorGetting an iterator iterator begin ()Return appropriate iterator representing firstReturn appropriate iterator representing first item in container iterator end ()() Return appropriate iterator representing end marker in container23 Position afterlast item in container23Cpt S 223. School of EECS, WSUIterator Methods itr++ and ++itr Advance iterator itr to next location *itr Return reference to object stored at iterator itr’s locationitr1==itr2itr1 itr2 Return true if itr1 and itr2 refer to same location; otherwise return falseit1! it2itr1 != itr2 Return true if itr1 and itr2 refer to different locations; otherwise return false2424Cpt S 223. School of EECS, WSUExample: printListtemplate <typename Container>void printList