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