List size

[jdm2104]

Hi,

What would be the best way to keep a list size from being no greater than a specified amount.

For example, if I update my list and the list size goes over a limit a node is deleted from the end of the list.

Would it be better implementing a circular list or a doubly linked list?

I have tried to implement the latter but can't work out how to keep track of the tail.

Cheers

[SuperKoko]

Why not implement your list in term of std::list ?
Your class would contain a std::list object and a std::list::size_type object which would contain the number of items in the list.

[jdm2104]

Thanks for your suggestion but I would like to implement this myself rather than use any of the STL classes. The reason why is so I can learn the detail behind the algorithm and understand it.

[SuperKoko]

I have tried to implement the latter but can't work out how to keep track of the tail.

You need to define two pointers as class's members.
One pointer to the list head.
And one pointer to the list queue.
All operations on your list should be done from non-static member functions of your list, not on context-free iterators, because it would be hard to take trace of which list belong to your iterator.... or, you may include a pointer to the list as instance variable of the iterator.

If you keep in mind that each member function of your list can assume that, before being called, the tail-pointer really points to the tail of your list (pre-condition), and must ensure that before returning, the tail pointer is also valid (post-condition), then your class will work!

Now, if you find a more specific problem, you can post the code you have written.

[jdm2104]

Thanks I'll give it a go.

[cilu]

What would be the best way to keep a list size from being no greater than a specified amount.

A simple example:

#define MAXSIZE 10

class mylist
{
int list[MAXSIZE];
int index;
public:
mylist(): index(0) {}

void add(int element)
{
list[index++] = element;
index %= MAXSIZE;
}
};