04.ARRAY-BASED LIST

SYNTAX

DEFINITIONS

LIST

• a collection of elements of the same type

  • because all the elements of a list are of the same type, they will be stored in an array

• the length of a list is the number of elements in the list

• to process a list in an array, the following variables are required

  • the array holding the list elements (a pointer)

  • a variable to store the length of the list (the number of list elements currently in the array)

  • a variable to store the size of the array (the maximum number of elements that can be stored in the array

LIST OPERATIONS

• create the list. the list is initialized to any empty state (constructor)

• determine whether the list is empty (check the length)

• determine whether the list is full (compare the length with the size

• find the size of the list

• destroy, or clear the list (destructor or a user-defined function)

• insert an item at a given position

• search the list for a given item

TEMPLATE

• a collection of elements of generic type

ARRAY-BASED LIST IMPLEMENTATION

UML

• The negative sign (-) signifies that the member variables are private

• The positive sign (+) signifies that the member functions are public

• The hash symbol (#) signifies that the member variables are protected

SOURCE CODE

HEADER FILE: arrayListDesign.h

/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 170741SEP24
# Filename: arrayListDesign.h
# Dependency: N/A
################################################*/

template <class Type>
class ArrayList
{
protected:
	int selfLength, selfMaxSize;
	Type* selfList;
public:
	ArrayList(int);              //constructor
	bool isEmpty();
	bool isFull();
	int listSize();
	int maxListSize();
	const void print();
	bool isItemAtEqual(int, const Type&);
	void insertAt(int, const Type&);
	void insertEnd(const Type&);
	void removeAt(int);
	void retrieveAt(int, Type&);
	void replaceAt(int, const Type&);
	void clearList();
	int seqSearch(const Type&);
	void insert(const Type&);    //without duplication
	void remove(const Type&);
	ArrayList(const ArrayList<Type>&);     //copy constructor
	~ArrayList();
	const ArrayList<Type>& operator=(const ArrayList<Type>&);
};

HEADER FILE: arrayListImplementation.h

#/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 170741SEP24
# Filename: arrayListImplementation.h
# Dependency: arrayListDesign.h
################################################*/

#include "ArrayListDesign.h"
#include <assert.h>

using namespace std;

template <class Type>
//constructor
ArrayList<Type>::ArrayList(int size) {
	selfLength = 0;
	if (size < 0) {
        cout << "The array size must be positive. Creating a default array of size 100.\n";
        selfMaxSize = 100;
    }
    else
        selfMaxSize = size;
    selfList = new Type[selfMaxSize];
    assert(selfList != NULL);             //capture programming error
}

template <class Type>
bool ArrayList<Type>::isEmpty() {
    return selfLength == 0;
    /*ALT procedure
    ** if (selfLength == 0)
    *    return true;
    *  else
    *    return false;
    */
}

template <class Type>
bool ArrayList<Type>::isFull() {
    return selfLength == selfMaxSize;
}

template <class Type>
int ArrayList<Type>::listSize() {
    return selfLength;
}

template <class Type>
int ArrayList<Type>::maxListSize(){
    return selfMaxSize;
}

template <class Type>
const void ArrayList<Type>::print() {
    if (isEmpty())
        cout << "Empty list\n";
    else {
        for (int i = 0; i < selfLength; i++)
            cout << selfList[i] << " ";
        cout << "\n";
    }
}

template <class Type>
bool ArrayList<Type>::isItemAtEqual(int position, const Type& x) {
    if (position < 0 || position >= selfMaxSize) {
        cout << "Valid positions must be in " << 0 << "..." << selfLength - 1 << "\n";
        return false;
    }
    else if (selfList[position] == x)
        return true;
    else
        return false;
}

template <class Type>
void ArrayList<Type>::insertAt(int position, const Type& x) {
    if (isFull())
        cout << "Can't insert in a full list.\n";
    else if (position < 0 || position > selfLength)
        cout << "Valid positions for insertion are " << 0 << "..." << selfLength << "\n";
    else {
        for (int i = selfLength; i > position; i--)
            selfList[i] = selfList[i - 1];
        selfList[position] = x;
        selfLength++;
    }
}

template <class Type>
void ArrayList<Type>::insertEnd(const Type& x) {
    if (isFull())
        cout << "Can't insert in a full list.\n";
    else {
        selfList[selfLength] = x;
        selfLength++;
    }
}

template <class Type>
void ArrayList<Type>::removeAt(int position) {
    if (isEmpty())
        cout << "Can't remove from an empty list.\n";
    else if (position < 0 || position >= selfLength)
        cout << "Valid positions for removal are " << 0 << "..." << selfLength - 1 << "\n";
    else {
        for (int i = position; i < selfLength - 1; i++)
            selfList[i] = selfList[i + 1];
        selfLength--;
    }
}

template <class Type>
void ArrayList<Type>::retrieveAt(int position, Type& x) {
    if (isEmpty())
        cout << "Can't retrieve from an empty list.\n";
    else if (position < 0 || position >= selfLength)
        cout << "Valid positions for retrieving are " << 0 << "..." << selfLength - 1 << "\n";
    else
        x = selfList[position];
}

template <class Type>
void ArrayList<Type>::replaceAt(int position, const Type& x) {
    if (isEmpty())
        cout << "Empty list.\n";
    else if (position < 0 || position >= selfLength)
        cout << "Valid positions for replacement are " << 0 << "..." << selfLength - 1 << "\n";
    else
        selfList[position] = x;
}

template <class Type>
void ArrayList<Type>::clearList() {
    selfLength = 0;
}

template <class Type>
int ArrayList<Type>::seqSearch(const Type& x) {
    if (isEmpty()) {
        cout << "Can't search in an empty list.\n";
        return -1;
    }
    else {
        for (int i = 0; i < selfLength; i++)
            if (selfList[i] == x)
                return i;
        return -1;
    }
}

template <class Type>
//without duplication
void ArrayList<Type>::insert(const Type& x) {
    if (selfLength == selfMaxSize)               //or if(isFull())
        cout << "Can't insert in a full list.\n";
    else if (selfLength == 0)                    //or if(isEmpty())
        selfList[selfLength++] = x;
    else {
        if (seqSearch(x) != -1)
            cout << "Duplication is not allowed\n";
        else
            selfList[selfLength++] = x;
    }
}

template <class Type>
void ArrayList<Type>::remove(const Type& x) {
    if (selfLength == 0)                         //or if (isEmpty())
        cout << "Can't remove from empty list\n";
    else {
        int i = seqSearch(x);
        if (i == -1)
            cout << x << " doesn't exist in the list\n";
        else
            removeAt(i);
    }
}

template <class Type>
//copy constructor
ArrayList<Type>::ArrayList(const ArrayList<Type>& otherList) {
    selfMaxSize = otherList.selfMaxSize;
    selfLength = otherList.selfLength;
    selfList = new Type[selfMaxSize];
    assert(selfList != NULL);                    //capture programming error
    for (int i = 0; i < selfLength; i++)
        selfList[i] = otherList.selfList[i];
}

template <class Type>
//destructor
ArrayList<Type>::~ArrayList() {
    delete[] selfList;
}

template <class Type>
const ArrayList<Type>& ArrayList<Type>::operator=(const ArrayList<Type>& otherList) {
    if (this != &otherList) {
        delete[] selfList;
        selfMaxSize = otherList.selfMaxSize;
        selfLength = otherList.selfLength;
        selfList = new Type[selfMaxSize];
        assert(selfList != NULL);
        for (int i = 0; i < selfLength; i++)
            selfList[i] = otherList.selfList[i];
    }

    return *this;
}

SOURCE FILE: implementation.cpp

/*################################################
# Name: Stephen Razon
# Student ID:
# Date: 170741SEP24
# Filename: implementation.cpp
# Dependency: arrayListImplementation.h
################################################*/

#include <iostream>
#include "ArrayListImplementation.h"

using namespace std;

int main()
{
	ArrayList<int> intList(10);
	int x;
	intList.print();
	cout << intList.isEmpty() << "\n";
	intList.insert(0); intList.insert(10); intList.insert(30);
	intList.print();
	cout << intList.isEmpty() << "\n";
	intList.insertAt(2, 20);
	intList.print();
	intList.insertEnd(40);
	intList.print();
	intList.insertAt(7, 20);
	intList.print();
	intList.insert(20);
	intList.clearList();
	intList.print();
	cout << intList.isFull() << "\n";
	cout << intList.isItemAtEqual(2, 20) << "\n";
	intList.remove(10);
	intList.print();
	intList.removeAt(3);
	intList.print();
	intList.replaceAt(2, 100);
	intList.print();
	cout << intList.seqSearch(30) << "\n";
	intList.retrieveAt(4, x);
	cout << x << "\n";
	ArrayList<int> newIntList(intList);
	cout << "New list contains: ";
	newIntList.print();
	ArrayList<int> list2(10);
	list2 = intList;
	cout << "List 2 contains: ";
	list2.print();

	/*ArrayList<char> charList(10);
	char x;
	charList.print();
	cout << charList.isEmpty() << "\n";
	charList.insert('A'); charList.insert('B'); charList.insert('D');
	charList.print();
	cout << charList.isEmpty() << "\n";
	charList.insertAt(2, 'C');
	charList.print();
	charList.insertEnd('E');
	charList.print();
	charList.insertAt(7, 'Z');
	charList.print();
	charList.insert('B');
	//charList.clearList();
	//charList.print();
	cout << charList.isFull() << "\n";
	cout << charList.isItemAtEqual(2, 'C') << "\n";
	charList.remove('B');
	charList.print();
	charList.removeAt(0);
	charList.print();
	charList.replaceAt(1, 'O');
	charList.print();
	cout << charList.seqSearch('Z') << "\n";
	charList.retrieveAt(0, x);
	cout << x << "\n";
	ArrayList<char> newCharList(charList);
	cout << "New list contains: ";
	newCharList.print();
	ArrayList<char> list2(10);
	list2 = newCharList;
	cout << "List 2 contains: ";
	list2.print();*/

	return 0;
}