Thread: Doubly linked list... nitpick and test if possible

  1. #1
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657

    Doubly linked list... nitpick and test if possible

    In the following code..
    Any template or design 'gotchas' ?
    Suggest
    1.More concise versions of the member functions.
    2.Boundary conditions I may have missed.
    3.A way to provide a better interface. I thought about making everything in node private and make list a friend... but it makes the interface more convoluted.
    4.Anything else I have messed up...or could be done better.

    Code:
    namespace mm
    {  
    template<typename T>    
    class node
    {
    public:
        T val;
        node<T>* next;
        node<T>* prev;
        
        node<T>()
        {
            next = 0;
            prev = 0;
        }
        node<T>(T n, node<T>* nxt=new node<T>(), node<T>* prv=new node<T>())
        {
            val = n;
            next = nxt;
            prev = prv;
        }
        bool null_p()
        {
            return (next==0)||(prev==0);
        }       
    };
    
    
    template<typename T> void link(node<T>* x, node<T>* y)
    {
        x->next = y;
        y->prev = x;
    }
    template<typename T>
    class list
    {    
        int size_val;
        node<T>* ini;
        node<T>* fin;
    public:
        node<T>* begin(){return ini;};
        node<T>* end(){return fin->next;};
           
        int size(){return size_val;}
        list()
        {
            ini =new node<T>();
            fin =new node<T>(); 
            size_val = 0;
        }
        void append(T n)
        {
            size_val++;
            node<T>* newbie = new node<T>(n);
            if(ini->null_p()&&fin->null_p())
            {
                link(ini,newbie);
                link(newbie,fin);
                ini=fin = newbie;
            }
            else
            {
                link(newbie,fin->next);
                link(fin,newbie);
                fin = newbie;            
            }
        }
        void insert(T n, node<T>* ref)// Insert a node containing n AFTER ref
        {
            size_val++;
            node<T>* newbie = new node<T>(n);
            link(newbie,ref->next);
            link(ref,newbie);
            if(ref==fin)fin = fin->next;
        }
        void remove(node<T>* ref)
        {
            if(size_val==0)return;
            if(size_val==1)
            {
                ini = ini->prev;
                fin = fin->next;
                ini->next = 0;
                fin->prev = 0;
                delete ref;            
            }
            else
            {
                link(ref->prev,ref->next);
                if(ref == ini)ini=ref->next;
                if(ref == fin)fin=ref->prev;
                delete ref;            
            }
            size_val--;
        }
        
        void debug_print()
        {
            if(size_val!=0)
                for(node<T>* x = begin();x!=end();x = x->next )
                    std::cout<<"< "<<x->val<<'\t'<<!x->null_p()<<" >\n";
            std::cout<<"Total- "<< size_val<<std::endl;
        }
    };
    }
    Last edited by manasij7479; 10-09-2011 at 01:22 AM.

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Code:
    node<T>(T n, node<T>* nxt=new node<T>(), node<T>* prv=new node<T>())
    This is not exception safe and will leak memory if the second allocation fails; this is partially what smart pointers solve.

    Code:
            ini =new node<T>();
            fin =new node<T>();
    This is the same as the bit above.

    Code:
    size_val++;
    This should be done after allocation and copy construction.

    Code:
    node<T>* newbie = new node<T>(n);
    This compounds the above issue by silently often allocating memory not needed.

    Code:
                link(ini,newbie);
                link(newbie,fin);
    This always leaks memory and fails to deconstruct multiple objects.

    Code:
                link(newbie,fin->next);
                link(fin,newbie);
    That has the same problem.

    Basically, your default parameters that allocate memory and construct an object are breaking things every time you try to use it.

    Soma

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    I noticed that I don't really use the default parameters anywhere... So I removed them for now...(would find better solutions later).

    How much of the leak issue remains valid.. after getting rid of those ?

    Quote Originally Posted by phantomotap
    Code:
    ini =new node<T>();
        fin =new node<T>();
    This is the same as the bit above
    They are done only once for a list... and are necessary for denoting its ends.

    Code:
    link(ini,newbie);
    link(newbie,fin);

    This always leaks memory and fails to deconstruct multiple objects.
    Why ?
    Last edited by manasij7479; 10-09-2011 at 02:03 AM.

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    You have lots of problems and lots of leaks.
    First off, you should make up your mind: are you going to use "sentinels" to act as head and tail of the list, or are you simply going to use special cases to handle operations at the end and head of the list?
    Using "sentinels" makes the code cleaner since you can ignore the special cases entirely, but eats up more memory.

    Right now, you are leaking the head and tail.
    Also, you should be using nullptr instead of 0.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. doubly linked list
    By bazzano in forum C Programming
    Replies: 5
    Last Post: 04-26-2007, 03:41 AM
  2. doubly linked list
    By bahareh in forum C++ Programming
    Replies: 7
    Last Post: 03-28-2007, 01:31 PM
  3. Doubly-Linked List
    By jgs in forum C Programming
    Replies: 7
    Last Post: 04-18-2005, 01:39 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. Doubly Linked List.. please Help!!
    By ProgrammingDlux in forum C++ Programming
    Replies: 8
    Last Post: 10-24-2004, 08:27 PM