19:29
Unknown
Algorithm for adding an element (data) to the front of the list list.
1. Declare and initialize necessary variables 2. Create an empty node and assign it to node pointer p. 3. Take input data and assign it to info field of new node i.e. p->info = data; 4. Set next field. i.e. p->next = list; 5. Set list pointer to p i.e. list = p; 6. For next insertion operation, goto step 2
Insertion new node at the end.
1. Declare neccessary variables.
2. Create an empty node and assign it to node pointer p.
3. Insert the data item to info field of newly created node,
i.e. p->info = data;
4. Assign NULL to the next field of newly created node
i.e. p->next = NULL;
5. If list == NULL;
then list = p;
Else
Find the last node of the current list say l.
then l->next = p;
6. For next insertion, goto step 2.
Deletion of the first node
1. Declare the necessary variables
2. If list = NULL
print "Empty list"
Else
p = list
list = p -> next
3. Remove the node p i.e. delete(p)
4. For next deletion, goto step 2
Deletion of the last node
1. Declare necessary variable
2. If list = NULL
print "Empty List"
Else
set p = list
if p->next = NULL
list = NULL
delete(p)
Else
while(p->next!=NULL)
temp = p
p = p->next
temp->next = NULL
delete(p)
3. For next deletion goto step 2
The source code in C++ for whole process include inserting and deleting elements before and after the given node is given below:
/********************************************Program: Linked List using C++by Bibek SubediJune, 29 2011********************************************/#include<iostream>#include<cstdlib>using namespace std;struct node{int info;struct node *next;};class Link{node *list;public:Link();void insert_at_begining(int);void insert_at_end(int);void insert_before_node();void insert_after_node();void delete_at_begining();void delete_at_end();void delete_before_node();void delete_before_after_node(int);node *find_before_node(node*);void display();};Link::Link(){list = NULL;}node *Link::find_before_node(node *p){int count = 0;int count1 = 0;node *temp = new node;temp = list;while(temp!=p){count++;temp=temp->next;}temp = list;while(count1<count-1){count1++;temp = temp->next;}return temp;}void Link::insert_at_begining(int data){node *p = new node;p->info = data;p->next = list;list = p;}void Link::insert_at_end(int data){node *p = new node;node *r = new node;node *q = new node;r = list;p->info = data;p->next = NULL;if(list == NULL){list = p;}else{while(r->next!=NULL){r = r->next;}r->next = p;}}void Link::insert_before_node(){node *p = new node;node *l = new node;node *r = new node;int data1, data2;bool isFound = false;cout<<"Enter the node: ";cin>>data1;p = list;while(p != NULL){if(p->info == data1){isFound = true;break;}l = p;p = p->next;}if(isFound){cout<<"Enter the data to insert:";cin >> data2;r->info = data2;if(p==list){insert_at_begining(data2);}else{l->next = r;r->next = p;}}else{cout<<"\nMember not found\n";}}void Link::insert_after_node(){node *p = new node;node *r = new node;node *l = new node;int data1, data2;bool isFound = false;cout<<"Enter the node: ";cin>>data1;p = list;while(p!= NULL){if(p->info == data1){isFound = true;break;}p = p->next;}if(isFound){cout<<"Enter the data to insert: ";cin>>data2;r->info = data2;if(p->next == NULL){insert_at_end(data2);}else{l = p->next;p->next = r;r->next = l;}}else{cout<<"\nMember not found\n";}}void Link::delete_at_begining(){node *p = new node;if(list == NULL){cout<<"\nList is Empty\n";}else{p = list;list = list->next;delete p;}}void Link::delete_at_end(){node *p = new node;node *l = new node;if(list == NULL){cout<<"\nList is Empty\n";}else{p = list;if(p->next == NULL){list = NULL;delete p;}else{while(p->next!= NULL){l = p;p = p->next;}l->next = NULL;delete p;}}}void Link::delete_before_node(){node *p = new node;node *l = new node;int data1;bool isFound = false;p = list;cout<<"Enter the node: ";cin>>data1;if(p == NULL){cout<<"\nList is Empty"<<endl;exit(0);}while(p!=NULL){if(p->info == data1){isFound = true;break;}l = p;p = p->next;}if(isFound){if(p == list){cout<<"\nIt is the first element\n";}else if(p == list->next){list = p;delete l;}else{find_before_node(l)->next = p;delete l;}}}void Link::display(){node *p = new node;p = list;if(list==NULL){cout<<"\nNothing to Display\n";}else{cout<<"\nThe contents of list\n";while(p!=NULL){cout<<p->info<<endl;p = p->next;}}}int main(){int choice;Link link;while(1){int data;cout<<"\n1. Insert at the begining"<<endl;cout<<"2. Insert at the end"<<endl;cout<<"3. Insert before node"<<endl;cout<<"4. Insert After node"<<endl;cout<<"5. Delete first element"<<endl;cout<<"6. Delete last element"<<endl;cout<<"7. Delete before node"<<endl;cout<<"8. Delete after node"<<endl;cout<<"9. Display"<<endl;cout<<"10. Exit"<<endl;cout<<"Enter the option: ";cin>>choice;switch(choice){case 1:cout<<"\nEnter data to Insert: ";cin>>data;link.insert_at_begining(data);break;case 2:cout<<"Enter data to Insert: ";cin>>data;link.insert_at_end(data);break;case 3:link.insert_before_node();break;case 4:link.insert_after_node();break;case 5:link.delete_at_begining();break;case 6:link.delete_at_end();break;case 7:link.delete_before_node();break;case 8://link.delete_before_after_node(0);break;case 9:link.display();break;case 10:exit(0);break;}}return 0;}
0 comments:
Post a Comment