DOUBLY LINKED LIST

In computer science, a doubly-linked list is a linked data structure that consists of a set of data records, each having two special link fields that contain references to the previous and to the next record in the sequence. It can be viewed as two singly-linked lists formed from the same data items, in two opposite orders.

A doubly-linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.

The two links allow walking along the list in either direction with equal ease. Compared to a singly-linked list, modifying a doubly-linked list usually requires changing more pointers, but is sometimes simpler because there is no need to keep track of the address of the previous node.

----------------------------------------------------------------------------------------------

A C PROGRAM TO IMPLEMENT OPERATIONS IN DOUBLY LINKED LIST

COMPILER EMPLOYED: DEV C++ COMPILER-4.9.9.2

SOURCE FILE SIZE :2 kb

EXE FILE SIZE :22 kb

NOTE: PLEASE INCLUDE THE DESIRED HEADER FILE

---------------------------------------------------------------------------------------------

C PROGRAM SOURCE & EXE DOWNLOAD:

Click download button to download

DISCLAIMER: The following program cannot be ensured of perfection.so any flaws in the program can be notified in the comments section.

----------------------------------------------------------------------------------------------

CODE:

#include

#define N 100

struct dlinklist
{
struct dlinklist *PREV; /** Stores address of previous node **/
int ELE; /** stores roll number **/

struct dlinklist *NEXT; /** stores address of NEXT node **/
};

/** Redefining dlinklist as node **/
typedef struct dlinklist NODE;

void init(NODE*); /** Input function **/
void ins_aft(NODE*); /** Function inserting before **/
NODE* ins_bef(NODE*); /** Function inserting after **/
NODE* del(NODE*); /** Function deleting a NODE **/

void DISPLAY(NODE*); /** Function for displaying NODE **/
void ELEFIND(NODE*); /** Function for searching NODE **/


int main()
{
NODE *HEAD;
char ch; /* Choice inputing varible */
int OPT; /* Option inputing variable*/
static int FLAG=0; /* Unchanged after iniialization */

HEAD=(NODE*)malloc(sizeof(NODE));
HEAD->NEXT=NULL;
HEAD->PREV=NULL;
do
{
MENU:
printf("\n DOUBLY LINKED LIST OPERATIONS & IMPLEMENTATION");
printf("\n MENU");
printf("\n [1]. NODE INITIALIZATION \n");
printf("\n [2]. INSERTION-BEFORE SPECIFIED NODE\n");
printf("\n [3]. INSERTION-AFTER SPECIFIED NODE \n");
printf("\n [4]. DELETE A PARTICULAR NODE\n");
printf("\n [5]. SEARCH THE NODES\n");
printf("\n [6]. DISPLAY ALL THE NODES\n");
scanf("%d",&OPT);
if(FLAG==0 && OPT!=1)
{
printf("\n WARNING :YOU MUST ATLEAST INITIALIZE ONE NODE...\n");
goto MENU;
}
if(FLAG==1 && OPT==1)
{
printf("\n INITIALIZATION CAN OCCUR ONLY ONCE...\n");
printf("\n NOW YOU CAN INSERT A NODE...\n");
goto MENU;
}
if(OPT==4 && HEAD->NEXT==NULL)
{
printf("\nYOU CANNOT DELETE THE ONLY ONE NODE...\n");
goto MENU;
}
if(FLAG==0 && OPT==1)
FLAG=1;
switch(OPT)
{
case 1:
printf("\n INVOKING INSERTION OPERATION...");
init(HEAD);
break;
case 2:
printf("\n INVOKING INSERTION OPERATION...");
HEAD=ins_bef(HEAD);
break;
case 3:
printf("\n INVOKING INSERTION OPERATION...");
ins_aft(HEAD);
break;
case 4:
printf("\n INVOKING DELETION OPERATION...");
HEAD=del(HEAD);
break;
case 5:
printf("\n INVOKING DEARCH OPERATION...");
ELEFIND(HEAD);
break;
case 6:
printf("\n INVOKING DISPLAY OPERATION...");
DISPLAY(HEAD);
break;
}
printf("\nDO YOU WISH TO CONTINUE [Y~N]:");
ch=getche();
}while(ch=='Y' || ch=='y');

system("pause");
return 0;
}

void init(NODE *CURRENT)
{
printf("\n\n INSERTION OPERATION INVOKED...");
CURRENT->PREV=NULL;
printf("\nENTER THE ELEMENT:\n");
scanf("%d",&CURRENT->ELE);

// fflush(stdin);

CURRENT->NEXT=NULL;
}

void ins_aft(NODE *CURRENT)
{
printf("\n\n INSERTION OPERATION INVOKED...");
int NO; /* inserting a NODE*/
int FLAG=0;
NODE *NEW;
NEW=(NODE*)malloc(sizeof(NODE));
printf("\nENTER THE ELEMENT AFTER WHICH YOU WISH TO INSERT:\n");
scanf("%d",&NO);
init(NEW);
while(CURRENT->NEXT!=NULL)
{
/*** Insertion checking for all nodes except last ***/
if(CURRENT->ELE==NO)
{
NEW->NEXT=CURRENT->NEXT;
CURRENT->NEXT->PREV=NEW;
CURRENT->NEXT=NEW;
NEW->PREV=CURRENT;
FLAG=1;
}
CURRENT=CURRENT->NEXT;
}
if(FLAG==0 && CURRENT->NEXT==NULL && CURRENT->ELE==NO)
{
/*** Insertion checking for last nodes ***/
NEW->NEXT=CURRENT->NEXT;
CURRENT->NEXT=NEW;
FLAG=1;
}
else if(FLAG==0 && CURRENT->NEXT==NULL)
printf("\n MATCH NOT FOUND...\n");
}

NODE* ins_bef(NODE *CURRENT)
{
printf("\n\n INSERTION OPERATION INVOKED...");
int NO; /* inserting a NODE*/
NODE *NEW,*TEMP;
NEW=(NODE*)malloc(sizeof(NODE));
printf("\nENTER THE ELEMENT BEFORE WHICH YOU WANT TO INSERT THE ELEMENT:\n");
scanf("%d",&NO);
init(NEW);
if(CURRENT->ELE==NO)
{
/*** Insertion checking for first NODE ***/
NEW->NEXT=CURRENT;
CURRENT->PREV=NEW;
CURRENT=NEW;
return(CURRENT);
}
TEMP=CURRENT;
while(TEMP->NEXT!=NULL)
{
/*** Insertion checking for all NODE except first ***/
if(TEMP->NEXT->ELE==NO)
{
NEW->NEXT=TEMP->NEXT;
TEMP->NEXT->PREV=NEW;
TEMP->NEXT=NEW;
NEW->PREV=TEMP;
return(CURRENT);
}
TEMP=TEMP->NEXT;
}
/*
If the function does not return from any return statement.
There is no match to insert before the input roll number.
*/
printf("\n MATCH NOT FOUND...\n");
return(CURRENT);
}

NODE* del(NODE *CURRENT)
{
printf("\n\n DELETION OPERATION INVOKED...");
int NO; /* deleting a NODE*/
NODE *NEW,*TEMP;
printf("\nENTER THE ELEMENT TO DELETE:\n");
scanf("%d",&NO);
NEW=CURRENT;
if(CURRENT->ELE==NO)
{
/*** Checking condition for deletion of first NODE ***/
NEW=CURRENT; /* Unnecessary step */
CURRENT=CURRENT->NEXT;
CURRENT->PREV=NULL;
free(NEW);
return(CURRENT);
}
else
{
while(NEW->NEXT->NEXT!=NULL)
{
/*** Checking condition for deletion of ***/
/*** all nodes except first and last NODE ***/
if(CURRENT->NEXT->ELE==NO)
{
NEW=CURRENT;
TEMP=CURRENT->NEXT;
NEW->NEXT=NEW->NEXT->NEXT;
NEW->NEXT->PREV=CURRENT;
free(TEMP);
return(CURRENT);
}
NEW=NEW->NEXT;
}
if(NEW->NEXT->NEXT==NULL && NEW->NEXT->ELE==NO)
{
/*** Checking condition for deletion of last NODE ***/
TEMP=NEW->NEXT;
free(TEMP);
NEW->NEXT=NULL;
return(CURRENT);
}
}
printf("\n MATCH NOT FOUND...\n");
return(CURRENT);
}


void ELEFIND(NODE *CURRENT)
{
printf("\n\n ELEMENT SEARCH OPERATION INVOKED...");
int NO;
printf("\nENTER THE ELEMENT TO SEARCH:\n");
scanf("%d",&NO);
while(CURRENT->NEXT!=NULL)
{
if(CURRENT->ELE==NO)
printf("\n %d",CURRENT->ELE);
CURRENT=CURRENT->NEXT;
}
if(CURRENT->NEXT==NULL && CURRENT->ELE==NO)
printf("\n%d",CURRENT->ELE);
}


void DISPLAY(NODE *CURRENT)
{
printf("\n\n DISPLAY OPERATION INVOKED...\n NODES:");
while(CURRENT!=NULL)
{
printf("\n%d",CURRENT->ELE);
CURRENT=CURRENT->NEXT;
}
}

----------------------------------------------------------------------------------------------
Your's friendly,

[MOHANRAM.G],
ADMIN...