Problem Statement: Implement Doubly Linked List

In this programming homework, we will be implementing sequence data structure as linked list.

One of the central type of data at the base of many indexes and algorithms is called set data. Typically, the

set is of keys, which are positive integers. It is a subset $S$ of the universal set $U=\{1,2,$dots,$u\}.$ When we

use sequence to represent a set, it may become an 'ordered' collection of keys. There are different ways this

order can be seen $-$ it may be based on the values of keys, or it may just be about the positions of keys in

the data structure.

In this programming assignment, we shall be using doubly linked lists $($as against singly linked list we saw

in the class$)$ to implement sequence which can serve both a stack and a queue. We choose doubly linked

list here so that no 'traversal' of the list is necessary, and all the operations can be done instantly $($with the

exception of printall$).$ Thus, Node structure here will have 'prev' pointer in addition to 'next'. In a singly

linked list, 'next' pointer of the tail element is null. In doubly linked list, in addition to this, 'prev' pointer

of the head element is also set to null. Base cases to consider are: what if the list is empty before the

insertion? What if the list becomes empty after deletion? Please use the following helper code. Fill up

commented part by an actual code. Your class name must be DoublyLinkedList and filename either

DoublyLinkedList.java or DoublyLinkedList.cpp$.$ Submit this on gradescope.

You can use and build on the following partial$/$pseudo code:

class Node $\{$

int key;

Node prev, next;

Node$($int key$)\{$

this. key $=$ key;

this.prev $=$ null;

this. next $=$ null;

$\}$

$\}$

class DoublyLinkedList $\{$

Node head;

Node tail;

int count;

DoublyLinkedList $()\{$

head $=$ tail $=$ null;

count $=0$;

$\}$