Question

Hi!

I 'm writing a code for a doubly linked list and this is the header file

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

struct node
{
int data;
node *next,*prev;
node(int d,node *p=0,node *n=0)
{
data=d; prev=p; next=n;
}
};

class list
{
node *head,*tail;
public:
list();
bool is_empty();
int size();
void print();
void search();
int search2(int el);
void add_last(int el);
void add_first(int el);
bool add_pos();
bool delete_first();
bool delete_last();
void delete_pos(int pos);
void delete_el();
void add_sorted();
};

i want to write a function that split the list into 2 list from a specific number

ex. 5 4 7 2 8

if I spilt it from number 4 it will be 5 in the first list and 7 2 8 in the second list and number 4 will go to the List that contains fewer element so first list will have 5 4 and second list 7 2 8 if the have the same number of element the number that you were separated from it goes to any list it does not matter

Answer 1

// header file

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

struct node
{
   int data;
   node *next,*prev;
   node(int d,node *p=0,node *n=0)
   {
       data=d; prev=p; next=n;
   }
};

class list
{
   node *head,*tail;
public:
   list();
   bool is_empty();
   int size();
   void print();
   void search();
   int search2(int el);
   void add_last(int el);
   void add_first(int el);
   bool add_pos();
   bool delete_first();
   bool delete_last();
   void delete_pos(int pos);
   void delete_el();
   void add_sorted();
  
   // function that splits this list into 2 lists, containing all data from start to first occurrence of elem
   // and other containing all data after elem to end of list
   // elem is inserted in the list with fewer elements. In case of both lists having same number of elements,
   // elem can be inserted in either of list
   // the second list is returned by the function
   list split(int elem); // add it to the class declaration
};

// end of header file

// function that splits this list into 2 lists, containing all data from start to first occurrence of elem
// and other containing all data after elem to end of list
// elem is inserted in the list with fewer elements. In case of both lists having same number of elements,
// elem can be inserted in either of list
// the second list is returned by the function
// add the below function to the implementation file
list list::split(int elem)
{
   list second; // create an empty second list
  
   // list is not empty
   if(!is_empty())
   {
       // set curr to head
       node* curr = head;
       node* pre = NULL; // set pre to node previous to curr
      
       // loop to get the first occurrence of elem in list in curr
       while(curr->data != elem)
       {
           pre = curr;
           curr = curr->next;
       }
      
       if(pre == NULL) // elem is the head node
       {
           // set head of second list to node next to head
           second.head = head->next;
           // list contains more than 1 node
           if(second.head != NULL)
           {
               // update prev of head to null
               second.head->prev = NULL;
               second.tail = tail; // update tail of second to tail of this list
              
               // second list contains only 1 node
               if(second.tail == second.head)
                   second.tail->prev = NULL;
           }  
          
           // make this list an empty list
           head = NULL;
           tail = NULL;
       }
       else if(curr != NULL) // elem in list
       {
           // set next of pre to null
           pre->next = NULL;
          
           // set head of second list to node next to curr
           second.head = curr->next;
          
           // second list is not empty
           if(second.head != NULL)
           {
               second.head->prev = NULL; // update prev of head of second list to null
               second.tail = tail; // update tail of second list to tail of this list
              
               // second list contains only 1 node
               if(second.tail == second.head)
                   second.tail->prev = NULL;
           }  
          
           tail = pre; // update tail of this list to pre
       }
      
       // insert curr's data
       if(curr != NULL)
       {
           if(size() <= second.size()) // size of this list <= size of second list
           {
               add_last(curr->data); // add curr's data at the end of this list
           }
           else // else add curr's data at the end of second list
           {
               second.add_last(curr->data);
           }
       }

       // if curr is null, then no change to this list as elem is not found in list
   }
   return second; // return the second list
}