Understanding Doubly Linked Lists in C Programming
A doubly linked list in C comprises nodes with pointers to the next and previous nodes. Managing two sets of pointers can be complex, but adds flexibility for adding and removing nodes dynamically. This post explores the structure, implementation, and examples of doubly linked lists in C.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Double-Linked Lists in C Personal Software Engineering
Singly Linked Lists A (singly) linked list comprises a set of nodes, each node having a pointer to the next node in the list. We keep a pointer to the first node in a list head pointer. p_head 800 next 150 next 100 next Since lists can grow and shrink dynamically, space for the list nodes is allocated and released dynamically using malloc and free.
Doubly Linked Lists A doubly linked list comprises a set of nodes, each node having a pointer to the next node in the list AND a pointer to the previous node We keep a pointer to the first node in a list head pointer and a pointers to the end of the list as the list tail point p_tail p_head 800 next prev 150 next prev 100 next prev Same as singly linked lists: Since lists can grow and shrink dynamically, space for the list nodes is allocated and released dynamically using malloc and free. To add and remove nodes, you now have to manage two sets of pointers (next and prev), and update head and tail as needed
Doubly Linked List Example in C Adding nodes typedef struct _node { int contents ; struct _node *next ; struct _node *prev; } node ; //Create the node struct node* n = malloc(sizeof(struct node)); n->contents = 800; n->next = NULL; n->prev = NULL;
Doubly Linked List Example in C Adding nodes typedef struct _node { int contents ; struct _node *next ; struct _node *prev; } node ; //Create the node struct node* n = malloc(sizeof(struct node)); n->contents = 800; n->next = NULL; n->prev = NULL; //Add the first node p_head = n; p_tail = n;
Doubly Linked List Example in C Insertion typedef struct _node { int contents ; struct _node *next ; struct _node *prev; } node ; //Create the node struct node* newNode = malloc(sizeof(struct node)); //The new node n->next = NULL; n->prev = NULL; //Find the node where you want to insert node* pNode = FindNode(100); //Have to write your own FindNode! //The previous node is pNode->prev; next is pNode->next pNode->prev->next=newNode;//previous node next now points to newNode newNode->prev = pNode->prev; //newNode prev. points to previousNode pNode->prev = n; n->next = pNode; //pNode prev now points to newNode
How insertion happens p_tail p_head 800 next prev 150 next prev 100 next prev 600 next prev
What you end up with p_tail p_head 800 next prev 150 next prev 100 next prev 600 next prev
Removing a node p_tail p_head 800 next prev 150 next prev 100 next prev 600 next prev
Removing a node (2) p_tail p_head 800 next prev 150 next prev 100 next prev 600 next prev
Removing a node (3) p_tail p_head 800 next prev 150 next prev 100 next prev 600 next prev
Removing a node (4) p_tail p_head 800 next prev 150 next prev 100 next prev 600 next prev
Removing a node (5) The next pointer of the node BEFORE THE REMOVED NODE now points to the next node OF THE REMOVED NODE p_tail p_head 800 next prev 150 next prev 100 next prev The previous pointer of the node AFTER THE REMOVED NODE now points to the previous node OF THE REMOVED NODE 600 next prev free
