/*
 * Doubly-linked order list with a dummy node
 */
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
        int data;
        struct node *lP, *rP;
} node, *list;

list initList();
int isEmptyList(list);
void printList(list);
int insertList(list, int);
list searchList(list, int);
int deleteList(list, int);
list successorList(list, int);
list predecessorList(list, int);

int main()
{
    list l;
    int data ;
    char c;
 

    l = initList();

    printf("I data: to insert\nD data: to delete\n");
    printf("S data: to search\nU data: to get successor\n");
    printf("R data: to get predecessor\nP: print list\nE: exit\n");
    while(1){
        scanf("%c", &c);
        if(c == 'I' || c == 'i') {
           scanf("%d", &data);
           insertList(l, data);
        }
        if(c == 'D' || c == 'd') {
           scanf("%d", &data);
           deleteList(l, data);
        }
        if(c == 'S' || c == 's') {
           scanf("%d", &data);
           if(searchList(l, data) != NULL) printf("Data present\n");
           else printf("Data is not there\n");
        } 
        if(c == 'U' || c == 'u') {
           list t;
           scanf("%d", &data);
           if((t = successorList(l, data)) != NULL) printf("%d\n", t->data);
           else printf("Data is not there\n");
        } 
        if(c == 'R' || c == 'r') {
           list t;
           scanf("%d", &data);
           if((t = predecessorList(l, data)) != NULL) printf("%d\n", t->data);
           else printf("Data is not there\n");
        } 
        if(c == 'P' || c == 'p') printList(l);
        if(c == 'E' || c == 'e') break;
    }     
    return 0;
}

list initList(){   // Initialise the list
     list l;

     l = (list)malloc(sizeof(node));
     l->lP = l->rP = NULL;
     return l;
}