PDA

View Full Version : Stu, more ?'s cometh



Orphious
11-20-01, 09:22 AM
Two questions for ya
1. This is a ? that I don't know
Say I wanted to make this class a class template with a type parameter of DataType. How could I do this.

class LinkedList
{
private:
class Node
{
public:
//members of Node
};
//members of linked list
};

And yes, this is for learning linked lists.

And 2.
What if I wanted to write a function to merges one linked listed object variable into another linked list obj var. keeping the items in order in the resulting list. The client prog would use list1.mergelists(list2); to merge them. How would I do this, or start to do this? Any ideas? I am only interested in the function to do this one operation.

Thanks a bunch again stu.

Stu
11-21-01, 01:44 AM
First question, something like the example that follows would work:




template<class DataType>
class LinkedList {

private:
class Node {

DataType the_data;

// Other stuff...

};

Node _ll_node; // Private node variable, for demo purposes; assume this is the current node

// Other stuff...

public:

// Access member function/method; returns current node value
DataType get_value(){

return _ll_node.the_data;

} // End get_value()

// Other stuff...
};



The second question is tough. Because there exists more than one type of linked list. I will assume you just want to insert the data of list2 to the end of the unordered/unsorted non-circular linked list list1 leaving list2 intact (the least complex problem).

Then the member function/method could be defined something like this:





// Assumptions:
//
// 1. This is a singly unordered non-circular linked list
// 2. Your insertion member function is defined as 'void LinkedList::insert(DataType val)'
// 3. That you have a 'void LinkedList::begin()' that moves you to the front of the list
// 4. That you have a 'bool LinkedList::next()' that moves you to the next item in the list
// and returns true; or returns false if there are no more items in the list
// 5. That you have a 'DataType LinkedList::get_value()' that returns the value of the current node
// 6. That you have a 'bool LinkedList::is_empty()' that returns true if the list has no items in it

void LinkedList::mergelists(LinkedList<DataType> &);
void LinkedList::mergelists(LinkedList<DataType> & other_list){

// If the list is empty, we are done!
if(!other_list.is_empty()){

// The list is not empty.

// Move to the first item in the other list...
other_list.begin();

// There exists at least one item; So, it is safe to use a do/while condition.

// Loop through the items in the other list and add them to this one...
do {

// Copy it in...
this->insert(other_list.get_value());

} while(other_list.next())

} // End if

} // End LinkedList::mergelists()



Finally, you will probably never--outside of a programming class--need to write your own linked list. The ANSI/ISO C++ Standard Template Library (STL) provides a 'list' template class, which is more than sufficient for most situations you need a list.