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

State warnock algorithm, Warnock's Algorithm An interesting approach to...

Warnock's Algorithm An interesting approach to the hidden-surface problem was presented by Warnock. His method does not try to decide exactly what is happening in the scene but

Linked lists - implementation, The Linked list is a chain of structures whe...

The Linked list is a chain of structures wherein each structure contains data in addition to pointer, which stores the address (link) of the next logical structure in the list.

Maximum degree of any vertex in a simple graph, The maximum degree of any v...

The maximum degree of any vertex in a simple graph with n vertices is (n-1) is the maximum degree of the vertex in a simple graph.

Construction of a binary tree , Q. Construct a binary tree whose nodes in i...

Q. Construct a binary tree whose nodes in inorder and preorder are written as follows: Inorder : 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50 Preorder: 20, 15, 10

Non-recursive algorithm to traverse a tree in preorder, Write the non-recur...

Write the non-recursive algorithm to traverse a tree in preorder.    The Non- Recursive algorithm for preorder traversal is as follows: Initially  push NULL onto stack and

Java code and algorythem, Suppose that you want to develop a program that a...

Suppose that you want to develop a program that accepts a postfix expression and asks values for variables in the expression. Then you need to calculate the answer for the expressi

Find a minimum cost spanning arborescence rooted, Find a minimum cost spann...

Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class. Please show your work, and also give a final diagram wh

Darw a flowchart that inputs country someone is visiting, Regis lives in Br...

Regis lives in Brazil and frequently travels to USA, Japan and Europe. He wants to be able to convert Brazilian Reais into US dollars, European euros and Japanese yen. Conversion f

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