List
List: (new ADT) Can find example in Data Structures
Book page 112-113
description of a list:
- A
List is a sequence of objects. All are of the same type similar to an array with
one exception.
array - next to each other in memory
list -
maybe yes but maybe no.
operations of a List:
- clear a list
- check if it's full
- check length
- retrieve an item from
- insert an item into
- delete an item from
- reset the list
Now we need to
create and implement methods for these operations. Detailed examples are
listed on page 119 of the Data Structures book.
const int MAX_SIZE = 100;
class IntList
{
int data[MAX_SIZE];
int count;
// counter
int cpos;
// current
position
public:
IntList();
void MakeEmpty();
bool IsFull()const;
int LengthIs()const;
void Insert(int);
void Retrieve(int &, bool & found);
void Delete(int);
};
/*******************************************/
IntList()
{
count = 0;
cpos = 0;
}
/********************************************/
void IntList::MakeEmpty()
{
// same as constructor but can be called at
anytime
cout = 0; // resets count to zero
cpos = 0; // resets current position to
zero
}
/**********************************************/
bool IntList::IsFull()const
{
return (count >= MAX_SIZE);
// can do this because results of relational expressions are
bools
}
/***********************************************/
int
IntList::LengthIs()const
{
return count;
}
/***********************************************/
void IntList::Insert(int item)
{
if (count == MAX_SIZE)
return;
data[count] = item;
cpos = count;
count++;
}
/**********************************************/
What is it that
we want to do in the retrieve function? Assume that you have a list as
follows:
|
2 |
6 |
5 |
3 |
9 |
if we want to
find the position of 5 we start at the beginning and step through list until we
find it. If it's not in the list we exit.
void IntList::Retrieve(int &item, bool &found)
{
int index = 0;
while(item != data[index] && index <
count)
index++;
if (index == count);
{
found = false;
return;
}
item = data[index];
cpos = index;
found = true;
}
Note:
You can also return a bool and "86" the bool &found in the header if
you would like. That would be my reference but the book does it this way
so we'll stick with it for now.
Now we need to
do some removal and cleanup…
If you want to
delete the item 6 in the list above, you have a problem if using an array.
What you need to do is to delete the item and then "shake down" all
remaining items one position to create a list containing the integers (2, 5, 3,
9).
This will
take three parts:
does the element you want
to delete exist in the list
delete the
element
copy or "shake down" items
over
void IntList::Delete(int item)
{
// first do the search
int index = 0;
while(index < count && item !=
data[index])
index++;
// if none is found do nothing and return
if (index == count)
return;
// found so perform move
cpos = index;
count--; // fix boundary position because of
deleted item
while(index < count);
{
data[index] = data[index+1]; //
shake down
index++;
}
}
You can also
make a second Insert method which will insert an item at a certain position of
the list. To do this you need to move to the end, add one position and do
a position swap moving backwards until you find the position you want to insert
the item into.
void IntList::Insert2(int &item, int pos)
{
// test for room to insert an item
if(count == MAX_SIZE)
return; // can't insert
because there isn't room
// check for other errors
if(pos < 0 || pos > count)
return;
// create an open position
while(index>pos)
{
data[index] = data[index-1];
index--;
}
// insert new item into list
data[index] = item;
cpos = pos;
count++;
}