#include<iostream.h>
#include<stdio.h>
typedef struct node
{
int value; //value stored in the node
node *next; //ukazatel kym sledvashtia element
node *prev; //ukazatel kym predishnia element
} node;
node *front; //ukazatel kym nachaloto na spisyka
node *back; //ukazatel kym kraia na spisyka
// prototipi (deklaracii) na vsichki izpolzvani funkcii
void insertFront(int value);
void insertBack(int value);
void removeFront();
void removeBack();
void insertBefore(int value,node *nodeB);
void insertAfter(int value,node *nodeA);
void removeBefore(node *nodeB);
void removeAfter(node *nodeA);
void removeNode(node *newNode);
void insertNodeFromBegin(int value, int n);
void insertNodeFromEnd(int value, int n);
void removeNodeFromBegin(int n);
void removeNodeFromEnd(int n);
void printDListFront();
void printDListBack();
//vmykva element predi nodeB
void insertBefore(int value,node *nodeB)
{
node *newNode;
newNode=new node;
newNode->prev=nodeB->prev;
newNode->next =nodeB;
newNode->value =value;
if(nodeB->prev==NULL)
{
front=newNode;
}
else{
nodeB->prev->next=newNode;
}
nodeB->prev=newNode;
// removeNode(newNode);
}
// vmykva element predi pyrviat element
void insertFront (int value)
{
node *newNode;
if(front==NULL)
{
newNode=new node;
front=newNode;
back =newNode;
newNode->prev=NULL;
newNode->next=NULL;
newNode->value=value;
}
else
{
insertBefore(value,front );
}
}
// vmykva element sled nodeB
void insertAfter(int value,node *nodeB)
{
node *newNode;
newNode=new node;
newNode->next= nodeB->next ;
newNode->prev =nodeB;
newNode->value =value;
if(nodeB->next==NULL)
{
back =newNode;
}
else{
nodeB->next->prev=newNode;
}
nodeB->next=newNode;
}
// vmykva element sled poslednia element
void insertBack (int value)
{
if(back==NULL)
{
// cout<<"insert at back";
insertFront(value);
}
else
{
// cout<<"insert at back";
insertAfter(value,back );
}
}
//trie nachalnia element
void removeFront ()
{
removeNode(front);
}
//trie poslednia element
void removeBack()
{
removeNode(back);
}
//trie predi posochenia element
void removeBefore(node *nodeB)
{
if(nodeB->prev==front)
{
front=nodeB;
front->prev=NULL;
}
else
{
removeNode(nodeB->prev);
}
}
//trie sled posochenia element
void removeAfter(node *nodeA)
{
if(nodeA->next==back)
{
back=nodeA;
back->next=NULL;
}
else
{
removeNode(nodeA->next);
}
}
//trie posochenia element
void removeNode(node *nodeToRemove)
{
if(nodeToRemove==front)
{
front=front->next;
front->prev=NULL;
}
else if (nodeToRemove==back)
{
back=back->prev;
back->next=NULL ;
}
else
{
nodeToRemove->prev->next=nodeToRemove->next;
nodeToRemove->next->prev=nodeToRemove->prev;
}
}
//dobavia sled "n"-ia element, zapochvaiki otnachalo
void insertNodeFromBegin(int value, int n)
{
node *nodeToInsert = front;
int i;
if (n==0 && front == NULL){
insertFront(value);
return;
}
if (n>0 && front == NULL){
cout<<"spisyka ima po malko ot "<<n<<" elementi"<<endl;
return;
}
for (i=0;i < n-1;i++)
{
nodeToInsert=nodeToInsert->next;
if(nodeToInsert==NULL){
cout<<"spisyka ima po malko ot "<<n<<" elementi"<<endl;
// tuk "return" e zadyljitelen
return;
}
}
insertAfter(value,nodeToInsert);
}
//dobavia predi "n"-ia element, zapochvaiki otkraia
void insertNodeFromEnd(int value, int n)
{
node *nodeToInsert = back;
int i;
if (n==0 && back == NULL){
insertFront(value);
return;
}
if (n>0 && back == NULL){
cout<<"spisyka ima po malko ot "<<n<<" elementi"<<endl;
return;
}
for (i=0;i < n-1;i++)
{
nodeToInsert=nodeToInsert->prev;
if(nodeToInsert==NULL){
cout<<"spisyka ima po malko ot "<<n<<" elementi"<<endl;
// tuk "return" e zadyljitelen
return;
}
}
// if(nodeToInsert->prev == NULL){
// insertBefore(value,front);
// }
// else{
insertBefore(value,nodeToInsert);
// }
}
//trie "n"-ia element, zapochvaiki otnachalo
void removeNodeFromBegin(int n)
{
node *nodeToRemove = front;
int i;
for (i=0;i < n-1;i++)
{
nodeToRemove=nodeToRemove->next;
if(nodeToRemove==NULL){
cout<<"spisyka ima po malko ot "<<n<<" elementi"<<endl;
// tuk "return" e zadyljitelen
return;
}
}
removeNode(nodeToRemove);
}
//trie "n"-ia element, zapochvaiki otkraia
void removeNodeFromEnd(int n)
{
node *nodeToRemove = back;
int i;
for (i=0;i < n-1;i++)
{
nodeToRemove=nodeToRemove->prev;
if(nodeToRemove==NULL){
cout<<"spisyka ima po malko ot "<<n<<" elementi"<<endl;
// tuk "return" e zadyljitelen
return;
}
}
removeNode(nodeToRemove);
}
//Pechata spisyka ot nachaloto
void printDListFront()
{
node* p1;
p1= front;
// cout<<"\n-----\n";
cout<<"\n Spisyka sega e:\n";
// cout<<"Queue\n";
// cout<<"-----\n";
while(p1!=NULL)
{
cout<<" |"<<p1->value<<"|";
p1=p1->next;
}
cout<<endl;
}//
// Pechata spisyka otzad napred
void printDListBack()
{
node* p1;
p1= back;
// cout<<"\n-----\n";
cout<<"\n Spisyka v obraten red sega e:\n";
// cout<<"Queue\n";
// cout<<"-----\n";
while(p1!=NULL)
{
cout<<" |"<<p1->value<<"|";
p1=p1->prev;
}
cout<<endl;
}//
void main()
{
int a,val;;
front=NULL;
back=NULL;
a = 0;
val= 12;
cout << "\nShte dobavim element sys stoinost = "<<val
<<" sled element nomer "<<a
<<" ot nachaloto\n";
insertNodeFromBegin(val, a);
printDListFront ();
a = 1;
val= 13;
cout << "\nShte dobavim element sys stoinost = "<<val
<<" predi element nomer "<<a
<<" ot kraia\n";
insertNodeFromEnd(val, a);
printDListFront ();
getchar();
insertBack(8);
// printDListFront ();
insertBack(5);
// printDListFront ();
insertBack(6);
// printDListFront ();
insertFront(1) ;
// printDListFront ();
insertFront(3) ;
// printDListFront ();
insertBack(7);
printDListFront ();
printDListBack ();
getchar();
a = 7;
cout << "\nShte iztriem element nomer "<<a
<<" ot nachaloto\n";
removeNodeFromBegin(a);
printDListFront ();
getchar();
a = 6;
cout << "\nShte iztriem element nomer "<<a
<<" ot kraia\n";
removeNodeFromEnd(a);
printDListFront ();
a = 2;
val= 12;
cout << "\nShte dobavim element sys stoinost = "<<val
<<" sled element nomer "<<a
<<" ot nachaloto\n";
insertNodeFromBegin(val, a);
printDListFront ();
a = 7;
val= 18;
cout << "\nShte dobavim element sys stoinost = "<<val
<<" predi element nomer "<<a
<<" ot kraia\n";
insertNodeFromEnd(val, a);
printDListFront ();
removeFront();
printDListFront ();
removeBack();
printDListFront ();
}
