Answer to Question #239911 in C++ for Rohit

Question

Create a doubly Linked List and perform the following functions to
1)A function insert element at head of list
2)a function insert element at tail of list
3)A function insert element at any position
4)a function delete element at head of list
5)a function delete element at tail of list
6)a function delete element at any position
7) a function to check if list is sorted if not then returns sorted list
8) a function that displays the list
9) a function that reverses the list
Note:
no global declarations
Test the functions inside main

Answer 1

#include <iostream>
#include <algorithm>
using namespace std;
class Node{
    public:
    int data;
    Node *next, *prev;
    Node();
    Node(int);
};
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();
    void append(int);
    void prepend(int);
    void insert(int, int);
    void remove_at(int);
    void remove_at_head();
    void remove_at_tail();
    int len();
    void show();
    void reverse();
    DoublyLinkedList sorted();
};
DoublyLinkedList::DoublyLinkedList(){
    head = NULL;
    tail = NULL;
    size = 0;
}
void DoublyLinkedList::append(int data){
    if(head == NULL){
        head = new Node(data);
        tail = head;
        size++;
    }
    else{
        tail->next = new Node(data);
        tail->next->prev = tail;
        tail = tail->next;
        size++;
    }
}
void DoublyLinkedList::prepend(int data){
    if(head == NULL){
        head = new Node(data);
        tail = head;
        size++;
    }
    else{
        Node *temp = new Node(data);
        temp->next = head;
        head->prev = temp;
        head = temp;
        size++;
    }
}
void DoublyLinkedList::insert(int data, int index){
    if(index == 0){
        prepend(data);
        return;
    }
    if(index == size){
        append(data);
        return;
    }
    if(index + 1 > size) return;
    Node *temp = new Node(data);
    Node *curr = head;
    for(int i = 0; i < index; i++){
        curr = curr->next;
    }
    temp->prev = curr->prev;
    temp->next = curr;
    curr->prev->next = temp;
    curr->prev = temp;
    size++;
}
void DoublyLinkedList::remove_at(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){
            this->remove_at_head();
            return;
        }
        if(pos == size - 1){
            this->remove_at_tail();
            return;
        }
        temp->prev->next = temp->next;
        temp->next->prev = temp->prev;
        size--;
        delete temp;
    }
}
void DoublyLinkedList::remove_at_head(){
    Node *temp = head;
    if(temp != NULL){
        head = head->next;
        head->prev = NULL;
        size--;
        delete temp;
    }
}
void DoublyLinkedList::remove_at_tail(){
    Node *temp = tail;
    if(temp != NULL){
        tail = tail->prev;
        tail->next = NULL;
        size--;
        delete temp;
    }
}
int DoublyLinkedList::len(){
    return size;
}
void DoublyLinkedList::show(){
    Node* curr = head;
    while(curr != NULL){
        cout<<curr->data<<" ";
        curr = curr->next;
    }
    cout<<endl;
}
void DoublyLinkedList::reverse(){
    Node* curr = head, *temp = head;
    while(curr != NULL){
        temp = curr->next;
        curr->next = curr->prev;
        curr->prev = temp;
        curr = temp;
    }
    temp = head;
    head = tail;
    tail = head;
}
DoublyLinkedList DoublyLinkedList::sorted(){
    DoublyLinkedList list;
    Node* curr = head;
    int *arr = new int[size];
    int i = 0;
    while(curr != NULL){
        arr[i] = curr->data;
        curr = curr->next;
        i++;   
    }
    sort(arr, arr + size);
    curr = head;
    i = 0;
    while(curr != NULL){
        list.append(arr[i]);
        i++;
        curr = curr->next;
    }
    return list;
}
int main(){
    DoublyLinkedList list;
    cout<<"Appending 1, 2, 8, 9, 0\n";
    list.append(1);
    list.append(2);
    list.append(8);
    list.append(9);
    list.append(0);
    list.show();
    cout<<"Prepending 3\n";
    list.prepend(3);
    list.show();
    cout<<"Inserting 5 at index 2\n";
    list.insert(5, 2);
    list.show();
    cout<<"Deleting at head\n";
    list.remove_at_head();
    list.show();
    cout<<"Deleting at tail\n";
    list.remove_at_tail();
    list.show(); 
    cout<<"Deleting at index 1\n";
    list.remove_at(1);
    list.show(); 
    cout<<"Sorted\n";
    DoublyLinkedList l2 = list.sorted();
    l2.show();
    cout<<"Reversed\n";
    l2.reverse();
    l2.show();
    return 0;
}