What is a Doubly Linked List in C?

This C Tutorial explains a Doubly Linked List in C language.

A singly liked list can be traversed in one and in Forward Direction only while doubly linked list in either Forward or Backward direction. For this either way traversal, each node contains two pointer fields. We consider, for example, declaration of a node,

typedef struct NODE {
                     struct NODE *fwd;
                     struct NODE *bwd;
                     int value;
         } Node; 
    /* Node is user defined type for above structure template */

fwd pointer of each node, except last node in which it’s NULL, points to next node in the list while bwd pointer of each node, except first node in which it’s NULL, points to previous node in the list. But how list begins? There’s a root node of which fwd pointer field begins the list in Forward diection while bwd pointer field begins the list in backward direction.

Let’s see declaration for root node,

int main(void)
{
    Node root;  /* root node declared */
 
    /* fwd and bwd fields of root node are set to NULL */
    root.fwd = 0;
    root.bwd = 0;
 
}

Instead of declaraing a root node, here for ex. it also contains an integer “value” which wastes memory, we could have used two separate pointers each of type Node *. Since we write dedicated functions to perform different operations on the list and then we would have required to pass two pointers to functions. To simplify the task we better declare single root node with two pointer fields and use it’s value field for stroing other list related information, for ex. no. of nodes in the list, etc.
This way you are required to pass pointer to root to different functions for different operations on the list.

advertisement
advertisement

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.