Abstract Data Type Lists C

Abstract data type Lists C++

Abstract Data Type Lists C

ADT in lists in C++ or sequence is an abstract data type that implements a finite ordered collection of values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a finite sequence; the (potentially) infinite analog of a list is a stream. Lists are a basic example of containers, as they contain other values. Each instance of a value in the list is usually called an item, entry, or element of the list; if the same value occurs multiple times, each occurrence is considered a distinct item. Lists are distinguished from arrays in that lists only allow sequential access, while arrays allow random access.

ADT List Operations

Create an empty list
Destroy a list
Determine whether a list is empty
Determine the number of items in a list
Insert an item at a given position in the list
Delete the item at a given position in the list
Retrieve th item at a given position in the list

C++ Classes

Encapsulation( used to refer to one of two related but distinct notions, and sometimes to the combination) combines an ADT’s data with its operations to form an object

An object is an instance of a class
A class defines a new data type
A class contains data members and
methods (member functions)
By default all members in a class are private.
Encapsulation hides implementation details.

Each class definition is placed in a header file Classname.h

The implementation of a class’s methods are placed in an implementation file Classname.cpp

Constructors- Create and initialize new instances of a class. Invoked when you declare an instance of the class. Have the same name as the class. Have no return type, not even void

Destructor- Destroys an instance of an object when the object’s lifetime ends

C++ Namespaces- A mechanism for logically grouping declarations and definitions into a common

Abstract data type list using array-based implementation

Heather file ADT Lists C++


/*
 * File: lists.h
 * Author: MyCodingLab
 * Code: ADT list - array-based implementation
 * Date: Created on August 26, 2011, 2:59 AM
 *
 */

#ifndef LISTS_H
#define LISTS_H

#include <stdio.h>
#include <iostream>

const int MAX_SIZE = 10;
typedef int ListItemType;

class List
{
public:

 //Default constructor
 List();

 //Default Destructor would be provided by compiler in this case.
 //~List();

//List operations:

 //return True if the list is empty; otherwise returns false
 bool isEmpty() const;

//return the number of items stored in the list.
 int getSize() const;

//Inserts an item into the list at position index.
 void insert(int index, const ListItemType& newItem);

// Deletes an item from the list at a given position.
 void remove(int index);

// Retrieves a list item by position.
 void retrieve(int index) const;

 // Output all elements.
 void print() const;

private:

 // array of list items
 ListItemType items[MAX_SIZE];

//number of items
 int size;

};//end List
 //end file.
#endif /* LISTS_H */

Implementation file ADT Lists C++


#ifndef LISTS_CPP
#define LISTS_CPP

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

using namespace std;

List::List() : size(0)
{
 //initial the array
 for(int k=0; k<MAX_SIZE; k++) items[k]=0;
}//end default constructor

bool List::isEmpty() const
{
 return size == 0;
}//end isEmpty

int List::getSize() const
{
 return size;
}// end getLength

void List::insert(int pos, const ListItemType& newItem)
{
 if( ( pos<0) || (MAX_SIZE<pos ) )
 cout<< pos <<" is out of bound "<<endl;
 else{
 items[pos]= newItem;
 cout<< newItem <<" has been inserted"<< endl;
 size++;
 }//end of if
}// end insert

void List::remove(int pos)
{
 if( ( pos<0) && (MAX_SIZE<pos ) )
 cout<< "position is out of bound "<<endl;
 else{
 items[pos]= 0;
 --size;
 }// end if
}// end remove

void List:: print() const
{
 cout<<"List contains: ";
 for(int k=0; k<MAX_SIZE; k++)
 cout << items[k]<< " ";
 cout<< endl;

}//end print

void List::retrieve(int pos) const
{
 if( ( pos<0) && (MAX_SIZE<pos ) )
 cout<< "position is out of bound "<<endl;
 else{
 if (items[pos]==0) cout<< "Cell is empty"<<endl;
 else cout<< "item at position " << pos << " is: " << items[pos]<<endl;
 }// end if
}// end retrieve
// End file.
#endif /* LISTS_CPP */

Main file ADT Lists C++


#include "lists.cpp"
#include <iostream>

using namespace std;

int main(int argc, char** argv) {

//declare list
 List testList;

 //check if list is empty
 if(testList.isEmpty()==0)
 cout<< "List is not empty"<<endl;
 else cout<< "List is empty"<<endl;

//insert valueslists
 testList.insert(4,10);

 //insert values
 testList.insert(5,15);
 testList.insert(7,33);
 testList.insert(0,86);
 testList.retrieve(0);

 // get the size of list
 cout<< "size is: " << testList.getSize()<< endl;

testList.print();

 return 0;
}//end main

Program Output:


List is empty

10 has been inserted
15 has been inserted
33 has been inserted
86 has been inserted
item at position 0 is: 86
size is: 4
List contains: 86 0 0 0 10 15 0 33 0 0