Data Structure
LABORATORY
Lab. Sheet Two
Link List
Computer engineering department
Second class
Link List:
#include "stdafx.h"
#include<iostream>
using namespace std;
template<class T>
class Linkedlist
{
private:
struct Node
{ T data ; // data item
Node *next; // points to next node in the list
};
Node *head; // head points to first node
int count; // current number of nodes in the list
public :
Linkedlist() // constructor
{ head=NULL ;
count= 0 ;
}
void insertFirst(T item)
{
Node *p=new Node ;// create new node
p->data = item ;
p->next= head ; // new node refers to old head
head = p ; // new node refers to new node
count++ ;
}
void insertAfter(T item ,T key)
{
Node *p = find(key); // get the address of key
if(p== NULL)
cout<<key<<" key is not found";
else
{
Node *q= new Node ; // create new node
q->data = item ;
q->next = p->next ; // new node next refers to
p->next
p-> next = q ; // p->next refers to new node
count++ ;
}
}
void deleNode(T item)
{
Node *p ,*prevNode;
if(isEmpty())
{ cout<<"List is empty : no deletion " <<endl;
return;
}
if( head->data == item ) // if it is the first
node
{
p= head ; // p saves reference to head
head=head->next ;
count--;
}
else
{
p=head;
while( p!=NULL && p->data != item)
{
prevNode= p ;
p=p->next ;
}
if ( p!= NULL)
{
prevNode->next= p->next ; count--;}
else
cout<<item<<" not found : deletion is
void ." << endl;
}
}
void displayList()
{
Node *p=head; // assign address of head to p
cout<<"\nLinked List: ";
while(p!=NULL) // start at beginning of list until
end of list
{
cout<<p->data<<" -> " ; // print data
p= p-> next ; //advance to next node
}
cout<<"null" << endl;
}
//if the 'key' matches with list node data , function
returns address of key ,else null
Node *find( T key)
{
Node *p=head ;
while(p!= NULL)
{
if( p->data == key ) return p;
p=p->next ;
}
return p ;
}
bool isEmpty()
{
if(count==0) return true ;
else return false;
}
int size()
{ return count ;}
};
void main()
{
Linkedlist<int> list ;
list.insertFirst(55);
list.displayList();
cout<<"new List: "<<endl;
list.insertAfter (77,33);
list.displayList();
cout<<endl;
list.deleNode(55) ;
list.displayList();
list.deleNode(31) ;
list.displayList();
list.deleNode(33) ;
list.displayList();
cout<<"size = " <<list.size() << endl;
}
Lab Exercise:
A new video store in your neighborhood is about to open. However, it does not
have a program to keep track of its videos and customers. The store managers want
someone to write a program for their system so that the video store can function.
The program should be able to perform the following operations:
1. Create a list of videos owned by the store.
2. Rent a video; that is, check out a video.
3. Return, or check in, a video.
4. Show the details of a particular video.
5. Print a list of all of the videos in the store.
6. Check whether a particular video is in the store.
Let us write a program for the video store. This example further illustrates the
object oriented design methodology and, it should use Link List data structure.
The video stricter component are:
Name of the movie
Names of the main leading actor
Name of the producer
Name of the director
Name of the production company
Number of copies in the store
Note: add any other functions or classes that your program may need.
Exercises:
1. Create Link list data structure with doubly links,
2. Create Link list data structure that has sorted insert function.
3. Create Circular Link List.
