What are Different Operations that Can be Performed on a Doubly Linked List 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.

advertisement

Sanfoundry Global Education & Learning Series – 1000 C Tutorials.

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

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn