Question

class DoubleLinkedList {

public:

//Implement ALL following methods.

//Constructor.

DoubleLinkedList();

//Copy constructor.

DoubleLinkedList(const DoubleLinkedList & rhs);

//Destructor. Clear all nodes.

~DoubleLinkedList();

// Insert function. Returns true if item is inserted,

// false if the item it a duplicate value

bool insert(int x);

// Removes the first occurrence of x from the list,

// If x is not found, the list remains unchanged.

void remove(int x);

//Assignment operator.

const DoubleLinkedList& operator=(const DoubleLinkedList & rhs);

private:

struct node{

int data;

node* next;

node* prev;

};

node* head;

node* tail;

};

For the double linked list class above, implement all of the methods.

Answer 1

Complete code in C++:-

I've added main function just for testing purpose, its not part of your 'DoubleLinkedList' class, you can remove it from code.

#include <bits/stdc++.h>

using namespace std;

class DoubleLinkedList {

private:
   typedef struct node{
       int data;
       struct node* next;
       struct node* prev;
   }node;
   node* head;
   node* tail;

public:
   //Implement ALL following methods.
   //Constructor.
   DoubleLinkedList();
   //Copy constructor.
   DoubleLinkedList(const DoubleLinkedList & rhs);
   //Destructor. Clear all nodes.
   ~DoubleLinkedList();
   // Insert function. Returns true if item is inserted,
   // false if the item it a duplicate value
   bool insert(int x);
   // Removes the first occurrence of x from the list,
   // If x is not found, the list remains unchanged.
   void remove(int x);
   void print();
   //Assignment operator.
   const DoubleLinkedList& operator=(const DoubleLinkedList & rhs) {
       return rhs;
   }
};

DoubleLinkedList::DoubleLinkedList() {
   // Default constructor, Initialize as NULL
   this->head = NULL;
   this->tail = NULL;
}

DoubleLinkedList::DoubleLinkedList(const DoubleLinkedList & rhs) {
   // Making new copy of rhs.
   this->head = NULL;
   this->tail = NULL;
   node *temp = rhs.head;
   // Copying node by node.
   while(temp != NULL) {
       insert(temp->data);
       temp = temp->next;
   }
}

DoubleLinkedList::~DoubleLinkedList() {
   // Destructor, deleting head and tail pointer.
   delete this->head;
   delete this->tail;
}

bool DoubleLinkedList::insert(int x) {
   // Creating new node with data.
   node *p1 = (node*)malloc(sizeof(node));
   p1->data = x;
   p1->next = NULL;
   p1->prev = NULL;
   // If currently list is empty.
   if(this->head == NULL) {
       this->head = p1;
       this->tail = this->head;
       return true;
   }
   // Otherwise add this new node in the end of list.
   node *temp = this->head;
   while(temp) {
       // If node is present return false.
       if(temp->data == x) {
           return false;
       }
       temp = temp->next;
   }
   // else add new node and return true.
   temp = p1;
   temp->prev = this->tail;
   this->tail->next = temp;
   this->tail = temp;
   return true;
}

// Remove specified node from the list.
void DoubleLinkedList::remove(int x) {
   node *temp = this->head;
   while(temp) {
       // If mnode is found
       if(temp->data == x) {
           // If node is internal node.          
           if(temp->prev && temp->next) {
               temp->prev->next = temp->next;
           }
           // If node is one the terminal node, head or tail.
           else if(temp->prev){
               this->tail = temp->prev;
               this->tail->next = NULL;
           }
           else if(temp->next) {
               this->head = this->head->next;
               this->head->prev = NULL;
           }
           // If node is the single presnt in the list.
           else {
               this->head = NULL;
               this->tail = NULL;
           }
           // Delete node.
           delete temp;
           break;
       }
       temp = temp->next;
   }
}

void DoubleLinkedList::print() {
   node *temp = this->head;
   while(temp) {
       cout << temp->data << " ";
       temp = temp->next;
   }
   cout << '\n';
}

int main(void) {
   DoubleLinkedList d1;
   d1.insert(5);
   d1.insert(2);
   d1.insert(3);
   d1.insert(4);
   d1.insert(5);
   cout << "Original list: ";
   d1.print();
   DoubleLinkedList d2 = d1;
   cout << "Copy of original list using Assignment: ";
   d2.print();
   d2.remove(2);
   cout <<"Removed 2 form the copy list: ";
   d2.print();
   d2.insert(49);
   cout <<"Inserted 49 in the copy list: ";
   d2.print();
   cout << "Original list: ";
   d1.print();
   DoubleLinkedList d3(d1);
   cout << "Copy of original list using Copy constructor: ";
   d3.print();
   return 0;
}

Screenshot of output:-