Doubly linked list push

Write a C program to create a doubly linked list and insert a new node in beginning, end or at any position in the list. How to insert a new node at beginning of a Doubly linked list. How to insert a new node at the end of a doubly linked list. How to insert a new node at any position of a doubly linked list in C. Algorithm to insert node in a doubly linked list.

Required knowledge

Basic C programming, Functions, Dynamic memory allocation, Doubly linked list

Algorithm to insert node at the beginning of a Doubly linked list

Algorithm to insert node at the end of a Doubly linked list

Algorithm to insert node at any position of a Doubly linked list

Steps to insert a new node in Doubly linked list

We have supposed that we want to insert a node at 3rd position.

1. Traverse to N-1 node in the list. Where N is the position to insert. Say temp now points to N-1th node.

2. Create a newNode that is to be inserted and assign some data to its data field.

3. Connect the next address field of newNode with the node pointed by next address field of temp node.

4. Connect the previous address field of newNode with the temp node.

5. Check if temp->next is not NULL then, connect the previous address field of node pointed by temp.next to newNode.

6. Connect the next address field of temp node to newNode i.e. temp->next will now point to newNode.

7. Final list

Program to insert a node in doubly linked list

/** * C program to insert a node in Doubly linked list */ #include #include /* * Basic structure of Node */ struct node { int data; struct node * prev; struct node * next; }*head, *last; /* * Function used in this program */ void createList[int n]; void displayList[]; void insertAtBeginning[int data]; void insertAtEnd[int data]; void insertAtN[int data, int position]; int main[] { int n, data, choice=1; head = NULL; last = NULL; /* * Run forever until user chooses 0 */ while[choice != 0] { /* * Menu creation to use the program */ printf["============================================\n"]; printf["DOUBLY LINKED LIST PROGRAM\n"]; printf["============================================\n"]; printf["1. Create List\n"]; printf["2. Insert node - at beginning\n"]; printf["3. Insert node - at end\n"]; printf["4. Insert node - at N\n"]; printf["5. Display list\n"]; printf["0. Exit\n"]; printf["--------------------------------------------\n"]; printf["Enter your choice : "]; scanf["%d", &choice]; /* * Choose from different menu operation */ switch[choice] { case 1: printf["Enter the total number of nodes in list: "]; scanf["%d", &n]; createList[n]; break; case 2: printf["Enter data of first node : "]; scanf["%d", &data]; insertAtBeginning[data]; break; case 3: printf["Enter data of last node : "]; scanf["%d", &data]; insertAtEnd[data]; break; case 4: printf["Enter the position where you want to insert new node: "]; scanf["%d", &n]; printf["Enter data of %d node : ", n]; scanf["%d", &data]; insertAtN[data, n]; break; case 5: displayList[]; break; case 0: break; default: printf["Error! Invalid choice. Please choose between 0-5"]; } printf["\n\n\n\n\n"]; } return 0; } /** * Creates a doubly linked list of n nodes. * @n Number of nodes to be created */ void createList[int n] { int i, data; struct node *newNode; if[n >= 1] { /* * Create and link the head node */ head = [struct node *]malloc[sizeof[struct node]]; printf["Enter data of 1 node: "]; scanf["%d", &data]; head->data = data; head->prev = NULL; head->next = NULL; last = head; /* * Create and link rest of the n-1 nodes */ for[i=2; idata = data; newNode->prev = last; // Link new node with the previous node newNode->next = NULL; last->next = newNode; // Link previous node with the new node last = newNode; // Make new node as last/previous node } printf["\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n"]; } } /** * Display content of the list from beginning to end */ void displayList[] { struct node * temp; int n = 1; if[head == NULL] { printf["List is empty.\n"]; } else { temp = head; printf["DATA IN THE LIST:\n"]; while[temp != NULL] { printf["DATA of %d node = %d\n", n, temp->data]; n++; /* Move the current pointer to next node */ temp = temp->next; } } } /** * Inserts a new node at the beginning of the doubly linked list * @data Data of the first node i.e. data of the new node */ void insertAtBeginning[int data] { struct node * newNode; if[head == NULL] { printf["Error, List is Empty!\n"]; } else { newNode = [struct node *]malloc[sizeof[struct node]]; newNode->data = data; newNode->next = head; // Point to next node which is currently head newNode->prev = NULL; // Previous node of first node is NULL /* Link previous address field of head with newnode */ head->prev = newNode; /* Make the new node as head node */ head = newNode; printf["NODE INSERTED SUCCESSFULLY AT THE BEGINNING OF THE LIST\n"]; } } /** * Inserts a new node at the end of the doubly linked list * @data Data of the last node i.e data of the new node */ void insertAtEnd[int data] { struct node * newNode; if[last == NULL] { printf["Error, List is empty!\n"]; } else { newNode = [struct node *]malloc[sizeof[struct node]]; newNode->data = data; newNode->next = NULL; newNode->prev = last; last->next = newNode; last = newNode; printf["NODE INSERTED SUCCESSFULLY AT THE END OF LIST\n"]; } } /** * Inserts a node at any position in the doubly linked list * @data Data of the new node to be inserted * @position Position where to insert the new node */ void insertAtN[int data, int position] { int i; struct node * newNode, *temp; if[head == NULL] { printf["Error, List is empty!\n"]; } else { temp = head; i=1; while[inext; i++; } if[position == 1] { insertAtBeginning[data]; } else if[temp == last] { insertAtEnd[data]; } else if[temp!=NULL] { newNode = [struct node *]malloc[sizeof[struct node]]; newNode->data = data; newNode->next = temp->next; // Connect new node with n+1th node newNode->prev = temp; // Connect new node with n-1th node if[temp->next != NULL] { /* Connect n+1th node with new node */ temp->next->prev = newNode; } /* Connect n-1th node with new node */ temp->next = newNode; printf["NODE INSERTED SUCCESSFULLY AT %d POSITION\n", position]; } else { printf["Error, Invalid position\n"]; } } }

Happy coding