In this programming homework, we will be implementing sequence data structure as $*$doubly$*$ 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,....,$ 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$;

$\}$

void insertF$($int key$)\{$

Node p$=$ new Node$($key$)$;

if$($head $==$ null$)$

head$=$tail$=$p; $//$ it is a single element list now

else $\{$

$//$ we will do some $$pointer stitching$$ carefully

$//$ prepare p to become new head so that p$$s next will point to current

head

$//$ set current head$$s prev to p

$//$ set new head to p

$\}$

$//$increment count

$\}$

void insertL$($int key$)\{$

Node p $=$ new Node$($key$)$;

if $($tail $==$ null$)$

head$=$tail$=$p;

else $\{$

$//$set tail$$s next to p

$//$ set p$$s prev to tail

$//$ set new tail as p

$\}$

$//$ increment count

$\}$

int deleteF$()\{$

if $($count $==0)$ return $-1$; $//$error

Node p $=$ head;

int i $=$ p$.$key;

$//$prepare to remove head by setting head to head.next

if$($head $==$ null$)$ tail $=$ null; $//$ if list becomes empty after deletion

else $\{$

$//$new head let$$s go of the old head by setting new head$$s prev to null

$\}$

$//$decrement count

$//$deallocate p $($optional$)$

return i;

$\}$

int deleteL$()\{$

if $($count $==0)$ return $-1$; $//$error

Node p $=$ tail;

int i $=$ p$.$key;

tail $=$ tail.prev;

if $($tail $==$ null$)$ head $=$ null;

else tail.next $=$ null;

count$--$;

$//$deallocate p

return i;

$\}$

void printall$()\{$

Node p $=$ head;

while $($p$!=$null$)\{$

System.out.print$($p$.$key$)$;

if $($p$.$next $!=$null$)$ System.out.print$("")$;

p$=$p$.$next;

$\}$

$//$System$.$out.println$()$; $//$do not use this for submission

$\}$

public static void main$($String$[]$ args$)\{$

DoublyLinkedList l $=$ new DoublyLinkedList$()$;

l$.$insertF$(32)$;

l$.$insertF$(42)$;

l$.$insertL$(37)$;

l$.$insertL$(27)$;

int temp $=$ l$.$deleteF$()$;

l$.$printall$()$; $//$ output will be $323727$

$\}$

$\}$

Required Output:

$323727$