You are here:

C++/Lists with pointers


I've been trying to figure this out for a while:  Here is a simple list class:

class ListElement
     ListElement(void *itemPtr, int sortKey);   
     ListElement *next; // next element on list,
     int   key;   // priority, for a sorted      
     void *item;        // pointer to item on the

And here's a member function from class List:

void List::Append(void *item)
 ListElement *element = new ListElement(item, 0);

 if (IsEmpty())
        // list is empty
        first = element;
        last = element;
    {   // else put it after last
        last->next = element;
        last = element;

Here's my question.  When I create an instance of ListElement, and I Append that Element, both first and last are the same.  (Let's say I Append the integer 5.)  Now when I append a new element (Say the integer 6), exactly what happens?  It seems that both last's Next member AND last itself should both be 6.  Why does the "last=element;" exist?  Why do we need that?  If I append a third element, say the integer 7, it seems to me that last's Next member will be overwritten and last itself with 7.

Ah! The joys of linked lists!

First the list does _not_ contain the values - it contains lists elements which contain the values together with the housekeeping information to maintain the list - in this case the next element pointer.

The list contains two list element pointers - one to point to the first element and one to point to the last element. Each element is linked to the next element by the element's next pointer - which should I would expect be a null pointer if there is no next element (because it is the last element). The only other alternative would be if the last element points back to the first making the list circular - however this appears not to be the case in the Append operation you show.

Now taking the case of Appending a value, 5, to the end of an empty list we see that first off the list creates a new element initialised with the element value and a sort key of 0 - which is not used further in the code shown. This new element is then linked to both the first and the last element pointers maintained by the list as it is the only element in the list and so is both the first and the last element. All this is just as you state in the question. Ok so far.

(Use a fixed spaced font such as Courier or Courier New to view the following diagrams)

The list and element can be pictured as follows:

list.first -> element(5,0).next-> <null>
list.last  ----^

Now we append a second value, 6, to the end of the list as shown above. The new list element created for this will be the new last element. The new element will also be the first element's next element. So, after creating the new list element the Append operation first links the new element to the _previous_ last element - which of course is the first element which can be reached by following the last pointer of the list, hence list.last points to the first element whose next pointer is set to point to the new element:

list.first -> element(5,0).next
list.last  ----^          |
         element(6,0).next -> <null>

(sorry for the poor quality of the diagram, there is not much I can do with just text in the way of pictures!).

However, as you should be able to see this is not correct as list.last still points to the first element and not the new last, so the code next sets the List's last pointer to point to the new (last) element:

list.first -> element(5,0).next
         element(6,0).next -> <null>
list.last  ----^

The thing to remember here is that we are dealing with pointers to objects - new returns a pointer to the newly created object (a ListElement in this case). List's first and last data members will be pointers to ListElement objects or (hopefully) a null pointer value and each ListElement's next pointer points to another ListElement object or is a null pointer value.

All the assignments do is change the stored pointers. The elements which contain the list values are still out there in memory - in fact they stay allocated in memory until they are deleted - so it is important to maintain the list so that every time an item is removed from the list the ListElement object managing it is deleted so the object is destroyed and its memory returned to the system.

Now looking at specifically at your question's detail:

The list last pointer changes each time an element is appended. Initially it is a null pointer value (at least I hope it is and not some random rubbish!). Then it points to the element for the value 5 then it is the pointer value that points to the element for the value 6. If we then append a value 7 last will point to the element created for this item:

list.first -> element(5,0).next
         element(7,0).next -> <null>
list.last  ----^

Notice that we have not lost any of the elements containing the list values - they are all still there, linked to each other and the list (for the current first and last elements).

Note that last only changes as the final thing done by Append. On entry last points to the element previously appended (or nothing for an empty list). This is exactly the element that should refer to the new last item via its next element pointer, for lists with at least one existing element that is.

So last->next really means "locate the element currently pointed to by last, then use its next member".

At the end of Append for non empty lists the last element object always has two things pointing at it - the previous element's next pointer (or the list's first pointer for the first element) and the list's last element pointer. Strictly speaking the last pointer is not required as you can always find the last element by starting with the element referenced by first (if any, if none then it is the first element being appended) and following the next pointers to each subsequent element until the one with a null next pointer is reached - indicating the end of the list, and just overwriting this final null next pointer value with the pointer value of the newly appended value's ListElement object. However this is tedious and takes longer each time a new element is appended to the list - so storing a last element pointer in the list seems a good way to simplify appending and speed up most append operations - making each append operations take a (roughly) fixed amount of time and not an amount that varies proportionally with the number of elements in the list.

Sorry if this has gone on for a bit but I am hoping that at least one way of explaining it will clarify your confusion as I am not clear from your question where exactly you have wandered off the path (as it were) in your thinking.

Oh one final thing. Link lists and other such data structures can be tricky to visualise at first and drawing a diagram of what is going on often helps. Even now I sometimes draw diagrams showing which things point to others - just to make sure I have got it right.  


All Answers

Answers by Expert:

Ask Experts


Ralph McArdell


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.


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


©2017 All rights reserved.