# Implementing a new Data Structure

Being a major principle in the foundations of the Computer Science field, a good Data Structure implementation is crucial to have a clean and optimized code.

It all started with 2 structures called: Array and LinkedList. And all other DS are derived from or based on them.

Let’s discuss each one of both quickly.

An array is a collection of data having all the same type and all stored according to indexes.

Arrays come in various ways: 1D as a linear array, 2D as a matrix, 3D as blocks of matrixes and etc..

Whereas elements in a LinkedList are represented as nodes, consisted of data-pointer structure.

The data field defines the actual value of the entered record.

However, the pointer field , also known as “next” pointer, stands for the link that connects these nodes.

After a brief presentation of Arrays and LinkedLists, it’s time to switch our attention to 2 next DS that are so-called: Stack and Queue.

Starting with the queue, the elements are stored in it in a FIFO (First In First Out) linear way, which manages the data using the 2 popular Push and Pop methods.

Push: Adds the element to the end of the queue, since the data is stored in a fifo way.

Pop: Removes the element whose turn is up next (Aka the element located at the head of the list).

However, the stack handles the deal differently. The data in it is stored in a linear LIFO ( Last in First Out) method and the Push and Pop functions are implemented in a slightly distinguished way, where:

Push: Adds now the element to top of the stack, since the data is stored according to the LIFO principle.

Pop: Removes the element on the top of the stack.

After presenting the differences between these 2 approaches, we’ll now highlight the limits of each one concisely.

The pop function in the queue removes the first entered element of the queue, which means if we’d like to remove the last entered element, we have to traverse the whole queue to reach it and hence lose a lot of precious execution time. Additionally, if we’d like to remove the first entered element in a stack, we’ll also have to traverse the whole stack to reach it and therefore suffer the same loss.

In contrast to that, the push function could impose a similar efficiency waste when it comes to adding an element to the head of the queue, or to the bottom of the stack.

However, the developers’ desire to reduce time complexity as possible, lead them to think of a new Data Structure that could fulfill the gap mentioned above.

The Deque data structure provides 4 data manipulation methods, 2 for pushing and 2 for popping that work in the following way:

Push: You could now choose between either pushing the element to the beginning or to the end of the structure, whichever is more convenient.

Pop: You get to choose between either removing the first element of the structure, or the last one.

The creation of this new DS stimulated a revolution in the linear DS approach where data is now more organized (The result of a mix between Stack and Queue design) and more flexible (4 data management methods, 2 push and 2 pop).

The c++ implementation of Deque is represented in the code snippet attached within this article.

``````//Implementation of the Deque using LinkedList

#include <bits/stdc++.h>

using namespace std;

// Node of a doubly linked list
struct Node
{
int data;
Node *prev, *next;
}

Node* getNode(int data)
{
Node* newNode = (Node*)malloc(sizeof(Node))
newNode->data = data;
newNode->prev = newNode->next = NULL;
return newNode;
}

//structure of the Deque

struct Deque
{
Node* front;
Node* rear;
int Size;
}

void initialize(Deque& d)
{
d.front = d.rear = NULL;
d.Size = 0;
}

void push_front(Deque &d, int data)
{
Node* newNode = getNode(data);

if(newNode == NULL) {  //If it's null, it means that the structure is full and cannot allocate more, since the getNode gets the size
// of the Node
cout <<"Overflow \n";
return;
}

if (d.front == NULL)   //If the deque is empty
d.rear = d.front = newNode;

else { //Adds it to the beginning of the Deque
newNode->next = d.front;
d.front->prev = newNode;
d.front = newNode;
}

d.Size++; //Increments the size by 1 since we successfully added the element.

}

void push_rear(Deque &d, int data)
{
Node* newNode = getNode(data);

if(newNode == NULL) {  //If it's null, it means that the structure is full and cannot allocate more, since the getNode gets the size
// of the Node
cout <<"Overflow \n";
return;
}

if (d.rear == NULL)   //If the deque is empty
d.rear = d.front = newNode;

else { //Adds it to the end of the Deque
newNode->prev = d.rear;
d.rear->prev = newNode;
d.rear = newNode;
}

d.Size++; //Increments the size by 1 since we successfully added the element.

}

void pop_front(Deque &d)
{
if(d.front==NULL && d.rear ==NULL) //If the deque is empty, then nothing to do
return;

Node* tmp = d.front;
d.front = d.front->next;

if(d.front ==NULL) //if there's only 1 element
d.rear = NULL;
else d.front->prev = NULL;

delete tmp;
d.Size-- ;  //Decrements the size by 1 since we successfully deleted the element.
}

void pop_rear(Deque &d)
{
if(d.front==NULL && d.rear ==NULL) //If the deque is empty, then nothing to do
return;

Node* tmp = d.rear;
d.rear = d.rear->prev;

if(d.rear ==NULL) //if there's only 1 element
d.front = NULL;
else d.rear->next = NULL;

delete tmp;
d.Size-- ;  //Decrements the size by 1 since we successfully deleted the element.
}

// -----------------------------------------------End of implementation using LinkedList -----------------------------------------------

// -----------------------------------------------Start of implementation using Arrays ----------------------------------------------------

#include <iostream>
using namespace std;
#define MAX 200  // 200 for instance

struct Deque
{
int  arr[MAX];
int  front;
int  rear;
int  size;
}

void initialize(Deque &d , int size)
{
d.front = -1;
d.rear = 0;
d.Size = size;
}

bool isFull(Deque d)
{
return ((d.front == 0 && d.rear == d.size-1) ||  d.front == d.rear+1);
}

void push_front(Deque &d, int data)
{

if (isFull(d))
{
cout << "Overflow\n";   //If it's full, can't add it because of overflow
return;
}

// If deque is empty
if (d.front == -1)
{
d.front = 0;
d.rear = 0;
}

// front is at first position of deque
else if (d.front == 0)
d.front = d.size - 1 ;

else // decrement front by 1
d.front = d.front-1;

// insert current element into Deque
d.arr[d.front] = data;
}

void push_rear(Deque &d, int data)
{

if (isFull(d))
{
cout << "Overflow\n";   //If it's full, can't add it because of overflow
return;
}

// If deque is empty
if (d.front == -1)
{
d.front = 0;
d.rear = 0;
}

// rear is at last allowed position of deque
else if (d.rear == d.size-1)
d.rear = 0;

else // increase rear by 1
d.rear = d.rear + 1 ;

// insert current element into Deque
d.arr[d.rear] = data;
}

void delete_front (Deque &d )
{

if (d.front == -1)
{ //if empty, nothing to do here
cout << "Underflow\n";
return ;
}

// Deque has only one element
if (d.front == -1)
{
d.front = -1;
d.rear = -1;
}
else
// back to initial position
if (d.front == d.size -1)
d.front = 0;

else // increment front by 1 to remove front value from Deque
d.front = d.front+1;
}

void delete_rear(Deque &d)
{
if (d.front == -1)
{ //if empty, nothing to do
cout << " Underflow\n" << endl ;
return ;
}

// Deque has only one element
if (d.front == d.rear)
{
d.front = -1;
d.rear = -1;
}
else if (d.rear == 0)
d.rear = d.size-1;
else
d.rear = d.rear-1;
}``````

100 points
3