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
Exact analysis of insertion sort: Let us assume the following pseudocode to analyse the exact runtime complexity of insertion sort. T j   is the time taken to execute the s

There are ten stations on a railway line: Train travels in both directions (i.e. from 1 to 10 and then from 10 to 1).  Fare between each station is $2. A passenger input

Elaborate the symbols of abstract data type length(a)-returns the number of characters in symbol a. capitalize(a)-returns the symbol generated from a by making its first cha

The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

circular queue using c

Write down the algorithm of quick sort. An algorithm for quick sort: void quicksort ( int a[ ], int lower, int upper ) {  int i ;  if ( upper > lower ) {   i = split ( a,

Question a) Describe how the endogenous model is an improvement to the neo-classical model in explaining the long-run effect of investment on economic growth of a country.

Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion

According to this, key value is divided by any fitting number, generally a prime number, and the division of remainder is utilized as the address for the record. The choice of s

Define the term - Array A fixed length, ordered collection of values of same type stored in contiguous memory locations; collection may be ordered in several dimensions.