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;
}Last updated