Deleting items in array-based List

Question

In a program for an array-based list, I have a function that calls the following 3 times:

list->remove(1)

My issue is that, when this prints out, it says it's deleting the original first item 3 times, rather than going to the next, new first item.

To be specific, when this code is called in test.cpp:

for (int i = 1; i <= 3 && ! list->isEmpty(); i++) {
        cout << "Deleting item " << i << "." << endl;
        try {
                cout << "Deleted item " << list->remove(1) << endl;
        }
        catch (int e) {
                cout << "*** Error deleting from position " << i << " ***" << endl;
        }
}

it returns the following:

Deleting item 1.
Deleted item 1
Deleting item 2.
Deleted item 1
Deleting item 3.
Deleted item 1

Here is the ABList class I created. I think the error is in my remove method, but I cannot figure out where:

#ifndef _ABLIST_H_
#define _ABLIST_H_

#define LIST_MAX 10

#include <iostream>
#include "ABCList.hpp"

using namespace std;

template <class T>
class ABList : public ABCList<T> {

    private:
        T    a[LIST_MAX];
        int  size;

    public:
        ABList ();
        ~ABList ();
        virtual bool isEmpty ();
        virtual int  getLength ();
        virtual void insert (int pos, T item);
        virtual T    remove (int pos);
        virtual T    retrieve (int pos);
};


template <class T>
ABList<T>::ABList () {
    size = 0;
}

template <class T>
bool ABList<T>::isEmpty () {
    if (size == 0)
        return true;
    return false;
}

// returns size, which is updated whenever the list is lengthened or shortened
template <class T>
int ABList<T>::getLength() {
    return size;
}

template <class T>
void ABList<T>::insert(int pos, T item) {

    try {
        // if list is at maximum size
        if (size >= LIST_MAX)
            throw "Size is greater than or equal to LIST_MAX\n";
        // if "pos" is a negative number
        if (pos < 0)
            throw "Pos must be greater than 0\n";
        // if "pos" is outside the bounds of the existing list
        if (pos > size + 1)
            throw "Pos must be less than or equal to list size\n";

        //shift all items at indices > pos one index up
        for (int i = size; i >= pos; --i) {
            a[i] = a[i-1];
        }
        //insert new item
        a[pos-1] = item;
        //increment size
        size++;

    } catch (char* message) {
        cout << "Error: " << message;
        throw 1; // any int will do, to catch exception flag in test.cpp
    }
}

template <class T>
T ABList<T>::remove(int pos) {

    try {
        if (pos < 1)
            throw "Pos cannot be less than 1";
        if (pos > size)
            throw "Pos cannot be greater than size";
        //find T to be removed, to return later
        T temp = retrieve(pos);
        //shift all items greater than pos down one index
        for (int i = pos + 1; i <= size; i++)
            a[i] = a[i+1];
        // decrement size
        size--;
        return temp;
    } catch (char* message) {
        cout << "Error: " << message;
        throw 1;
    }
}

template <class T>
T ABList<T>::retrieve(int pos) {
    try {
        //check that pos is valid
        if (pos < 1 || pos > size)
            throw "Position is outside bounds of ABList\n";

        return a[pos-1];

    } catch (char* message) {
        cout << "Error: " << message;
    }
}


#endif

Here is the main program. (For the sake of this problem, I have to assume it is immutable):

int main () {
    // Testing the List implmenetations; first, get a list:
    ABCList<string> * list = getList();

    // Test "insert"
    cout << "Let's populate the list with a few items." << endl;
    for (int i = 1; i <= TEST_SIZE; i++) {
        int pos = getPos(i); // Randomise "i" to test
        string input;

        cout << "Enter a word to place into the list at position " << pos << ": ";
        cin >> input;

        try {
            list->insert(pos, input);
            cout << "Successfully inserted at position " << pos << "." << endl;
        }
        catch (int e) {
            cout << "*** Error inserting at position " << pos << " ***" << endl;
        }
}


    // Test "retrieve" & "getLength"
    cout << "List is as follows: \n\t";
    for (int i = 1; i <= list->getLength(); i++) {
        cout << list->retrieve(i) << " ";
    }
    cout << endl;


    // Test "delete" and "isEmpty"
    for (int i = 1; i <= 3 && ! list->isEmpty(); i++) {
        cout << "Deleting item " << i << "." << endl;
        try {
            cout << "Deleted item " << list->remove(1) << endl;
        }
        catch (int e) {
            cout << "*** Error deleting from position " << i << " ***" << endl;
        }
    }

    // Done. Let the destructor handle the rest.
    delete list;

    return 0;
}

Answer 1

During removal you do this after getting the item at (1) (which is really the item at a[0]:

for (int i = pos + 1; i <= size; i++)
    a[i] = a[i+1];

Now what is pos when this is entered? it's (1), so you're walking the list from (2) to size, shifting everything from 3..(size+1) to 2...(size). The item at "position" 1 (which again, is actually in slot 0 in the array, is never overwritten, thus it is always the reported returned item.

Not only is this incorrect, it is also UB (undefined behavior) when the array is fully populated you'll be access data one slot past the last viable location.

You want to throw out the item at pos, which is 1-based (your design; not mine). Its underlying element was at location a[pos-1] in the array. so try this:

for (int i = pos; i < size; ++i)
    a[i-1] = a[i];

This should be safe if you check to ensure pos is always 1 or greater (and it appears you do, in fact, do this). Personally I'd stick with a zero-based indexing system, but you have your design reasons, I'm sure.

Answer 2

In the remove method you are shifting down one index wrongly. It should be like this:

for (int i = pos + 1; i <= size; i++)
    a[i-1] = a[i]; // instead of a[i] = a[i+1];

The other way could be

for (int i = pos; i <= size; i++)
    a[i] = a[i+1];

Please check if it works.