[Liezel]

I am new to the topic of linked lists and I don't know how to define this function to add two linked list based integers and storing the result in a third. I tried to do this, could not put function in main because then I don't have acces to protected members of the class. I think I can manage the addition algorithm, just need help with the return type en parameters of my function.

//Header file: linkedList.h

#ifndef H_LinkedListType
#define H_LinkedListType

#include <iostream>
#include <cassert>

using namespace std;

//Definitions of the node
template<class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};

template<class Type>
class linkedListType
{

friend ostream& operator<<<>(ostream&, const linkedListType<Type> &);
//Overload the stream insertion operator.

//Adding two integers
friend linkedListType<int> AddLists<>(const linkedListType<int> &,
const linkedListType<int> &);

public:
const linkedListType<Type>& operator=
(const linkedListType<Type>& list);
void initializeList();
bool isEmptyList();
int length();
void destroyList();
Type front();
Type back();
bool search(const Type& searchItem);
void insertFirst(const Type& newItem);
void insertLast(const Type& newItem);
void deleteNode(const Type& deleteItem);
linkedListType();
linkedListType(const linkedListType<Type>& otherList);
~linkedListType();


protected:
int count;
nodeType<Type> *first;
nodeType<Type> *last;

private:
void copyList(const linkedListType<Type>& otherList);


};

//Function that I have problem with:
template<class Type>
linkedListType<int> AddLists(const linkedListType<int> &L1,
const linkedListType<int> &L2)
{
linkedListType<Type> L3;
nodeType<Type> *current_L1;
nodeType<Type> *current_L2;
nodeType<Type> *current_L3;

current_L1 = L1.first;
current_L2 = L2.first;
current_L3 = L3.first;

Type carry = 0;

while (current_L1 != NULL || current_L2 != NULL)
{
current_L3->info = current_L1->info + current_L2->info + carry;
if (current_L3->info > 9)
{
carry = current_L3->info/10;
current_L3->info = current_L3->info%10;
}
current_L1 = current_L1->link;
current_L2 = current_L2->link;
current_L3 = current_L3->link;
}

}

//Main to test function with:
#include <iostream>
#include "LinkedList.h"

using namespace std;

int main()
{
linkedListType<int> L1;
linkedListType<int> L2;
linkedListType<int> L3;

//Build up L1 and L2 starting with least signigicant digit
L1.insertLast(5);
L1.insertLast(3);
L1.insertLast(1);

L2.insertLast(2);
L2.insertLast(7);
L2.insertLast(1);

cout<<L1<<endl<<L2<<endl;

AddLists(L1,L2);
cout<<L3<<endl;



return 0;
}

[mattman059]

can you use the STL or do you have to implement your own linked lists

[Liezel]

Hi I only have this linkedList class and its implementation to work with, I am not aware of STL functions that I can use.

//Header file: linkedList.h

#ifndef H_LinkedListType
#define H_LinkedListType

#include <iostream>
#include <cassert>

using namespace std;

//Definitions of the node
template<class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};

template<class Type>
class linkedListType
{

friend ostream& operator<<<>(ostream&, const linkedListType<Type> &);
//Overload the stream insertion operator.

public:
const linkedListType<Type>& operator=
(const linkedListType<Type>& list);
void initializeList();
bool isEmptyList();
int length();
void destroyList();
Type front();
Type back();
bool search(const Type& searchItem);
void insertFirst(const Type& newItem);
void insertLast(const Type& newItem);
void deleteNode(const Type& deleteItem);
linkedListType();
linkedListType(const linkedListType<Type>& otherList);
~linkedListType();


protected:
int count;
nodeType<Type> *first;
nodeType<Type> *last;

private:
void copyList(const linkedListType<Type>& otherList);


};

[NickDMax]

Boy oh boy does that look like fun!!! Sarcastic I know.

The process of doing arithmatic with abstract linked list is interesting. The first problem I see is that of carry... how do you know when you need to preform a carry?

If you were using a KNOWN data type such as an int, then you would preform the addition itself in a larger datatype (say a long) and then check to see if a carry occured. IF you are using an unknown data type how can you do this?

I don't think you really can unless you specify an interface for the datatype.

I don't know exactly what your assignment is, but I would use a linked list of ints.

When I did addition I would create a NEW linked list that held the result, and so the return value would be the pointer to the head node of the new list.