Design a doubly linked list, Data Structure & Algorithms

Assignment Help:

Instructions :

  • You have to design a doubly linked list container.
  • The necessary classes and their declarations are given below
  • The main() function for testing the your design is also given below. The outputs form each of the output statements are provided in the text box for your comparison.
  • So complete the program by supplying your implementations of the member functions. Some are already implemented, use as it is.

// List . h

template

class List;

template

std::ostream& operator<< (std::ostream& os, const List& l);

template

class Link;

template

class ListIterator;

template

class List{

            friend std::ostream& operator<< (std::ostream& os, const List& l);

public:

typedef ListIterator Iterator;

List() : first_(0), last_(0) {};

List(const List & other);                    // copy constructor

~List();                                                  // destructor

List & operator = (const List & rhs);  // assignment operator

T& front() const;                                                // returns the front element

void push_front(const T& e);                  // adds from front

void pop_front();                                               // deletes from front

T& back() const;                                                // returns the last element

void push_back(const T& e);                 // adds from back

void pop_back();                                               // deletes the last element

void clear();                                                       // emptied by deleting all elements in it

bool empty() const;                                           // return true if list id empty

int size() const;                                      // returns the no. of elements

Iterator begin();

Iterator end();

Iterator insert(Iterator& itr, const T& val);

void insert(Iterator& itr, int n, const T& val);

void erase(Iterator& itr);

void erase(Iterator& start, Iterator& stop);

private:

void copy(const List & other);                      // private utility only, users use =

Node* first;                                     // points to first node

Node* last;                                      // points to last node

};

template

std::ostream& operator<< (std::ostream& os, const List& lst){

            os<<"f[ ";

            Link *pp = lst.first_; //cursor to lst

            while(pp != 0){

                        if(pp != lst.first_)os<<", ";

                                    os<< pp->elem_;

                        pp = pp->next_;

            }

            os<<" ]b"<

            return os;

}

 

template                                 //  implements the node of a doubly linked list

class Node{

                        friend class List;

                        friend class ListIterator;

                        friend std::ostream& operator<< (std::ostream& os, const List& l);

            private:

                        Node(const T& e) : elem_(e), next_(0), prev_(0){} // constrructor

                        T elem_;                        // element value

                        Node* next; //  pointer to next element in the list

                        Node* prev; //  pointer to the previous element in the list

};

template                                 // implements a iterator for the list class

class ListIterator{

                        friend class List;

                        typedef ListIterator Iterator;

            public:

                        ListIterator(List* list = 0, Link* ccNode = 0) : list_(list), cNode(ccNode) {}

                        T& operator *(){

                                    //  returns the element value of the node pointed by the iterator

                        }

                        bool operator == (Iterator rhs){

                                    // returns true  if this integrator and itertrator rhs are pointing to same node                                  }

                        bool operator != (Iterator rhs){

                                    // returns false if this integrator and itertrator rhs are pointing to same node        

                        }

                        Iterator& operator ++ (int){

                                    // advance the iterator to the right

                        }

                        Iterator operator ++ (){

                                    // postfix version

                        }

                        Iterator& operator -- (int){

                                    // backward the iterator by one position to the left

                        }

                        Iterator operator -- (){

                                    // postfix  version

                        };

            private:

                        List* list;                  // pointer to current doubly linked list object

                        Node* cNode;         // pointer to the node in the doubly linked list

};

// Main driver program

#include "List.h"

#include

#include

using namespace std;

 

typedef List ListD;

typedef List ListI;

typedef List ListS;

int main(){

            ListD    x;

            x.push_front(4.4); x.push_front(3.3); x.push_front(2.2); x.push_front(1.1);

 

            ListD y(x);

            ListD z = x;

            // output is shown in the text box 1

            cout<< "x.front = "<< x.front()<< endl;   

            cout<< "List x ="<

            cout<< "x.size() ="<< x.size()<< endl;

            while(!x.empty()){

                        cout<< x.front()<< endl;

                        x.pop_front();

            }

           cout<< "x.size() now = "<< x.size()<< endl;

            cout<< "List y ="<

            cout<< y<< endl;

            cout<< "List z ="<

            cout<< z<< endl;

            ListD v;

            v = y;

            v.pop_front();

                        // output is show in the text box  2

             cout<< "List v (v = y; v.pop_front();) ="<

            cout<< v<< endl;

            ListI li;

            li.push_front(3); li.push_front(2); li.push_front(1);

                        // output is show in the text box 3

            cout<< "List li via operator <<"<

            cout<< li<< endl;

            li.push_back(22);

            li.push_back(33);

                        // output is show in the text box 4

            cout<< "li.push_back(22), li.push_back(33)"<< endl;

            cout<< li<< endl;

            cout<< "back(), pop.back()"<< endl;

            while(!li.empty()){

                        cout<< li.back()<< endl;

                        li.pop_back();

            }

           ListS ls;

            ls.push_front("abcd");

            ls.push_front("cdefgh");

            ls.push_back("back");

            cout<< ls<< endl;          // output is show in the text box 5

            ListI c5;

            for(uint i = 0; i< 5; ++i){

                        c5.push_back(i);

                        cout<< "c5.push_back(i = "<< i<< "): "<< c5;  // output is show in the text box6

            }

           cout<< "using Iterator"<< endl;   // output is show in the text box 7                   

            ListI::Iterator itr = c5.begin();

            ListI::Iterator itrb = c5.begin();

            ListI::Iterator itre = c5.end();

            if(itr == itrb)       cout<< "itr == itrb"<< endl;

            else cout<< "itr != itrb"<< endl;

            if(itr != itrb)        cout<< "itr != itrb"<< endl;

            else cout<< "itr == itrb"<< endl;

            ListI::Iterator it;

            for(it = c5.begin(); it != c5.end(); ++it){

                        cout<< *it<< ' ';             // output is show in the text box 7

            }

            // output is show in the text box 8

            cout<< "ListI::Iterator itr2 = c5.begin(), ++, ++ "<< endl;

            cout<< "c5.insert(itr2, 5, 33) "<< endl;

            ListI::Iterator itr2 = c5.begin();

            itr2++; itr2++;

            c5.insert(itr2, 5, 33);

            cout<< c5;

            return 0;

}


Related Discussions:- Design a doubly linked list

Lists, In the earlier unit, we have discussed about the arrays. Arrays are ...

In the earlier unit, we have discussed about the arrays. Arrays are data structures of fixed size. Insertion & deletion involves reshuffling of array elements. Thus, arraymanipulat

Explain the different types of traversal on binary tree, Question 1 What i...

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Qu

Traversing a binary search tree, Binary Search Tree let three types of trav...

Binary Search Tree let three types of traversals by its nodes. They are: Pre Order Traversal In Order Traversal Post Order Traversal In Pre Order Traversal, we ca

Tower of hanoi, how do we use 4-discs stack to solve tower of hanoi problem...

how do we use 4-discs stack to solve tower of hanoi problem and write an algorithm to solve it?

Infix expression into the postfix expression, Q. Write down an algorithm to...

Q. Write down an algorithm to convert an infix expression into the postfix expression.     Ans. Algo rithm to convert infix expression to post fix expression is given as

Expression trees, What are the expression trees? Represent the below writte...

What are the expression trees? Represent the below written expression using a tree. Give a relevant comment on the result that you get when this tree is traversed in Preorder,

Applications of linear and binary search, The searching method are applicab...

The searching method are applicable to a number of places in current's world, may it be Internet, search engines, text pattern matching, on line enquiry, finding a record from data

Multilist file organisation, what is multilist length file organisation? ex...

what is multilist length file organisation? explain with an example

Define doubly linked list, A list item stores pointers and an element ...

A list item stores pointers and an element to predecessor and successor. We call a pointer to a list item a handle . This looks simple enough, but pointers are so powerful tha

Define about the inheritance hierarchy, Define about the inheritance hierar...

Define about the inheritance hierarchy Languages Eiffel and D provide constructs in language for invariants and pre- and post conditions which are compiled into the code and ar

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd