# C++ and linked lists ...



## TypeSK (Mar 16, 2002)

would anyone be willing to help me with my C++ and linked lists?

my problem, is that a couple semesters, we were required to do a linked list ....

i did it, but that was a couple years ago...

now, i have a project, and i am having to implement linked lists.

but i am having problem with one issue.

i was using the linked list implementation from a couple semesters ago, but found one issue. the implementation that i have, would take int as its data type within the linked list. 

but now, i need to use structs instead of ints, so converting it to take structs is a little harder?

here is my basic setup (try to explain it best i can):

files:
main.cpp (program itself)
linkedli.cpp <--
linkedli.h <--class to implement the linked list functions
node.cpp <--
node.h <--class to implement the node containing the pointer to next element and data itself

is there an easy way of converting it?

only functions i need to implement is to add data to the end of the list, retrieve from the front of the list, print the whole list, and peek into the front of the list. (basically a queue).

any help would be appreciated. if needed, i will post the files so you can see what i mean.


----------



## TypeSK (Mar 16, 2002)

here is the original node.cpp


```
// FILE: node.cxx
// IMPLEMENTS: The functions of the node class and the
// linked list toolkit (see node1.h for documentation).
// INVARIANT for the node class:
//   The data of a node is stored in data_field, and the link in link_field.

#include "node.h"
#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL and size_t
using namespace std;

namespace main_savitch_5
{
    size_t list_length(const node* head_ptr)
    // Library facilities used: cstdlib
    {
	    const node *cursor;
	    size_t answer;
        
    	answer = 0;
    	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	        ++answer;
    	
    	return answer;
    }
    
    void list_head_insert(node*& head_ptr, const node::value_type& entry)
    {
	    head_ptr = new node(entry, head_ptr);
    }

    void list_insert(node* previous_ptr, const node::value_type& entry) 
    {
	    node *insert_ptr;
    
	    insert_ptr = new node(entry, previous_ptr->link( ));
	    previous_ptr->set_link(insert_ptr);
    }

    node* list_search(node* head_ptr, const node::value_type& target) 
    // Library facilities used: cstdlib
    {
	    node *cursor;
   
	    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
    	    if (target == cursor->data( ))
		    return cursor;
	    return NULL;
    }

    const node* list_search(const node* head_ptr, const node::value_type& target) 
    // Library facilities used: cstdlib
    {
	    const node *cursor;
   
	    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
    	    if (target == cursor->data( ))
		        return cursor;
	    return NULL;
    }

    node* list_locate(node* head_ptr, size_t position) 
    // Library facilities used: cassert, cstdlib
    {
	    node *cursor;
	    size_t i;
    
	    assert (0 < position);
	    cursor = head_ptr;
	    for (i = 1; (i < position) && (cursor != NULL); i++)
    	    cursor = cursor->link( );
    	return cursor;
    }

    const node* list_locate(const node* head_ptr, size_t position) 
    // Library facilities used: cassert, cstdlib
    {
    	const node *cursor;
    	size_t i;
    
    	assert (0 < position);
    	cursor = head_ptr;
    	for (i = 1; (i < position) && (cursor != NULL); i++)
	        cursor = cursor->link( );
	    return cursor;
    }

    void list_head_remove(node*& head_ptr)
    {
	    node *remove_ptr;
    
    	remove_ptr = head_ptr;
    	head_ptr = head_ptr->link( );
    	delete remove_ptr;
    }

    void list_remove(node* previous_ptr)
    {
	    node *remove_ptr;
    
    	remove_ptr = previous_ptr->link( );
    	previous_ptr->set_link( remove_ptr->link( ) );
    	delete remove_ptr;
    }

    void list_clear(node*& head_ptr)
    // Library facilities used: cstdlib
    {
	    while (head_ptr != NULL)
    	    list_head_remove(head_ptr);
    }

    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) 
    // Library facilities used: cstdlib
    {
	    head_ptr = NULL;
	    tail_ptr = NULL;

	    // Handle the case of the empty list.
	    if (source_ptr == NULL)
    	    return;
    
	    // Make the head node for the newly created list, and put data in it.
	    list_head_insert(head_ptr, source_ptr->data( ));
	    tail_ptr = head_ptr;
    
	    // Copy the rest of the nodes one at a time, adding at the tail of new list.
	    source_ptr = source_ptr->link( ); 
	    while (source_ptr != NULL)
	    {
    	    list_insert(tail_ptr, source_ptr->data( ));
	        tail_ptr = tail_ptr->link( );
	        source_ptr = source_ptr->link( );
	    }
    }

}
```
here is the original node.h


```
#ifndef MAIN_SAVITCH_NODE_H  
#define MAIN_SAVITCH_NODE_H
#include <cstdlib> // Provides size_t and NULL

namespace main_savitch_5
{
    class node
    {
    public:
	// 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;
    };

    // FUNCTIONS for the linked list toolkit
    std::size_t list_length(const node* head_ptr);
    void list_head_insert(node*& head_ptr, const node::value_type& entry); 
    void list_insert(node* previous_ptr, const node::value_type& entry);  
    node* list_search(node* head_ptr, const node::value_type& target);
    const node* list_search
	(const node* head_ptr, const node::value_type& target);
    node* list_locate(node* head_ptr, std::size_t position);
    const node* list_locate(const node* head_ptr, std::size_t position);
    void list_head_remove(node*& head_ptr);
    void list_remove(node* previous_ptr);
    void list_clear(node*& head_ptr);
    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);
}

#endif
```
here is what ive done with node.h so far:

```
#ifndef MAIN_SAVITCH_NODE_H  
#define MAIN_SAVITCH_NODE_H
#include <cstdlib> // Provides size_t and NULL

namespace main_savitch_5
{

	template <class Comparable>
    class node
    {
    public:
	// TYPEDEF
    
	// CONSTRUCTOR
	node(
	    const Comparable& init_data = 0,
	    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 Comparable& 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:
	Comparable data_field;
	node* link_field;
    };

    // FUNCTIONS for the linked list toolkit
    std::size_t list_length(const node* head_ptr);
    void list_head_insert(node*& head_ptr, const node::value_type& entry); 
    void list_insert(node* previous_ptr, const node::value_type& entry);  
    node* list_search(node* head_ptr, const node::value_type& target);
    const node* list_search
	(const node* head_ptr, const node::value_type& target);
    node* list_locate(node* head_ptr, std::size_t position);
    const node* list_locate(const node* head_ptr, std::size_t position);
    void list_head_remove(node*& head_ptr);
    void list_remove(node* previous_ptr);
    void list_clear(node*& head_ptr);
    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);
}

#endif
```
i havent touched node.cpp

but ive basically been replacing all the typedef instances with Comparable (so that in the main program, i can declare what kind of linked list data it should hold (which in my case, would be mostly structs).

in my changes, am i doing everything correctly?

should i be swapping all the typedef instances with Comparable?

grrrrr


----------

