The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Linked lists Modifying Lists
 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter

Modifying Lists

Obviously one way to modify a list is to change the cargo of one on the nodes, but the more interesting operations are the ones that add, remove, or reorder the nodes.

As an example, we'll write a method that removes the second node in the list and returns a reference to the removed node.

    Node* removeSecond (Node *list) {
        Node *first = list;
        Node *second = list->next;

        // make the first node refer to the third
        first->next = second->next;

        // separate the second node from the rest of the list
        second->next = null;
        return second;
    }

Again, I am using temporary variables to make the code more readable. Here is how to use this method.

        printList (node1);
        Node *removed = removeSecond (node1);
        printList (removed);
        printList (node1);

The output is

(1, 2, 3)           the original list
(2)                 the removed node
(1, 3)              the modified list

Here is a state diagram showing the effect of this operation.

What happens if we invoke this method and pass a list with only one element (a singleton)? What happens if we pass the empty list as an argument? Is there a precondition for this method?
Home Linked lists Modifying Lists

Last Update: 2005-12-05