Write a c program to implement a sorted doubly linked list?

Answer 1

The implementation of a sorted doubly linked list is similar to an unsorted doubly linked list. The only change will be in the insertion function where you will need to search for the position where the new element should be inserted.

Consider a doubly linked list with node structure as:

typedef struct node{

int data;

node *next. *prev;

}node;

node *head = NULL;

int isempty(){//This function returns whether the list is empty or not

return !head;

}

The code for insertion:

void insert( int num, int ** head){

node *temp, *temp1= *head;

temp = (node *)malloc(sizeof(node));

if( temp == NULL){

printf("Not enough space\n");

return;

}

temp->data = num;

temp->next = temp->prev = NULL;

if(isempty()){//insertion when the list is empty

*head= temp;

return;

}

if( temp1->data > num){//Insertion at the head

temp->next = head;

temp1->prev = num;

return;

}

while( temp1->next != NULL && temp->next->data < num)//Determiningthe postion of the element for insertion

temp1 = temp1->next;

temp->next = temp1->next;

if( !temp->next)

temp->next->prev = temp;

temp->prev = temp1;

temp1->next = temp;

}

If you want to know how to implement a normal doubly linked list, check the related liks below.