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


class List;


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


class Link;


class ListIterator;


class List{

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


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);


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

Node* first;                                     // points to first node

Node* last;                                      // points to last node



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);


                        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;


                        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



                        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"



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;


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



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

            cout<< "List y ="<

            cout<< y<< endl;

            cout<< "List z ="<

            cout<< z<< endl;

            ListD v;

            v = y;


                        // 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;



                        // 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;


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



           ListS ls;




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

            ListI c5;

            for(uint i = 0; i< 5; ++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
What is a Spanning tree of a graph? A Spanning Tree is any tree having of vertices of graph tree and some edges of graph is known as a spanning tree.

The time required to delete a node x from a doubly linked list having n nodes is O (1)

I =PR/12 Numbers of years .Interest rate up to 1yrs . 5.50 up to 5yrs . 6.50 More than 5 yrs . 6.75 design an algorithm based on the above information

The controversy of RISC versus CISC never ends. Suppose that you represent an advocate for the RISC approach; write at least a one-page critic of the CISC approach showing its disa

Q. The reason bubble sort algorithm is inefficient is that it continues execution even after an array is sorted by performing unnecessary comparisons. Therefore, the number of comp

discuss the operating system under the following: MONOLITHIC SYSTEM,LAYER SYSTEM AND VIRTUAL MACHINES

lower triangular matrix and upper triangular matrix


Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text

AVL trees are applied into the given situations: There are few insertion & deletion operations Short search time is required Input data is sorted or nearly sorted