3/11/08

Doubly-Linked List in C

In case you don't know what is a doubly-linked list see the image below. It is the same as the linked list with the difference that every node point not only to the next node but to the next and the previous nodes. This make it easier to scan the list and also provides flexibility.

Here is an implementation of the above list in C programming language. User can insert,delete or search numbers in the list. User can also print all the numbers in the list. When starting list is empty and user must input some numbers to try it. Dialog with the user is done by the main() function.

#include <stdio.h>

struct list {
int num;
struct list* nxt;
struct list* prv;
};

struct list *root;

void listinit() {
root=(struct list*)malloc(sizeof(struct list));
root->nxt=root;
root->prv=root;
}
/*return 1 if num is on the list else 0*/
int listfind(int num) {
root->num=num;
struct list* l;
for(l=root->nxt;l->num!=root->num;l=l->nxt) {}
return(l!=root);
}
/* insert num to the list
1 = success
0 = fail
*/
int listenter(int num) {
struct list *l1;
l1=(struct list*)malloc(sizeof(struct list));
if (l1==NULL) {return(0);}
l1->num=num;
l1->prv=root;
l1->nxt=root->nxt;
root->nxt=l1;
l1->nxt->prv=l1;
return(1);
}
/* remove num from the list
1 = success
0 = fail
*/
int listrmv(int num) {
struct list *l1;
root->num=num;
for(l1=root->nxt;l1->num!=num;l1=l1->nxt) {}
if(l1==root) { return(0); }
else {
l1->prv->nxt=l1->nxt;
l1->nxt->prv=l1->prv;
free(l1);
return(1);
}
}
/*print all the numbers in the list*/
void printlist() {
struct list *l1=root->nxt;
if(l1==root) { printf(" Empty list\n"); }
else{
for(;l1!=root;l1=l1->nxt) {
printf(" %d\n",l1->num);
}
}
}
/*destroy the queue*/
void destroy_list(){
struct list *l1=root->nxt;
struct list *l2;
if(l1==root) free(root);
else {
for(;l1!=root;) {
l2=l1->nxt;
free(l1);
l1=l2;
}
}
}
int main(int argc,char* argv[]) {
int sel,num;

listinit();
do {
printf("0:Exit\n");
printf("1:Insert number\n");
printf("2:Find number\n");
printf("3:Delete number\n");
printf("4:Print all numbers\n");
printf("Choose one of the above : ");
scanf("%d",&sel);
switch (sel) {
case 1: {
printf("Give a number : ");
scanf("%d",&num);
if(listenter(num)) {printf("Success\n");}
else {printf("Failed\n");}
break;
}
case 2: {
printf("Give a number : ");
scanf("%d",&num);
if(listfind(num)) { printf("Exists\n"); }
else { printf("Does not exist\n"); }
break;
}
case 3: {
printf("Give a number : ");
scanf("%d",&num);
if(listrmv(num)) {printf("Success\n");}
else {printf("Failed\n");}
break;
}
case 4: {
printlist();
break;
}
}
}
while(sel!=0);
destroy_list();
exit(0);
}

No comments: