Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Intro to linked lists

  1. May 16, 2008 #1

    Defennder

    User Avatar
    Homework Helper

    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:

    Code (Text):
    //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?
     
    Last edited: May 16, 2008
  2. jcsd
  3. May 16, 2008 #2
    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.
     
  4. May 17, 2008 #3

    Defennder

    User Avatar
    Homework Helper

    Okay thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Intro to linked lists
  1. Linked List (Replies: 9)

  2. Linked list (Replies: 12)

  3. Java linked list (Replies: 1)

Loading...