Design a doubly linked list, Data Structure & Algorithms

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;

}

Posted Date: 2/26/2013 3:14:46 AM | Location : United States







Related Discussions:- Design a doubly linked list, Assignment Help, Ask Question on Design a doubly linked list, Get Answer, Expert's Help, Design a doubly linked list Discussions

Write discussion on Design a doubly linked list
Your posts are moderated
Related Questions
Q. Establish the usage of linked lists for polynomial manipulation.                                       Ans. Usag e of Linked List for Polynomial Manipulation. Link

Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem

Merge sort is a sorting algorithm which uses the basic idea of divide and conquers. This algorithm initially divides the array into two halves, sorts them separately and then merge

Conversion of Forest into Tree A binary tree may be used to show an entire forest, since the next pointer in the root of a tree can be used to point to the next tree of the for

insertion and deletion in a tree

What are the different ways of representing a graph? The different ways of representing a graph is: Adjacency list representation: This representation of graph having of an

how to draw a 5 inch square on the screen using * symbol

Q. Which are the two standard ways of traversing a graph?  Explain them with an example of each.  Ans:   T he two ways of traversing a graph are written below

Define Dynamic Programming  Dynamic  programming  is  a  method  for  solving  problems  with  overlapping  problems.  Typically, these sub problems arise from a recurrence rel

Explain about the Abstract data type Abstract data type (ADT) A set of values (the carrier set) and operations on those values