---
description: Double Ended Queue (Deque)
---

# Deque using Linked List



## <mark style="color:blue;">`Filename:`</mark>    _<mark style="color:red;">Doubly LL.h</mark>_

```cpp
#include <iostream>
#pragma once
using namespace std;

template<typename T>class Node{
public:
    T data;
    Node<T>* next = nullptr;
    Node<T>* prev = nullptr;
    explicit Node(T val): data(val) {};
};

template<typename T>class DoublyLL{
    Node<T> *head = nullptr;
    Node<T> *tail = nullptr;
    int elements = 0;
public:
    
    DoublyLL() {};
    
    DoublyLL(const DoublyLL<T>&);

    DoublyLL& operator= (const DoublyLL<T>&);

    void insert(const T);

    void insertAtHead(const T);

    bool search(const T) const;

    bool remove(const T);

    bool removeHead(T&);

    bool removeTail(T&);

    bool isEmpty() { return elements == 0; }
    
    void Swap(DoublyLL&);

    template<typename out> friend ostream& operator<< (ostream& , const DoublyLL<out>&);

    T peakHead() const;
    T peakTail() const;

    ~DoublyLL();
};

template<typename out> ostream& operator<< (ostream& cout, const DoublyLL<out>& list) {
    Node<out>* temp = list.head;
    while (temp != nullptr) {
        cout << temp -> data << " ";
        temp = temp -> next;
    } cout << endl;
    return cout;
}

template<typename T> T DoublyLL<T> :: peakHead()const {
    if(elements == 0) {
        puts("List is Empty!");
        T t;
        return t;
    }
    return head->data;
}
template<typename T> T DoublyLL<T> :: peakTail()const {
    if(elements == 0) {
        puts("List is Empty!");
        T t;
        return t;
    }
    return tail->data;
}

template<typename T> DoublyLL<T> :: DoublyLL(const DoublyLL<T>& list) {  
    elements = list.elements;  

    Node<T>* tempHead = list.head;  
    Node<T>* cur = new Node<T>(tempHead -> data);  
    tempHead = tempHead -> next;  

    head = tail = cur;  
        
    while (tempHead != nullptr) {  
        Node<T>* newNode = new Node<T>(tempHead -> data); 
        tail -> next = newNode;  
        newNode -> prev = tail;  
        tail = newNode;  

        tempHead = tempHead -> next;  
    }
} 

template<typename T> DoublyLL<T>& DoublyLL<T> :: operator= (const DoublyLL<T>& rhs) {  

    if(this == &rhs) return *this; 

    elements = rhs.elements; 
    
    while (head != nullptr) { 
        Node<T>* temp = head; 
        head = head -> next;  
        delete temp; 
    }  
    tail = nullptr;  

    Node<T>* tempHead = rhs.head; 
    Node<T>* cur = new Node<T>(tempHead -> data); 
    tempHead = tempHead -> next;  

    head = tail = cur;  
        
    while (tempHead != nullptr) {  
        Node<T>* newNode = new Node<T>(tempHead -> data);  
        tail -> next = newNode;
        newNode -> prev = tail;
        tail = newNode;

        tempHead = tempHead -> next;
    }
    return *this;
}

template<typename T> void DoublyLL<T> :: insert(const T val){

    if (!elements) insertAtHead(val);
    else{
        Node<T>* newNode = new Node<T>(val);
        tail -> next = newNode;
        newNode -> prev = tail;
        tail = newNode;
        elements++;
    }
}

template<typename T> void DoublyLL<T> :: insertAtHead(const T val){
    Node<T>* newNode = new Node<T>(val);
    if(!elements) head = tail = newNode;
    else{
        newNode -> next = head;
        head -> prev = newNode;
        head = newNode;
    }
    elements++;
}

template<typename T> bool DoublyLL<T> :: search(const T val) const {
    Node<T>* temp = head;

    while (temp != nullptr) {
        if(temp -> data == val) return true;
        temp = temp -> next;
    }
    return false;
}

template<typename T> bool DoublyLL<T> :: remove(const T val) {
    if(elements == 0) return false;

    if(head -> data == val && elements == 1) {
        delete head;
        head = tail = nullptr;
        elements--;
        return true;
    }
    
    if(tail -> data == val) {
        Node<T>* temp = tail;
        tail = tail -> prev;
        tail -> next = nullptr;
        delete temp;
        elements--;
        return true;
    }

    Node<T>* cur = head;
    Node<T>* pre = nullptr;

    while (cur -> next != nullptr) {
        if(cur -> data == val) {
            pre -> next = cur -> next;
            cur -> next -> prev = pre;
            elements--;
            return true;
        }
        pre = cur;
        cur = cur -> next;
    }
    
    return false;
}

template<typename T> bool DoublyLL<T> :: removeTail(T& val) {
    if(elements == 0) {
        puts("List is Empty!");
        T t;
        val = t;
        return false;
    }
    val = tail -> data;
    
    if(elements == 1) {
        delete head;
        head = tail = nullptr;
        elements--;
        return true;
    }

    Node<T>* temp = tail;
    tail = tail -> prev;
    tail -> next = nullptr;
    delete temp;
    elements--;
    return true;
}

template<typename T> bool DoublyLL<T> :: removeHead(T& headData) {
    if(elements == 0) return false;

    headData = head ->data;
    if(elements == 1) {
        delete head;
        head = tail = nullptr;
        elements--;
        return true;
    }
    Node<T>* temp = head;

    head = head -> next;
    head -> prev = nullptr;
    delete temp;
    elements--;
    return true;
}
template<typename T> DoublyLL<T> :: ~DoublyLL() {

    while (head != nullptr) {
        Node<T>* temp = head;
        head = head -> next;
        delete temp;
    }
    tail = nullptr;
}
```

## <mark style="color:blue;">`Filename:`</mark>    _<mark style="color:red;">Deque.h</mark>_

```cpp
#include "Doubly LL.h"
template<typename T> class deque {
    DoublyLL<T> list;
    int elements = 0;
public:
    
    bool isEmpty() {
        return list.isEmpty();
    }
    
    T front() {
        return list.peakHead();
    }
    
    T rear() {
        return list.peakTail();
    }

    T size() {
        return elements;
    }

    void insertFront(const T);
    void insertRear(const T);
    void deleteFront(T&);
    void deleteRear(T&);
};

template<typename T> void deque<T> :: insertFront(const T val) {
    elements++;
    list.insertAtHead(val);
} 

template<typename T> void deque<T> :: insertRear(const T val) {
    elements++;
    list.insert(val);
} 

template<typename T> void deque<T> :: deleteFront(T& val) {
    elements--;
    list.removeHead(val);
} 

template<typename T> void deque<T> :: deleteRear(T& val) {
    elements--;
    val = list.peakTail();
    list.removeTail(val);
} 
```

## <mark style="color:blue;">`Filename:`</mark>    _<mark style="color:red;">main.cpp</mark>_

```cpp
#include "Deque.h"

int main() {
    deque<int> dq;

    dq.insertRear(1);
    dq.insertRear(2);
    dq.insertFront(3);
    dq.insertFront(4);
    
    cout << "Front: " << dq.front() << ",Rear: " << dq.rear() << endl; 

    while (!dq.isEmpty()){
        int t;
        dq.deleteRear(t);
        cout << t;
    }

}
```

