You are here:

C++/linked lists

Advertisement


Question

hello

how can i destroy an entire linked list?

assuming that i have a linked list "head"
if i go like this
delete head;

it will only delete the first element, not the rest

also, what is the difference between
head = NULL and
delete head?
does NULL free memory space?

thanks

Answer
Starting with your last points, as these are most fundamental.

Setting a pointer to a null pointer value _only_ sets the pointer to the object to point to nothing, it does not touch the object.

The reason this sort of thing works in other languages is that they employ garbage collection to automatically reclaim memory used by unused objects. Setting a reference to an object to null or nothing explicitly indicates that this reference to the object is no longer used. If it is the final reference then the object would be unused by anything and therefore eligible to be garbage collected - which by the way may be some time in the future.

However C++ (at present) does not as standard support garbage collection. Resource management (of memory and other resources) is up to the programmer to sort out.

Hence when a dynamically allocated object (i.e. an object created with new) is no longer required it has to be explicitly deleted - which causes its destructor to be called and the memory it occupies to be freed for reuse.

Also please note that NULL is a preprocessor macro and is really part of C not C++, although C++ ensures that NULL is defined correctly for use in C++ programs. In C++ we use the literal value 0 (zero) to indicate a null pointer value. This has some problems - firstly it is not always so clear that we are referring to pointers and secondly in some cases the compiler cannot tell we mean 0 (zero) a null pointer rather than 0 (zero) an integer. These problems have been noted and a nullptr name for the null pointer value looks likely to be part of the next version of the C++ standard (see http://en.wikipedia.org/wiki/C++0x#Null_pointer).

The other thing to note about deleting objects in C++ is that only the object directly referred to is deleted - whether explicitly by using delete or implicitly because the object went out of scope (for objects not dynamically allocated using new). Thus any objects referred to by pointer members of a deleted object are not also deleted.

This you point out in your question. Hence you have to follow the links in the linked list to delete each node in the list, and possibly the data pointed to by each node, although the destructor of the nodes should handle doing this. The only thing to remember is that you have to get the link to the next node _before_ deleting the current one as the link to the next node is part of the current node. You could use something like the following:

   Node * current = head;          // start with the head node
   while ( NULL != current )         // while we still have nodes...
   {
       Node * next = current->next;  // store the pointer to the next node
       delete current;          // delete the current node
       current = next;          // move on to the next node
   }

If nodes hold their data by pointer rather than by direct inclusion then destroying the nodes will have to ensure the data object is also deleted:

   Node::~Node  
   {
       delete data;    // if data is pointed to by each node.
   }

Note that this assumes data is not shared and that each node _owns_ the data value it is associated with.

You might be horrified that you have to keep track of all these dynamically created objects and the pointers to them and understand the ownership status of such objects. You may wonder if there are ways to help make life simpler. The answer is yes indeed there are.

C++ has what is called deterministic destruction. This mean you know when an object's destructor will be called and that it _will_ be called. It is either when it goes out of scope (what ever the scope of the object is) or, for dynamically created objects, when delete is called on a pointer to the object (or when delete [] is called on a pointer to a built in array of objects).

For sub-objects of class instances (data members and base class sub-objects), their destructors get called during the destruction of the object they are part of.

Local stack objects (or local automatic objects) defined in functions are destroyed when they go out of scope either at the end of the function call or at the end of the block they are defined in. Most usefully they will also be properly destroyed with destructors called if an exception is thrown while they are' live'.

This allows us to create resource management class types that acquire a resource on construction and release it on destruction. Simple object handling types just accept a pointer to a (new) object on construction and delete the pointed to object in the destructor:

   class DynamicNodeManager
   {
   public:
       DynamicObjectManager( Node * node )
       : iNode(node)
       {
       }
       
       ~DynamicObjectManager() { delete iNode; }

   private:
       Node *    iNode;
   };

Of course this is not too useful as we have no way of using the managed object. Here another of C++'s features comes to the rescue: operator overloading. Most C++ operators can be overloaded for use with user defined (class) types. This includes the dereference (*) and member access through pointer (->) operators.

   class DynamicNodeManager
   {
   public:

       // ...
       
       Node & operator*() const  { return *iNode; }

       Node * operator->() const { return iNode; }
       
   private:
       Node *    iNode;
   };

Finally, the above only works with one type. Making such types generic is much more use. Generic types are implemented using templates in C++:

   template <class T>
   class DynamicObjectManager
   {
   public:
       DynamicObjectManager( T * p )
       : iPtr(p)
       {
       }
       
       ~DynamicObjectManager() { delete iPtr; }
       
   T & operator*() const  { return *iPtr; }
   T * operator->() const { return iPtr; }
       
   private:
       T *    iPtr;
   };

This is the basis for all such resource management types, although full blown versions have a few more bells and whistles - maybe a get function to return the managed pointer or a reset operation to reset the managed pointer to another.

Such types are sometimes called smart types - if they manage memory based resources as above then they are called smart pointers. The general idiom is called Resource Acquisition Is Initialisation (RAII), although in fact the most important part is ensuring the resource is correctly released on destruction of the smart object.

Objects such as that above may be used as follows:

   void Fn()  
   {
       DynamicObjectManager<Node> pNode( new Node(1234) );

       DoSomethingWithTheNodeData( pNode->GetData() );

       DoSomethingWithTheNodePassedByReferece( *pNode );

   // No need to delete
   // - pNode goes out of scope and ~DynamicObjectManager<Node> is called
   // which will call delete on the Node pointer for us
   }

If either DoSomethingWithTheNodeData or DoSomethingWithTheNodePassedByReferece throws an exception then pNode is deleted and the managed Node pointer has delete called on it.

The other use is as class members:

   class Node
   {

   // ...

       Node( int data )
       :  iData( new int(data) )
       {
       }

   // ...
   
   private:
       DynamicObjectManager<int>    iData;
   };

The above is somewhat contrived as it is a little extreme for nodes that store int data items to create a new int dynamically for each node, however it demonstrates the point.

When a node is created it is handed an int value. This is used to initialise a newly created int, the pointer of which is stored in a DynamicObjectManager<int> - a DynamicObjectManager for int. When the Node object is deleted the destructor of the iData member is called and that calls delete on the contained pointer to the created int. There is no need for Node to do this explicitly in its  destructor anymore.

We can extend this to the next node pointer, however here we need to have a reset operation in our smart pointer type and a default constructor that initialises the managed pointer to a null pointer value. I shall redefine the smart pointer type and change its name to ScopedPtr, as it basically manages objects over a given scope (as in the Fn example above). This is taken from some actual code I used a few years ago:

 template <typename T>
 class ScopedPtr : NonCopyable
 {
       T* iPtr; // Managed pointer.

 public:
       explicit ScopedPtr( T* p=0 ) : iPtr(p) {}

         ~ScopedPtr()    { delete iPtr; }

       T & operator*() const   { return *iPtr; }

       T * operator->() const  { return iPtr; }

       T * Get() const         { return iPtr; }

       void Reset( T* p=0 )    { if ( iPtr != p ) {delete iPtr; iPtr = p; }}

 };  // ScopedPtr

Get simply returns the managed pointer.

Reset first checks to see if we are resetting the pointer to the same value and if not deletes the currently managed object and then sets the iPtr member so the ScopedPtr object manages object pointed to by the new pointer.

The constructor now defaults the pointer parameter p to 0 (null pointer) if it is not given. Note the use of explicit on the constructor. This prevents any single parameter constructor being used for implicit type conversions.

The base class NotCopyable is a utility class that prevents copying and assignment of object of classes derived from it.

We need to be able to reset the managed pointer after construction of a ScopedPtr in the case of next nodes in a linked list because there may not be a next node when the node object is created.

Node might now look like this:

   class Node
   {

   // ...

       Node( int data )
       :  iData( new int(data) )
       {
       }

       void SetNext( Node * node )
       {
         iNext.Reset(node);
       }

   // ...
   
   private:
       ScopedPtr<int>     iData;
       ScopedPtr<Node>    iNext;
   };

This looks cool. We create a node with a value. Then we can add a next node to it using SetNext. This resets the iNext ScopedPtr for Nodes from the default value of 0, the null pointer, to the pointer to the next node, deleting the previous pointed to object (null). Calling delete on a null pointer is allowed and does nothing. Now when we delete the head node the ScopedPointers iData and iNext are destroyed, deleting what they point to. The iNext pointer points to another node and when it is deleted it causes its data and next node to be deleted etc, etc...

This is all very cools except for two points. The first is that now the deletion of a list is recursive and not iterative - when we delete the head we call the destructor of each node in the list before returning (view using a fixed point font such as Courier):

      Delete Head -> delete iNext -> delete iNext -> ...
         <- return       <- return       <- ...

[-> shows a call to and <- a return from a function (destructors are special functions). Each -> creates a new stack frame that is not released until the call returns.]

This may be a problem with large lists and/or systems with limited stack space.

The second problem is more fundamental: (re)setting the next node _deletes_ the previous next node. This is OK for the initial setting of next described above but it is common to insert, delete and re-order nodes by manipulating their links so this is not at all a good thing!!

In order to get around this we can use a smart pointer type that keeps a reference count of the number of references for a particular managed object. A common name for such a beast is a shared pointer because it allows a resource to be shared. Such a smart pointer allows itself to be copied and assigned to. Each time it is the reference count of references to the originally managed object is incremented. Each time a shared pointer that references and object is assigned to another it also decrements the count of references to any object is was managing. When a shared pointer is deleted the count of references to any object it is managing is decremented. When the count of references for a managed object goes to zero then it is deleted. I say 'any object it is managing' to cater for cases where no object is managed - the shared pointer's internal pointer is a null pointer.

I am not going to show code for a shared pointer as they tend to be more complex than the simpler scoped pointer types shown already. However assuming we have access to such a type, called SharedPtr rather than ScopedPtr we could re-write Node as follows:

   class Node
   {

   // ...

       Node( int data )
       :  iData( new int(data) )
       {
       }

       void SetNext( SharedPtr<Node> & node )
       {
         iNext = node;
       }
       
        SharedPtr<Node> GetNext()
       {
         return iNext;
       }

   // ...
   
   private:
       ScopedPtr<int>     iData;
       SharedPtr<Node>    iNext;
   };

Here we use a SharedPtr<Node> for iNext. Rather than passing in a raw Node pointer to SetNext we pass in a reference to a SharedPtr<Node>, this is assigned to the existing iNext SharedPtr which increments the new next node's reference count and decrements the existing.

I have also added a GetNext operation that returns the iNext pointer as a value copy of the iNext SharedPtr. This will bump up the reference count for the got node.

Now if we play around with the node links we can at least prevent a node from being deleted by calling GetNext to get another reference and bump up the reference count. On the other hand deleting a node is quite easy:

   pNodeBefore->SetNext( pNodeBefore->GetNext()->GetNext() );
   
This works providing you have already checked that

    pNodeBefore->GetNext().Get() != 0
    
i.e. that there is in fact a next node for node before.

Node before is the node before the one to be deleted. We want to set it to link to the node after the one to be deleted. Of course we want have the node to be deleted to be deleted!

The expression works as follows. Assume that all nodes referenced by SharedPtr have a node count of 1 to start.

First

    pNodeBefore->GetNext()

is evaluated and returns a (temporary) SharedPtr to its (non-null) next node, the node to be deleted. This node now has a reference count of 2.

Next we call

   GetNext()

for the node to be deleted to obtain a link to the node after it. The returned (temporary) SharedPtr will either refer to a node or to a null pointer. The null pointer case is not too interesting so let's check out the case where we do in fact have a node. This node's reference count will also be bumped up to 2.

At this point we have:

    Node before (1) -> Node to delete (2) -> Node after (2)

Where the numbers in ( and ) are the reference counts for the nodes and -> means 'links to'.

So far

    pNodeBefore->GetNext()->GetNext()

has been evaluated and we have a SharedPtr to the node following the one to be deleted. We pass this by _reference_ to

   pNodeBefore->SetNext

This means that no new instance of a SharedPtr is created and thus there is no change to the reference count.

In pNodeBefore->SetNext the line

   iNext = node;

is executed. The node parameter is the result of:

   pNodeBefore->GetNext()->GetNext()

i.e. the SharedPtr to Node after.

This assignment bumps up the reference count for the object referenced by node and decrements the reference count for the object referenced by iNext. So the reference count to Node after is incremented and the reference count to Not to delete is decremented (remember iNext is in fact the next node pointer for node before and so points to the node to be deleted). Also, after the assignment has been executed node before now has node after as its next pointer, and the node to be deleted is no longer linked in to the list but still refers to node after thus:

   Node before (1) -> Node after (3)        <- Node to delete (1)

Now the call to

   pNodeBefore->SetNext

returns and the end of the original statement is encountered. At this point all temporary values are deleted. We have two of them: The SharedPtrs returned by

   pNodeBefore->GetNext()->GetNext()

One references Node to delete and the other Node after. These are destroyed in the reverse of the order they were created, so the SharedPtr to Node after is destroyed first. This decrements the reference count for Node after:

   Node before (1) -> Node after (2)        <- Node to delete (1)

Next the temporary SharedPtr to Node to delete is destroyed, decrementing the reference count of Node to delete:

   Node before (1) -> Node after (2)        <- Node to delete (0)

This is now zero so the referenced Node object is deleted and in doing so its SharedPtr to its next node (Node after) is destroyed, decrementing the reference to Node after:

   Node before (1) -> Node after (1)

Now my ScopedPtr (and NotCopyable) are based on types in the Boost libraries (see http://www.boost.org/). In addition SharedPtr takes its name from the Boost type of a similar name. I did not use the Boost versions directly as the Boost libraries were not supported on the platform I was developing for.

The Boost names are scoped_ptr and shared_ptr - that is they use a different naming style. See http://www.boost.org/doc/libs/1_35_0/libs/smart_ptr/smart_ptr.htm for the Boost documentation on their smart pointer types. Some of these types have made it into the C++ ISO standard TR1 library update (most notably shared_ptr).

The original (1998) standard C++ library contained a smart pointer called std::auto_Ptr. It has very odd semantics and so has to be used with care (see Scott Meyers book "Effective STL" item 8).

Note that you require separate smart pointer types for managing single objects and arrays of objects. This is because single objects are deleted using delete while arrays of objects are deleted using delete [], which ensures the destructor is called for _every_ item in the array.

Finally, I repeat that although I have concentrated on smart pointers RIAA techniques can be used for handling any resource that has acquire/release semantics - e.g. open/close (files, sockets etc), acquire/release (concurrency locks etc.).

Hope this answers your question.  

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.