You are here:

C++/Doubly Linked List

Advertisement


Question
A_O_A
     Sir, I implemented Doubly Linked List in C++.But the add and remove method can not work properly. So sir see the code and correct it. The code is,
The code of the Node class,
/************************************************/
#ifndef _NODE_H
#define _NODE_H

class Node{
         public:
         int get( ){return object;};
         void set(int object){this -> object = object;};
         
         Node *getNext( ){return nextNode;};
         void setNext(Node *nextNode){this -> nextNode = nextNode;};
         
         Node *getPrev( ){return prevNode;};
         void setPrev(Node *prevNode){this -> prevNode = prevNode;};
         
         private:
         int object;
         Node *nextNode;
         Node *prevNode;
         };

#endif         
/************************************************/
The code for the Linked List is,
/************************************************/
#include <iostream.h>
#include <conio.c>
#include "Node.h"

class List{
         public:
         List( );
         void add(int);
         void remove( );
         int get( );
         private:          
         int size;
         Node *headNode;
         Node *currentNode;
         };
         List::List( )
         {
         headNode = new Node( );
         headNode -> setNext(NULL);
         headNode -> setPrev(NULL);
         currentNode = NULL;
         size = 0;
         }
         void List::add(int n)
         {
         Node *newNode = new Node( );
         newNode -> set(n);
         if(currentNode != NULL)
         {
         newNode -> setNext(currentNode -> getNext( ));
         newNode -> setPrev(currentNode);
         (currentNode -> getNext( )) -> setPrev(newNode);
         currentNode -> setNext(newNode);
         currentNode = newNode;
         }
         else
         {
         newNode -> setNext(NULL);
         headNode -> setNext(newNode);
         newNode -> setPrev(headNode);
         currentNode = newNode;
         }
         size++;
         };
         void List::remove( )
         {
         if(currentNode != NULL && currentNode != headNode)
         {
         (currentNode -> getPrev( )) -> setNext(currentNode -> getNext( ));
         (currentNode -> getNext( )) -> setPrev(currentNode -> getPrev( ));
         delete currentNode;
         currentNode = (currentNode -> getPrev( )) -> getNext( );
         size--;
         }
         }
         int List::get( )
         {
         if(currentNode != NULL)
         {
         return currentNode -> get( );
         }
         }

main( )
{
   clrscr( );
   List list;
   list.add(2);
   list.remove();
   cout << list.get( );
}          
/************************************************/

Sir see the code and correct the code.
         I am very thankful to you.

         Your,
         Imran Ahmad Mughal

Answer
Note that I am _not_ going to send you fully operational code. I will show you where I think you went wrong and one way to fix it. You will have to do the work of integrating my ideas into your code yourself however.

Your problem I think is that you tend to assume that you have good next and previous node pointers - checking for special end cases by seeing if the current node is NULL or the head node.

Now after you add a node your list looks like this (use a fixed pitch font otherwise things will not line up):

       0 <-(prev)
         HN <-(prev)
         (next)-> CN
         (next)-> 0
         

Where 0 are null pointer values and HN is the head node and CN is the current node (sorry for the bad diagram - hope you get the idea).

Now when you delete a node - the current node - you check that the current node pointer is not null and not the head node - all well so far. You get the current node's previous node pointer and set that node's next node pointer to point to the current node's next pointer, all well and good and we have the following:

       0 <-(prev)
         HN <-(prev)
       0 <-(next)   CN
         (next)-> 0

Now you try to set the previous pointer of the node following the current node to that of the current node - and this is where it all falls apart - there is no next node following on from the current node. The current node's next pointer is null - so

       (currentNode -> getNext( ))

returns null - bang! This is nothing that you could not have worked out for yourself given some time and paper and pen or pencil.

You  might like to try keeping both head and tail node pointers - the first node is both head and tail. The next node is the tail and the first the becomes just the head.

You can also not bother having any special nodes for these - just set their pointers to null pointer value to start with.

To insert at the head of the list you set the head pointer to the new node and set its previous pointer to null and its next pointer to the old head node value:

       newNode.next = head;
       newNode.prev = 0;
       if ( head )
       {
         head.prev = newNode;
       }
       head = newNode;
       if ( 0 == size )
       {
         tail = newNode;
       }
       ++size;

And similarly for inserting at the tail of the list:

       newNode.prev = tail;
       newNode.next = 0;
       if ( tail )
       {
         tail.next = newNode;
       }
       tail = newNode;
       if ( 0 == size )
       {
         head = newNode;
       }
       ++size;

Notice the special clauses for first nodes when the list is empty - in these cases we have to update both the head and tail node pointers.

To remove the current node you have to check that the next and previous pointers are not null before using them:

       Node * cn = currentNode;
       if ( cn->next )
       {
         cn->next->prev = cn->prev;
         currentNode = cn->next;
       }
       else
       {
         currentNode = cn->prev;
       }
       if ( cn->prev )
       {
         cn->prev->next = cn->next;
       }
       delete cn;
       --size;

Notice that in general the new current node is the next node, unless there is no next node when I make it the previous node - this was an arbitrary decision on my part and may not be what you require. The current node will only be null if the list is empty.     

Note that the code fragments shown above are straight out of my head and have not been tested at all so may contain logic errors and typos, but I hope it is enough to point you in the right direction.  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Ralph McArdell

Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials

©2016 About.com. All rights reserved.