C/C++ Introduction to Linked Lists in C++ Course

[Defennder]

I'm taking a C++ course and have just been introduced to the concept of linked lists and dynamic memory allocation. The following is from my notes:

//ListP.h: List ADT using Linked List
typedef int ListItemType;
class List {

    public:
        List();
        ~List();
        // ... ...No change to other methods
        bool isEmpty() const;
        int getLength() const;

        void insert(int index, const ListItemType& newItem)
            throw (ListException, ListIndexOutOfRangeException);

        void remove(int index)
            throw (ListIndexOutOfRangeException);

        void retrieve(int index, ListItemType& dataItem) const
            throw (ListIndexOutOfRangeException);

    private:
        struct ListNode {
            ListItemType item;
            ListNode *next;
        };
        int size;
        ListNode *head;
        ListNode* find(int index) const;
}; // end List class

List::List():size(0), head(NULL){}
List::~List()
{
    while (!isEmpty())
        remove(1);
} // end destructor
bool List::isEmpty() const
{
    return size == 0;
} // end isEmpty
int List::getLength() const
{
    return size;
} // end getLength

List::ListNode *List::find(int index) const
{
    if ( (index < 1) || (index > getLength()) )
        return NULL;
    else // count from the beginning of the list.
    {
        ListNode *cur = head;
        for (int skip = 1; skip < index; ++skip)
            cur = cur->next;
        return cur;
    } // end if
} // end find

void List::retrieve(int index,
        ListItemType& dataItem) const
throw(ListIndexOutOfRangeException)
{
    if ( (index < 1) || (index > getLength()) )
        throw ListIndexOutOfRangeException(
                "Bad index in retrieve");
    else
    { // get pointer to node, then data in node
        ListNode *cur = find(index);
        dataItem = cur->item;
    } // end if
} // end retrieve

    void List::insert(int index, const ListItemType& newItem)
throw(ListIndexOutOfRangeException, ListException)
{
    int newLength = getLength() + 1;
    if ( (index < 1) || (index > newLength) )
        throw ListIndexOutOfRangeException(
                "Bad index in insert");
    else
    { // try to create new node and place newItem in it
        ListNode *newPtr = new ListNode;
        size = newLength;
        newPtr->item = newItem;
        // attach new node to list
        if (index == 1)
        { // insert new node at beginning of list
            newPtr->next = head;
            head = newPtr;
        }
        else
        { ListNode *prev = find(index-1);
            // insert new node after node
            // to which prev points
            newPtr->next = prev->next;
            prev->next = newPtr;
        } // end if
    } // end insert

    void List::remove(int index)
        throw(ListIndexOutOfRangeException)
        {
            ListNode *cur;
            if ( (index < 1) || (index > getLength()) )
                throw ListIndexOutOfRangeException(
                        "Bad index in remove");
            else
            { --size;
                if (index == 1) {
                    // delete the first node from the list
                    cur = head; // save pointer to node
                    head = head->next;
                }

                else {
                    ListNode *prev = find(index - 1);
                    cur = prev->next; // save pointer to node
                    prev->next = cur->next;
                } // end if
                cur->next = NULL;
                delete cur;
                cur = NULL;
            } // end if
        } // end remove

The above contains both the header file and implementation file for a linked list. The question I have is, given that *head is a struct pointer to the start of the linked list, I don't see where in the above code is it initialised to point to the start of the linked list. I only see it declared under private of class List. The member functions above make use of *head as though it were already made to point to the start of the list, but it doesn't appear to have been made to point to the starting of the linked list. Is this supposed to be done in int main() or has it alread been done above?

 

[csprof2000]

It is set to null in the constructor ... head(NULL) ... and is set to the first item added to the list... under the insert method, when index == 1.

 

[Defennder]

Okay thanks.