CREATION OF DOUBLY LINKEDLIST
In computer science, a doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes' previous and next links respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.
A doubly-linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.
To create doubly linklist :-
In node class we have maintained two pointers prev and next.
next pointer points to next node and prev pointer points to previous node.
There is data which store integer value.
doubly link list code is :-/*
Creation of doubly linklist
Methods are :
addtohead();
addtotail();
addinbetween();
deletefromfront();
deletefromlast();
deletefrommiddle();
display();
reversedisplay(); //display's linklist in reverse order.
@author: Vikas Bek
*/
#include<iostream>
using namespace std;
void inputfun();
class llist{
class node{
public:
node *next;
node *prev;
int data;
node(){
data=0;
next=NULL;
prev=NULL;
}
node(int value,node *p,node* n){
data=value;
prev=p;
next=n;
}
int getdata(){
return data;
}
};
public :
node *head,*tail;
llist(){
head=NULL;
tail=NULL;
}
void addtotail(int);
void addtohead(int);
void addinbetween(int);
void deletefromfront();
void deletefromlast();
void deletefrommiddle();
void display();
void reversedisplay();
};
void llist::addtohead(int value){
node*temp=new node(value,tail,head);
if(head==0){
head=tail=temp;
temp->prev=NULL;
temp->next=NULL;
}else{
temp->next=head;
head->prev=temp;
temp->prev=NULL;
head=temp;
}
}
void llist::addtotail(int x){
node *temp=new node(x,head,head);
if(head==NULL){
head=temp;
tail=temp;
temp->next=NULL;
temp->prev=NULL;
}else{
tail->next=temp;
temp->prev=tail;
tail=temp;
tail->next=NULL;
}
cout<<"inserted"<<endl;
}
void llist::addinbetween(int value){
cout<<"Enter the position where you want to insert element"<<value<<endl;
int pos;
cin>>pos;
node *temp=new node(value,tail,head);
node *temp_pos=head;
if((pos==1)){
addtohead(value);
}else if((pos==2)&&(head->next==NULL)){
addtotail(value);
}else if((pos>1)&&(temp_pos==NULL)){
return;
}else{
node *temp_pos=head;
for(int i=2;i<pos;i++){
if((i<pos)&&(temp_pos->next==NULL)){
cout<<"Invalid position: "<<endl;
return;
}
if(temp_pos->next!=NULL)
temp_pos=temp_pos->next;
}
if(temp_pos->next==NULL){
addtotail(value);
}else{
temp->next=temp_pos->next;
temp_pos->next->prev=temp;
temp->prev=temp_pos;
temp_pos->next=temp;
}
}
}
void llist::deletefromfront(){
if(head==NULL){
cout<<"no element to delete"<<endl;
}
else if((head==tail)&&(head!=NULL)){
head=NULL;
tail=NULL;
}else{
node*temp=head;
head=temp->next;
head->prev=NULL;
temp=NULL;
}
cout<<"deleted "<<endl;
}
void llist::deletefromlast(){
if(head==NULL){
cout<<"no element to delete"<<endl;
}
else if((head==tail)&&(head!=NULL)){
head=NULL;
tail=NULL;
}else{
tail=tail->prev;
tail->next->prev=NULL;
tail->next=NULL;
}
cout<<"deleted "<<endl;
}
void llist::deletefrommiddle(){
int pos;
cout<<"Enter the position: "<<endl;
cin>>pos;
if((pos>=1)&&(head==NULL)){
cout<<"no element to delete"<<endl;
}else if((pos==1)&&(head->next==NULL) ){ //to delete if there is only one element in linklist
head=NULL;
tail=NULL;
}else{
node*temp=head;
for(int i=1;i<pos-1;i++){
if((temp->next->next==NULL)&&(i<pos-1)){
cout<<"Invalid position: "<<endl;
return;
}else {
temp=temp->next;
}
}
if(temp->next->next!=NULL){
if((temp==head)&&(pos==1)){
head=temp->next;
head->prev=NULL;
temp=NULL;
}else{
temp->next=temp->next->next;
temp->next->next->prev=temp;
}
}else{
tail->prev=NULL;
tail=temp;
temp->next=NULL;
}
}
}
void llist::display(){
cout<<"element in the linked list are"<<endl;
node *t=head;
while(t!=NULL){
cout<<t->data<<" ";
t=t->next;
}
cout<<endl;
}
void llist::reversedisplay(){
cout<<"element in ((reverse)"<<endl;
node *t=tail;
while(t!=NULL){
cout<<t->data<<" ";
t=t->prev;
}
cout<<endl;
}
int main(){
inputfun();
return 0;
}
void inputfun(){
llist ll;
//char rep='y';
int ch=0;
do{
int data;
cout<<"************************MENU*******************"<<endl;
cout<<"1. add to tail"<<endl;
cout<<"2. add to head"<<endl;
cout<<"3. add in between"<<endl;
cout<<"4. delete from front. "<<endl;
cout<<"5. delete from last. "<<endl;
cout<<"6. delete from middle. "<<endl;
cout<<"7. display linklist"<<endl;
cout<<"8. To exit \n Enter choice"<<endl;
cout<<"Enter choice"<<endl;
cin>>ch;
switch(ch){
case 1: cout<<"add element in the linklist..."<<endl;
cin>>data;
ll.addtotail(data);
ll.display();
ll.reversedisplay();
break;
case 2: cout<<"add element at the beginning...."<<endl;
cin>>data;
ll.addtohead(data);
ll.display();
ll.reversedisplay();
break;
case 3: cout<<"add element in middle...."<<endl;
cin>>data;
ll.addinbetween(data);
ll.display();
ll.reversedisplay();
break;
case 4: cout<<"delete from front in link list"<<endl;
ll.deletefromfront();
ll.display();
ll.reversedisplay();
break;
case 5: cout<<"delete from last: "<<endl;
ll.deletefromlast();
ll.display();
ll.reversedisplay();
break;
case 6: cout<<"delete from middle: "<<endl;
ll.deletefrommiddle();
ll.display();
ll.reversedisplay();
break;
case 7: cout<<"display..."<<endl;
ll.display();
ll.reversedisplay();
break;
case 8: cout<<"To EXIT!!!!!"<<endl;
exit(0);
default: cout<<"wrong choice: "<<endl;
}
}while(ch!=8);//while(rep=='y');
}
No comments :
Post a Comment