Short Answers

Short Answers Sections 5.1-5.2 Linked List Fundamentals

The node definition: class node { // TYPEDEF typedef double value_type; // CONSTRUCTOR node( const value_type& init_data = value_type( ), node* init_link = NULL ) { data_field = init_data; link_field = init_link; } // Member functions to set the data and link fields: void set_data(const value_type& new_data) { data_field = new_data; } void set_link(node* new_link) { link_field = new_link; } // Constant member function to retrieve the current data: value_type data( ) const { return data_field; } // Two slightly different member functions to retreive // the current link: const node* link( ) const { return link_field; } node* link( ) { return link_field; } private: value_type data_field; node* link_field; }; };

1. What is the one statement that can be used to insert a new node at the head of a linked list. Assume that the list's head_pointer is called head_ptr and the that the data for the new node is called entry.

2. Suppose that p is a pointer to a node in a linked list, and *p is not the tail node. What are the steps to removing the node after *p? Use one short English sentence for each step.

3. Suppose we are using the usual node definition (with member functions called data and link). Your program is using a node* variable called head_ptr to point to the first node of a linked list (or head_ptr == NULL for the empty list). Write a few lines of C++ code that will print all the double numbers on the list.

4. Suppose we are using the usual node definition (with member functions called data and link), and that locate_ptr is pointing to a node in a linked list. Write a statement that will make locate_ptr point to the next node in the list (if there is one). If there is no next node, then your statement should set locate_ptr to NULL.

5. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link.)

    size_t count_42s(const node* head_ptr); // Precondition: head_ptr is the head pointer of a linked list. // The list might be empty or it might be non-empty. // Postcondition: The return value is the number of occurrences // of 42 in the data field of a node on the linked list. // The list itself is unchanged. 

6. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link.)

    bool has_42(const node* head_ptr); // Precondition: head_ptr is the head pointer of a linked list. // The list might be empty or it might be non-empty. // Postcondition: The return value is true if the list has at least // one occurrence of the number 42 in the data part of a node. 

7. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link.)

    bool all_42s(const node* head_ptr); // Precondition: head_ptr is the head pointer of a linked list. // The list might be empty or it might be non-empty. // Postcondition: The return value is true if every node in the // list contains 42 in the data part. NOTE: If the list is empty, // then the function returns true. 

8. Implement the following function as a new function for the linked list toolkit. (Use the usual node definition with member variables called data and link. The data field is an int.)

    int sum(const node* head_ptr); // Precondition: head_ptr is the head pointer of a linked list. // The list might be empty or it might be non-empty. // Postcondition: The return value is the sum of all the data components // of all the nodes. NOTE: If the list is empty, the function returns 0.