Doubly Linked List Operations in C

This C Tutorial explains Different Operations that Can be Performed on a Doubly Linked List in C.

We have following C program which implements a doubly linked list and performs various operations on it.

/* dll.c -- a realistic approach */
#include <stdio.h>
#include <stdlib.h>
 
#define T 1 /* TRAVERSE */
#define I 2 /* INSERT   */
#define S 3 /* SEARCH   */
#define D 4 /* DELETE   */
#define Q 5 /* QUIT     */
#define TRAVERSE "enter 1 to TRAVERSE the list..."
#define INSERT "enter 2 to INSERT new value in the list..."
#define SEARCH "enter 3 to SEARCH a value in the list..."
#define DELETE "enter 4 to DELETE a value from the list..."
#define QUIT "enter 5 to QUIT the program..."
#define FORWARD 6
#define BACKWARD 7
 
typedef struct NODE {
                     struct NODE *fwd;
                     struct NODE *bwd;
                     int value;
        } Node;
 
/* function declarations */
int ftraverse(Node *);
int btraverse(Node *);
void insert(Node *, const int);
int search(Node *, const int);
int delete(Node *, const int);
 
int main(void)
{
    Node root;     /* root is a Node, not a pointer to Node */
    int op = 0;
    int value = 0;
    int fbchoice = 0; /* FORWARD BACKWARD Choice */
 
    /* fwd and bwd fields of root set to NULL */
    root.fwd = 0;
    root.bwd = 0;
 
    printf("\n**Program Shows different operations on Doubly Linked "
           "List.**\n");
    printf("\nUser, what operation do you want to do, now?\n\n");
    printf("%s\n%s\n%s\n%s\n%s\n: ",
            TRAVERSE, INSERT, SEARCH, DELETE, QUIT);
    while (1) {
        while (scanf("%d", &op) == 1) {
                if (op == T) {
                    printf("Whether in Forward or Backward Direction,\n");
                    printf("For FORWARD, enter 6, for BACKWARD, "
                           "enter 7,: ");
                    scanf("%d", &fbchoice);
 
                    if (fbchoice == FORWARD)
                        op = ftraverse(&root);
                    else if (fbchoice == BACKWARD)
                        op = btraverse(&root);
                }
 
                if (op == I) {
                    printf("User, enter integer value you want to "
                           "insert: ");
                    scanf("%d", &value);
                    insert(&root, value);
                }
 
                if (op == S) {
                    printf("User, enter an integer value you wish to "
                            "search in the list...: ");
                    scanf("%d", &value);
                    op = search(&root, value);
 
                    if (op == I) {
                        printf("User, enter integer value you want to "
                               "insert: ");
                        scanf("%d", &value);
                        insert(&root, value);
                    }
                }
 
                if (op == D) {
                    printf("User, enter a value you wish to delete: ");
                    scanf("%d", &value);
                    op = delete(&root, value);
 
                    if (op == I) {
                        printf("User, enter integer value you want to "
                               "insert: ");
                        scanf("%d", &value);
                        insert(&root, value);
                    }
                }
                if (op == 5) {
                    printf("Thank You!\n");
                    return 0;
                }
 
                printf("\nUser, what operation do you want now?\n\n");
                printf("%s\n%s\n%s\n%s\n%s\n: ",
                         TRAVERSE, INSERT, SEARCH, DELETE, QUIT);
 
        }
   }
}
 
void insert(register Node *p2r, const int value)
{
    register Node *this = p2r;
    register Node *next;
    register Node *newnode;
 
    /* Let's confirn if value is already in the list */
    while ((next = this->fwd) != NULL) {
            if (next->value == value) {
                    printf("Value %d is already in the list!\n");
                    return ;
            }
            /* I ensure each value is inserted once */
            if (next->value > value)
                    break;
 
            this = next;
    }
 
    /* Value isn't already in the list */
    /* Let's allocate it in proper place in the list */
    /* Allocate space to newnode */
    newnode = (Node *)malloc(sizeof(Node));
 
    /* Verify if allocation successful */
    if (newnode == NULL) {
        printf("Error: Memory Allocation Failed!\n");
        exit(EXIT_FAILURE);
    }
 
    /* write in value in the newnode */
    newnode->value = value;
 
    /* Insert value in the list */
    /* 
     * four pointer fields in this, newnode and next required
     * to be adjusted
     */
    newnode->fwd = next;
    this->fwd = newnode;
 
    if (this != p2r)
        newnode->bwd = this;
    else
        newnode->bwd = NULL;
 
    if (next != NULL)
        next->bwd = newnode;
    else
        p2r->bwd = newnode;
 
    printf("Value %d inserted successfully!\n", value);
}
 
int ftraverse(register Node *p2r)
{
    register Node *this = p2r->fwd;
    int op = 0;
 
    /* Let's verify if list is Empty */
    if (this == NULL) {
        printf("\nList is EMPTY.\n");
        printf("So, you can either enter a value in the list or ");
        printf("QUIT the program.\nEnter 2 to INSERT value in the list, "
               "or enter 5 to QUIT.: ");
        while (scanf("%d", &op) == 1 && (op != I && op != Q))
            printf("Entered value is INCORRECT, enter CORRECT "
                    "value...: ");
 
        return op;
    }
    /* List isn't EMPTY, Traversing the list in FORWARD direction */
    else {
            printf("\nList is as follows: ");
            while (this != NULL) {
                    printf("%d ,", this->value);
                    this = this->fwd;
            }
            puts("\n");
            return op;
    }
}
 
int btraverse(register Node *p2r)
{
    register Node *this = p2r->bwd;
    int op = 0;
 
    /* Let's verify if list is Empty */
    if (this == NULL) {
        printf("\nList is EMPTY.\n");
        printf("So, you can either enter a value in the list or ");
        printf("QUIT the program.\nEnter 2 to INSERT value in the list, "
               "or enter 5 to QUIT.: ");
        while (scanf("%d", &op) == 1 && (op != I && op != Q))
            printf("Entered value is INCORRECT, enter CORRECT value: ");
 
 
        return op;
    }
    /* List isn't EMPTY, Traversing the list in Backward direction */
    else {
            printf("\nList is as follows: ");
            while (this != NULL) {
                    printf("%d ,", this->value);
                    this = this->bwd;
            }
            puts("\n");
            return op;
    }
}
 
int delete(register Node *p2r, const int value)
{
    register Node *current = p2r;
    register Node *next;
    register Node *dnode;
    int op = 0;
 
    /* let's see if list is empty */
    if (current->fwd == NULL) {
        printf("List is empty.\n");
        printf("User, you can either enter an integer value or you can "
               "quit the program.\n");
        printf("Enter 2 to INSERT a value and enter 5 to QUIT the "
               "program: ");
        while (scanf("%d", &op) == 1 && (op != I && op != Q)) 
                 printf("You entered WRONG value! Please try again.\n");
 
        return op;
    }
    else {
        /*
         * List isn't empty. We search through the entire list for 
         * desired value and once found, we'll delete the node containing
         * the value
         */
        while ((dnode = current->fwd) != NULL && dnode->value != value)
                current = dnode; /* update the current node */
 
        /* now there are 2 cases, Either we've reached the end of list */
        if (dnode == NULL) {
           printf("We have reached the end of the List.\n");
           printf("Value %d is NOT in the list.\n", value);
           return op;
        }
        else if (dnode->value == value) {
                    printf("We have found value %d in the List.", value);
                    /* 
                     * set current->fwd to node following node to be 
                     * deleted
                     */
                    current->fwd = dnode->fwd;
 
                    /*
                     * now set bwd pointer field of node following the 
                     * deleting value
                     */
                    next = dnode->fwd;
                    if (next == NULL) {
                        /* reached end of list */
                        /* 
                         * set bwd field of root node to preceding node 
                         * of deleting node
                         */
                        p2r->bwd = dnode->bwd;
                    }
                    else {
                        /* else where in the list */
                        next->bwd = dnode->bwd;
                    }
 
                    printf(" And deleted the value!\n");
                    /* now free up the dnode */
                    free(dnode);
                    return op;
        }
    }
}
 
int search(register Node *p2r, const int value)
{
    register Node *this = p2r->fwd;
    int op = 0;
 
    /* Let's verify if list is Empty */
    if (this == NULL) {
        printf("\nList is EMPTY.\n");
        printf("So, you can either enter a value in the list or ");
        printf("QUIT the program.\nEnter 2 to INSERT value in the list, "
               "or enter 5 to QUIT.: ");
        while (scanf("%d", &op) == 1 && (op != I && op != Q))
            printf("Entered value is INCORRECT, enter CORRECT value: ");
 
        return op;
    }
    /* List isn't EMPTY, Searching value in the list */
    else {
            while ((this != NULL) && this->value != value)
                    this = this->fwd;
 
            if (this == NULL) {  /* reached end of list */
                printf(" %d is NOT in the list.\n", value);
                return op;
            }
            else {
                printf("%d is FOUND in the list.\n", value);
                return op;
            }
    }
}

Notice that a doubly linked list differs from singly linked list in that it can be traversed both in forward and backward direction. This feature requires two pointer fields in Node declaration. Try to run the program and analyse the various operations performed on doubly linked list. Comments are well written to let you know throughout how program is doing.

Sanfoundry Global Education & Learning Series – 1000 C Tutorials.

If you wish to look at all C Tutorials, go to C Tutorials.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.