# Linked Lists I, Continued; Polynomial Class

Tom Kelliher, CS18

May 3, 1996

• Evaluations on Monday.
• Quiz on Monday. Material: Today's list class for the polynomial class.
• Source code for the files available straight from the homepage.

Picking up from last time...

Operations:

• CreateList()
• DestroyList()
• ListIsEmpty()
• ListLength()
• ListInsert(NewPosition, NewItem, Success)
• ListDelete(Position, Success)
• ListRetrieve(Position, DataItem, Success)

## ListIsEmpty()

```int List::ListIsEmpty(void)
{
return list == NULL;
}
```

## ListLength()

```int List::ListLength(void)
{
int len = 0;
listPointer temp = list;

while (temp != NULL)
{
++len;
temp = temp->next;
}

return len;
}
```
Is this the ``best'' way?

## ListInsert()

```void ListInsert(int newPosition, int newItem)
{
listPointer newI;

assert (1 <= newPosition && newPosition <= ListLength() + 1);

if (newPosition == 1)
{
newI = new listItem;
assert (newI != NULL);

newI->next = list;
newI->value = newItem;
list = newI;
}
else
{
listPointer temp = list;

newI = new listItem;
assert (newI != NULL);

while (newPosition > 2)
{
--newPosition;
temp = temp->next;
}

newI->next = temp->next;
newI->value = newItem;
temp->next = newI;
}
}
```

## Exercise

Try the remaining List methods on your own.

# A Polynomial Class

• How can we use a linked list to represent a ``sparse'' polynomial?

Necessary files:

• list.cpp, list.h
• poly.cpp, poly.h
• main.cpp

## list.h

```#ifndef __LIST_H
#define __LIST_H

#include <stdlib.h>

struct ListItem
{
ListItem* next;
int exponent;
double coeff;
};

typedef ListItem* ListP;
```

```class List
{
private:
ListP l;

void Copy(const List& b);
void Free(void);

public:
List(void) : l(NULL) {}
~List();
List(const List& b);
const List& operator=(const List& b);
int Insert(int exp, double co);
int Retrieve(int exp, double& co);
int Delete(int exp);
void Print(void);   // For testing.
};

#endif
```

## list.cpp

```#include <iostream.h>
#include <stdlib.h>
#include <assert.h>
#include "list.h"

void List::Free(void)
{
ListP tmp;

while (l != NULL)
{
tmp = l;
l = l->next;
delete tmp;
}
}
```

```List::~List()
{
Free();
}

void List::Copy(const List& b)
{
ListP newCur;
ListP bCur;

if (b.l == NULL)
{
l = NULL;
return;
}

l = new ListItem;
assert (l != NULL);
l->exponent = b.l->exponent;
l->coeff = b.l->coeff;

newCur = l;   // Pointer to first item on target list.
bCur = b.l->next;   // Pointer to second item on source list.

while (bCur != NULL)
{
newCur->next = new ListItem;
assert (newCur != NULL);
newCur= newCur->next;
newCur->exponent = bCur->exponent;
newCur->coeff = bCur->coeff;
bCur = bCur->next;
}

newCur->next = NULL;
}

List::List(const List& b)
{
Copy(b);
}
```

```
const List& List::operator=(const List& b)
{
if (this != &b)
{
Free();
Copy(b);
}

return *this;
}

// It's up to the user to ensure there are no duplicate exponents on
// the list.

int List::Insert(int exp, double co)
{
ListP tmp;

tmp = new ListItem;
if (tmp == NULL)
return 0;

tmp->exponent = exp;
tmp->coeff = co;
tmp->next = l;
l = tmp;

return 1;
}

int List::Retrieve(int exp, double& co)
{
ListP i;

for (i = l; i != NULL; i = i->next)
if (i->exponent == exp)
{
co = i->coeff;
return 1;
}

return 0;
}
```

```int List::Delete(int exp)
{
ListP cur;
ListP tmp;

if (l == NULL)
return 0;

if (l->exponent == exp)
{
tmp = l;
l = l->next;
delete tmp;
return 1;
}

cur = l;

while (cur->next != NULL)
{
if (cur->next->exponent == exp)
{
tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
return 1;
}

cur = cur->next;
}

return 0;
}
```

```void List::Print(void)
{
ListP tmp;

cout << "----------\n";

for (tmp = l; tmp != NULL; tmp = tmp->next)
cout << "exp: " << tmp->exponent << "   coeff: "
<< tmp->coeff << endl;

cout << "----------\n";
}
```

## listtest.cpp

```#include <iostream.h>
#include "list.h"

void f(List a);

int main()
{
List a;

a.Insert(1, 2.3);
a.Insert(4, 5.6);

a.Print();

//   List b;
List b = a;

//   b = a;

b.Print();

cout << a.Delete(1) << endl;

a.Print();
b.Print();

cout << "Calling f().\n";
f(b);

b.Print();

cout << "Testing self-assignment.\n";

List c;

c.Insert(10, 11.12);
c.Insert(13, 14.15);

c.Print();
c = c;
c.Print();

cout << "Testing multiple-assignment.\n";

a = b = c;

a.Print();
b.Print();

return 0;
}

void f(List a)
{
cout << a.Delete(1) << endl;

a.Print();
}
```

Thomas P. Kelliher
Thu May 2 14:37:30 EDT 1996
Tom Kelliher