Answer to Question #268299 in C++ for zain

Question

Create a class Node with

a.      attributes data, next and previous pointer

b.      accessors and mutators for this class

c.      constructor and destructor

d.     function called display.

1. insert a node at first ,

2. overload to Insert a node at last

3. overload to Insert at specified position of double linked list. E.g if the position number is 6, it is inserted between node at position 5 and 7. If position number is greater than the size of list, it is prompted that the position number does not exist and therefore is being inserted at end.

4. eliminate duplicates from doubly linked list

5. delete a node from first,

6. overload to delete a node from last

7. overload to delete at specified position of double linked list. E.g if the position number is 6, it is deleted from between node at position 5 and 7. If position number is greater than the size of list, it is prompted that the position number does not exist and therefore is being deleted from the end.

Answer 1

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
class Node{
    public:
    int data;
    Node *next, *prev;
    Node();
    Node(int);
    int getData(){
        return data;
    }
    void setData(int data){
        this->data = data;
    }
    ~Node(){}
};
Node::Node(){
    next = NULL;
    prev = NULL;
}
Node::Node(int data){
    this->data = data;
    next = NULL;
    prev = NULL;
}
class DoublyLinkedList{
    Node *head, *tail;
    int size;


    public:
    DoublyLinkedList();
    //insert at head
    void insert(int);
    //insert at a specified position
    void insert(int, int);
    //delete at tail
    void remove();
    //delete at a specified position
    void remove(int);
    void eliminateDuplicates();
    //counts the number of occurrences of a specified data
    int find(int);
    //prints the list
    void show();
    int length(){return size;}
};
DoublyLinkedList::DoublyLinkedList(){
    head = NULL;
    tail = NULL;
    size = 0;
}
void DoublyLinkedList::insert(int data){
    if(head == NULL){
        head = new Node(data);
        head->next = tail;
        head->prev = tail;
        tail = head;
        size++;
    }
    else{
        tail->next = new Node(data);
        tail->next->prev = tail;
        tail = tail->next;
        tail->next = head;
        head->prev = tail;
        size++;
    }
}
void DoublyLinkedList::remove(){
    if(tail == head){
        head = NULL;
        delete tail;
        tail = NULL;
        return;
    }
    Node *temp = tail;
    tail = tail->prev;
    tail->next = head;
    size--;
    delete temp;
}
void DoublyLinkedList::remove(int pos){
    if(head != NULL){
        int i = 0;
        Node *temp = head;
        while(temp != NULL && i < pos){
            temp = temp->next;
            i++;
        }
        if(pos > size - 1) return;
        if(pos == 0){
            head = head->next;
            head->prev = NULL;
            size--;
            delete temp;
            return;
        }
        if(pos == size - 1){
            tail = tail->prev;
            tail->next = NULL;
            size--;
            delete temp;
            return;
        }
        temp->prev->next = temp->next;
        temp->next->prev = temp->prev;
        size--;
        delete temp;
    }
}
void DoublyLinkedList::show(){
    Node* curr = head;
    if(curr == NULL) return;
    do{
        cout<<curr->data<<" ";
        curr = curr->next;
    }while(curr != head);
    cout<<endl;
}
void DoublyLinkedList::insert(int data, int index){
    if(index > size - 1){
        cout<<"Position is greater than size of the list...inserting at the end\n";
        insert(data);
        return;
    }
    else if(index == size){
        insert(data);
        return;
    }
    Node *temp = new Node(data);
    Node *curr = head;
    if(index == 0){
        tail->next = temp;
        temp->prev = head;
        temp->next = head;
        head = temp;
        size++;
        return;
    }
    for(int i = 0; i < index - 1; i++){
        curr = curr->next;
    }
    temp->next = curr->next;
    curr->next->prev = temp;
    curr->next = temp;
    temp->prev = curr;
    size++;
}
void DoublyLinkedList::eliminateDuplicates(){
    Node *curr = head;
    if(curr == NULL) return;
    do{
        int count = find(curr->data);
        if(count > 1){
            Node *temp = curr->next;
            while(temp != head){
                if(temp->data == curr->data){
                    Node *temp2 = temp;
                    temp->prev->next = temp->next;
                    temp->next->prev = temp->prev;
                    temp = temp->prev;


                    if(temp2 == head){
                        head = head->next;
                        head->prev = tail;
                        tail->next = head;
                    }
                    if(temp2 == tail){
                        tail = tail->prev;
                        tail->next = head;
                        head->prev = tail;
                    }
                    size--;
                    delete temp2;
                }
                temp = temp->next;
            }
        }
        curr = curr->next;
    }while(curr != head);
    return;
}
int DoublyLinkedList::find(int data){
    Node *temp = head;
    int count = 0;
    do{
        if(temp->data == data){
            count++;
        }
        temp = temp->next;
    }while(temp != head);


    return count;
}
int main(){
    DoublyLinkedList list;
    for(int i = 0; i < 10; i++){
        list.insert(i, 0);
    }
    list.show();
    cout<<"Inserting 4 at position 5\n";
    list.insert(4,5);
    list.show();
    cout<<"Removing duplicates\n";
    list.eliminateDuplicates();
    list.show();
    return 0;
}