Linear List Program

This is program on linear list with formula based representation.

#include<iostream>
using namespace std;
template <class T>
class llist
{
	private:
		T *a;
		int l,size;
	public:
		llist(int k);
		~llist();
		bool isempty();
		bool isfull();
		void insert(int i,T x);
		bool del(int i,T &x);
		bool find(int i,T &x);
		int search(T x);
		void disp();
		int length();
};
template <class T>
llist<T>::llist(int k)
{
	size=k;
	a=new T[size];
	l=0;
}
template <class T>
int llist<T>::length()
{
	return l;
}
template <class T>
bool llist<T>::isempty()
{
	return l==0;
}
template <class T>
bool llist<T>::isfull()
{
	return l==size;
}
template <class T>
llist<T>::~llist()
{
	delete[] a;
}
template <class T>
bool llist<T>::find(int i,T &x)
{
	if(i<=l&&i>=1)
 	{	
		x=a[i-1];
		return true;
	}
  	return false;
}
template <class T>
int llist<T>::search(T x)
{
	for(int i=0;i<l;i++)
	{
        	if(a[i]==x)
	        return ++i;
 	}
	return 0;
}
template <class T>
void llist<T>::insert(int i,T x)
{
	if(isfull())
		cout<<"list is full";
	else
	{
		for(int j=l-1;j>=i;j--)
		a[j+1]=a[j];
	        a[i]=x;
	   	l++;
	}
}
template <class T>
bool  llist<T>::del(int i,T &x)
{
	if(find(i,x))
	{
		for(int j=i;j<l;j++)
			a[j-1]=a[j];
		l--;
		return true;
	}
	return false;
}
template <class T>
void llist<T>::disp()
{
	int i;
	for(i=0;i<l;i++)
	cout<<a[i]<<" ";
}

int main()
{
	int ch,k,x,i,l=0;
	cout<<"\nenter size of list: ";
	cin>>k;
	llist<int> obj(k);
	while(1)
	{
		cout<<"\n1.isempty\n2.isfull\n3.find\n4.search\n";
		cout<<"5.length\n6.insert\n7.display";
		cout<<"\n8.delele\n9.exit";
		cout<<"\n\t\tenter choice: ";
		cin>>ch;
		switch(ch)
		{
			case 1:	
				if(obj.isempty())
					cout<<"List is empty";
				else
					cout<<"List is not empty ";
				break;
			case 2:
				if(obj.isfull())
					cout<<" List is full";
				else
					cout<<"List is not full";
				break;
			case 3:
				cout<<" Enter location: ";
				cin>>i;
				if(obj.find(i,x))
					cout<<x<<" is found at "<<i;
				else
					cout<<"Location is incorrect ";
				break;
			case 4:
				cout<<"Which element you want to search:";
				cin>>x;
				i=obj.search(x);
				if(i)
					cout<<"Element found at location: "<<i;
				else
					cout<<"Element not found in the list";
				break;
			case 5:
				cout<<"Length is : "<<obj.length();
				break;
			case 6:
				cout<<"Enter an element to insert: ";
				cin>>x;
				obj.insert(l,x);
				l++;
				break;
			case 7:
				obj.disp();
				break;
			case 8:
				cout<<"Enter index of element to delete: ";
				cin>>i;
				if(obj.del(i,k))
				{
					cout<<" deleted element is :"<<k;
					l--;
				}	
				else 
					cout<<"Element not found";
				break;
			case 9: 
				exit(0);
			default:	
				continue;
		}
	}
}
		
			

Abstract data type for Linear list

I think most of you remember what’s this abstract data type if you haven’t then refer to the previous posts.Now let us see this abstract data type for Linear list.

ABSTRACT_DATA_TYPE  LinearList {

INSTANCES:-
Ordered finite collections of zero or more elements.

OPERATIONS:-
Create():            create an empty linear list
Destroy():          erase the list
IsEmpty():          return true if empty, false otherwise
Length():            return the list size
Find(k,x):           return the kth element of the list in x
Search(x):          return the position of x in the list
Delete(k,x):       delete the kth element and return it in x
Insert(k,x):        insert x just after the kth element
Output(out):     put the list into the output stream out

};

Here abstact data type may be class.

Implementation of Linear list

LINEAR LIST :-Linear list is a data object whose instances are of form (e1,e2,e3,….,eN) where,N is length of the list.

Ex:words sorted in dictionary order,list of marks in descending order…

Here  linear list is a data structure to implement it we use four data representations which are:

1.Formula-based :-Uses a mathematical fornula to determine where to store each element of list(i.e, the memory address).We use arrays in this since their memory locations are in consecutive positions.

2.Link-based :-The elements of list may be stored in any arbitrary set of locations since each element has an explicit pointer(or link)to the next element.

3.Indirect addressing :-The elements of list may be stored in any arbitrary locations since we maintain a table such that the Mth table entry tells us where the Mth element is stored.

4.Simulated pointer :-Similar to link-based representation but integers replace the C++ pointers.

So i think many of you guys&gals came to know what is meant by linear list and how we implement it using different data representations.So don’t get confused that linear list and linked list are two types of data structures but linear list is a data structure and linked list is implementation of linear list using link-based representation.

I am much awaiting to listen your comments,requests for programs and suggestions so just feel free to write to me.