Tom Kelliher, CS23

Mar. 12, 1996

• Collect designs.

• Exam problems:
1. Classes.

2. Unix.

3. Pointers and dynamic memory allocation.

4. Programming problem involving use of lists.

5. Recursion.

Solve four of five.

# A Simple Example: Integers on a List

## Array Implementation

Declaration file:

```#ifndef __ALIST_H
#define __ALIST_H

const int MAX = 100;

class List
{
public:
List(void) { size = 0; }
void Insert(int newValue);   // add newValue to "beginning" of list
int Delete(void);       // return and delete "first" item on list
void Print(void);       // print list

private:
int size;   // number of items in list
int items[MAX];
};

#endif
```

Implementation file:

```#include <assert.h>
#include <iostream.h>
#include <iomanip.h>
#include "alist.h"

void List::Insert(int newValue)
{
assert (size != MAX);
items[size++] = newValue;
}

int List::Delete(void)
{
assert (size != 0);
return items[--size];
}

void List::Print(void)
{
for (int i = size - 1; i >= 0; --i)
cout << setw(10) << items[i] << endl;
}
```

How do we choose the size of MAX?

How do we add to the middle of the list?

## Pointer-Based Implementation

Declaration file:

```#ifndef __PLIST_H
#define __PLIST_H

#include <stdlib.h>
struct listItem
{
listItem* next;
int value;
};

typedef listItem* listPointer;

class List
{
public:
List(void) { list = NULL; }
~List();
void Insert(int newValue);   // add newValue to "beginning" of list
int Delete(void);       // return and delete "first" item on list
void Print(void);       // print list

private:
listPointer list;
};

#endif
```

Implementation file:

```#include <iostream.h>
#include <iomanip.h>
#include <assert.h>
#include <stdlib.h>
#include "plist.h"

List::~List()
{
listPointer temp;

while (list != NULL)
{
temp = list;
list = list->next;   // unlink first item on list
delete temp;         // delete it
temp = NULL;
}
}

void List::Insert(int newValue)
{
listPointer temp = new listItem;
assert (temp != NULL);

temp->next = list;
list = temp;
temp->value = newValue;
}

int List::Delete(void)
{
listPointer temp;
int returnVal;   // value of first list item

assert (list != NULL);
returnVal = list->value;   // get value of first list item
temp = list;
list = list->next;   // unlink first list item
delete temp;         // delete first list item
temp = NULL;
return returnVal;
}

void List::Print(void)
{

for (listPointer i = list; i != NULL; i = i->next)
cout << setw(10) << i->value << endl;
}
```

How do we add to the middle of the list?

```#include <iostream.h>

#ifdef POINTERS

#include "plist.h"

#else

#include "alist.h"

#endif

int main()
{
List l;

l.Insert(4);
l.Insert(39);

l.Print();

cout << "Deleted " << l.Delete() << endl;

l.Print();

return 0;
}
```

Compiling?

## Comparison

• Memory space
• Execution 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.

Thomas P. Kelliher
Mon Mar 10 21:08:28 EST 1997
Tom Kelliher