#include <iostream>
#include <cstring>
using namespace std;

struct Node{
 struct Node *prev;
 char name[20];
 struct Node *next;
};

struct DLinkedList{
 struct Node *left;
 struct Node *right;
 struct Node *data;
 int len;
};

void Create_Node(DLinkedList &DLL);
Node* Input_Node(DLinkedList &DLL, char* value);
Node* Insert_After(DLinkedList &DLL, char* front_node, char* value);
Node* Search_Node(DLinkedList &DLL, char* value);
void Delete_Node(DLinkedList &DLL, char* value);
Node* Invert_Node(DLinkedList &DLL);
void Concatenate_Node(DLinkedList &DLL, DLinkedList &DLL2, DLinkedList &DLL3);
void Print_Node(DLinkedList &DLL);

int main(void)
{ 
 int n;
 struct DLinkedList DLL1;
 struct DLinkedList DLL2;
 struct DLinkedList DLL3;
 char name1[30];
 char name2[30];
 Create_Node(DLL1);
 Create_Node(DLL2);
 
 while(1)
 {
  cout << "───────────────" << endl;
  cout << "1. Creat Doubly Linked List 1" << endl;
  cout << "2. Creat Doubly Linked List 2" << endl;
  cout << "3. Insert Data " << endl;
  cout << "4. Search Data" << endl;
  cout << "5. Delete Data" << endl;
  cout << "6. Invert Data" << endl;
  cout << "7. Concatenate Data" << endl;
  cout << "8. Print Doubly Linked List" << endl;
  cout << "───────────────" << endl;
  cout << "Select number : ";
  cin >> n;
  switch(n)
  {
  case 1:
   cout << "Input Data : ";
   cin >> name1;
   Input_Node(DLL1, name1);
   break;
  case 2:
   cout << "Input Data : ";
   cin >> name1;
   Input_Node(DLL2, name1);
   break;
  case 3:
   cout << "What Node After? : ";
   cin >> name1;
   cout << "What Node Insert? : ";
   cin >> name2;
   Insert_After(DLL1, name1, name2);
   break;
  case 4: 
   cout << "Input Data : ";
   cin >> name1;
   Search_Node(DLL1, name1);
   break;
  case 5:
   cout << "Delete Data : ";
   cin >> name1;
   Delete_Node(DLL1, name1);
   break;
  case 6:
   cout << "Invert Node" << endl;
   Invert_Node(DLL1);
   break;
  case 7:
   cout << "Concatenate Node" << endl;
   Concatenate_Node(DLL1, DLL2, DLL3);
   break;
  case 8:
   cout<<"───────────────"<<endl;
   Print_Node(DLL1);
   cout<<"───────────────"<<endl;
   break;
  case 9:
   break;
  }
  
  if(n == 9) break;
 }
 
 return 0;
}

void Create_Node(DLinkedList &DLL)
{
 DLL.left = new Node;
 DLL.right = new Node;
 
 DLL.left->next = DLL.right;
 DLL.left->prev = DLL.left;
 
 DLL.right->next = DLL.right;
 DLL.right->prev = DLL.left;
 
 DLL.len = 0;
 DLL.data = NULL;
}

Node* Input_Node(DLinkedList &DLL, char* value)
{
 DLL.data = new Node;
 
 DLL.data->next = DLL.right;
 DLL.data->prev = DLL.right->prev;
 
 DLL.data->prev->next = DLL.data;
 DLL.right->prev = DLL.data;
 DLL.len++;
 strcpy(DLL.data ->name, value);
 
 return DLL.data;
}

Node* Insert_After(DLinkedList &DLL, char* front_node, char* value)
{
 Node* new_Node = new Node;
 int i;
 
 DLL.data = DLL.left->next;
 for(i=0; i<DLL.len; i++)
 {
  if(strcmp(DLL.data->name, front_node)==0) break;
  DLL.data = DLL.data->next;
 }
 
 new_Node->next = DLL.data->next;
 DLL.data->next->prev = new_Node;
 
 new_Node->prev = DLL.data;
 DLL.data->next = new_Node;
 
 DLL.len++;
 strcpy(new_Node->name, value);
 
 return DLL.data;
}

Node* Search_Node(DLinkedList &DLL, char* value)
{
 int i;
 DLL.data = DLL.left->next;
 
 for(i=0 ; i<DLL.len; i++)
 { 
  if(strcmp(DLL.data->name, value)==0) 
  {
   cout << value << " is in " << DLL.len << " Node" << endl;
  }
  DLL.data = DLL.data->next;
 }
 
 return DLL.data;
}
void Delete_Node(DLinkedList &DLL, char* value)
{
 int i=0;
 DLL.data = DLL.left->next;
 
 for(i=0 ; i<DLL.len; i++){
  if(strcmp(DLL.data->name, value)==0)
  {
   DLL.data->prev->next = DLL.data->next;
   DLL.data->next->prev = DLL.data->prev;
   
   delete DLL.data;
   DLL.len--;
   break;
  }
  
  DLL.data = DLL.data->next;
 }
}

Node* Invert_Node(DLinkedList &DLL)
{
 int i;
 DLinkedList p;
 DLinkedList temp;
 p = DLL;
 
 for(i=p.len; i<=0; i--){
  p.data->prev = p.left;
  p.data->next = temp.data;

  temp.data->prev = p.data;
  temp.data->next = temp.right;

  p= temp;
 }
 
 p.data = p.left->next;
 
 for(i=p.len; i<=0; i--)
 {
  cout << i+1 << " " << p.data->name << endl;
  p.data = p.data->next;
 }
 
 DLL = p;
 return DLL.data;
}

void Concatenate_Node(DLinkedList &DLL, DLinkedList &DLL2, DLinkedList &DLL3)
{
 int i;
 
 if(DLL.data->name == NULL){
  DLL3 = DLL2;
  cout << DLL3.data->name << endl;
 }
 else{
  DLL3 = DLL;
  if(DLL2.data->name != NULL)
  {
   DLL3.data = DLL3.left->next;
   
   for(i=0; i<DLL3.len; i++)
   {
    cout << i+1 << " " << DLL3.data->name << endl;
    DLL3.data = DLL3.data->next;
   }
  }
  DLL2.data = DLL2.left->next;
  
  for(i=0; i<DLL2.len; i++)
  {
   cout << i+1 << " " << DLL2.data->name << endl;
   DLL2.data = DLL2.data->next;
  }
 }
}

void Print_Node(DLinkedList &DLL)
{
 int i;
 DLL.data = DLL.left->next;
 
 for(i=0; i<DLL.len; i++)
 {
  cout << i+1 << " " << DLL.data->name << endl;
  DLL.data = DLL.data->next;
 }
}


;;;;;;;;;;;;