Lists. Stacks and Queues
Lists, Stacks and Queues
More com plete listADT List(i / const List(const List& list)i copy constructor List( destructor ist& operator=(const List& list)i // assignment operator // plus other overloaded operators void add (double x)i double head(consti // get the head element bool search(double x search for a given x void insert(double x) / insert x in a sorted list void delete(double x / delete x in a sorted list void addEnd (double x)i add to the end d deleteD(; delete the end and get the end element double end( / get the element at the end void display ()consti //output it length()consti / count the number of elements
2 struct Node{ double data; Node* next; }; class List { public: List(); // constructor List(const List& list); // copy constructor ~List(); // destructor List& operator=(const List& list); // assignment operator // plus other overloaded operators bool empty() const; // boolean function void add(double x); // add to the head void delete(); // delete the head and get the head element double head() const; // get the head element bool search(double x); // search for a given x void insert(double x); // insert x in a sorted list void delete(double x); // delete x in a sorted list void addEnd(double x); // add to the end void deleteEnd(); // delete the end and get the end element double end(); // get the element at the end void display() const; // output int length() const; // count the number of elements private: Node* head; }; More complete list ADT
list ADT (a general list) class list ublic t() List(const List& list) copy constructor LIston // destructor bool empty() consti double head( const // get the head element void add(double x)i // add to the head void delete(i // delete the head element void display() consti // output private: Or to define one function Double delete 0; Which deletes and returns the head element
3 class List { public: List(); // constructor List(const List& list); // copy constructor ~List(); // destructor bool empty() const; // boolean function double head() const; // get the head element void add(double x); // add to the head void delete(); // delete the head element void display() const; // output private: … }; list ADT (a general list) Or to define one function: Double delete(); Which deletes and returns the head element
list ADT (a sorted list lass list public Liston // constructor List(const List& list)i // copy constructor sto // destructor bool empty ()consti // boolean function double headon consti // get the first element void insert(double x) // insert x in a sorted list void delete (double x sorted list void display()col //output bool search(double x) // search for a given x
4 class List { public: List(); // constructor List(const List& list); // copy constructor ~List(); // destructor bool empty() const; // boolean function double head(); const; // get the first element void insert(double x); // insert x in a sorted list void delete(double x); // delete x in a sorted list void display() const; // output bool search(double x); // search for a given x private: … }; list ADT (a sorted list)
Implementation and efficiency Implementation Static array DynamIc array Linked lists e with and without dummy head tricks Efficiency Insertion> construction, composition Deletion> destruction, decomposition Search application, usage
5 Implementation Static array Dynamic array Linked lists with and without ‘dummy head’ tricks Efficiency Insertion → construction, composition Deletion → destruction, decomposition Search → application, usage Implementation and Efficiency
Efficiency: Algorithm Analysis Roughly 'counting the number of operations, assuming all basis operations are of the same unit one
6 Roughly ‘counting’ the number of operations, assuming all basis operations are of the same, unit one. Efficiency: Algorithm Analysis
A Few Simple rules Loops at most the running time of the statements inside the for-loop (including tests ) times the number of iterations O(N) Nested loops for(i=0; i<n; i ++ for (=0; j<n;j ++) k++; the running time of the statement multiplied by the product of the sizes of all the for-loops O(N2)
7 A Few Simple Rules Loops at most the running time of the statements inside the for-loop (including tests) times the number of iterations. O(N) Nested loops the running time of the statement multiplied by the product of the sizes of all the for-loops. O(N2 )
Consecutive statements for(=0;i<n;+) These just add a[i=0; O(N)+O(N2)=O(N2) for (i=0:; k<n:; ++ for (=0; j<n j ++ a+=a]++ Conditional: If s1 else s2 never more than the running time of the test plus the larger of the running times of S1 and S2 O(1)
8 Consecutive statements These just add O(N) + O(N2 ) = O(N2 ) Conditional: If S1 else S2 never more than the running time of the test plus the larger of the running times of S1 and S2. O(1)
Our first example: search of an ordered array Linear search and binary search Upper bound, lower bound and tight bound
9 Our first example: search of an ordered array Linear search and binary search Upper bound, lower bound and tight bound
10 Linear search: // Given an array of 'size, in increasing order, find int linearsearch(int* a[l, int size int x)i int low=0, high=size-li for (int i=0; i<size; i++) O(N) if (a[i]==x return i t
10 O(N) // Given an array of ‘size’ in increasing order, find ‘x’ int linearsearch(int* a[], int size,int x) { int low=0, high=size-1; for (int i=0; i<size;i++) if (a[i]==x) return i; return -1; } Linear search: