Concatenate two doubly linked list in C++

Introduction

In this post we will create doubly linked list example using C program. This example shows how to create, insert, append, remove nodes in doubly linked list using C program. We will use here Structure, which is a composite data type, in which we can define all data types under the same name or object. Size of the Structure is determined by computing the size of all data types, plus any internal padding. The key word struct is used to declare the Structure. In doubly linked list there are two links one is left and another is right link.

Nội dung chính Show

Introduction
Example with Source Code
Source Code

Example with Source Code

The complete source code for doubly linked list is given below:

/* * File: DoublyLinkedList.c * Author: https://roytuts.com */ #include <stdio.h> #include <stdlib.h> typedef struct node { struct node *left; int data; struct node *right; } node; /* *Create a new node */ node* createSingleNode(int data) { //allocate the memory for new node node* newNode = (node*) malloc(sizeof (node)); //error allocating memory to new node if (newNode == NULL) { printf("Error creating new node. So exiting...\n"); exit(0); } //put the data newNode->data = data; //point to the left and right node newNode->left = NULL; newNode->right = NULL; return newNode; } /* *Append new node at the end of the list */ node* appendNode(node* head, int data) { //if root node not found if (head == NULL) { return NULL; } //point to the first node node* current = head; //go to the last node while (current->right != NULL) { current = current->right; } //create the new node node* newNode = createSingleNode(data); //point current node to the new node current->right = newNode; newNode->left = current; newNode->right = NULL; return head; } /* * Create multiple nodes */ node* createMultipleNodes() { int i, noOfNodes, data; printf("Enter no. of nodes to be created: "); scanf("%d", &noOfNodes); printf("Enter data for node: "); scanf("%d", &data); node* head = createSingleNode(data); for (i = 1; i < noOfNodes; i++) { printf("Enter data for node: "); scanf("%d", &data); head = appendNode(head, data); } return head; } /* * Insert new node into the existing linked list */ node* insertNode(node* head, int position, node* newNode) { int j; node *current, *temp; //if root node not found if (head == NULL) { return NULL; } //if new node not found if (newNode == NULL) { return head; } //if new node to be inserted at first position if (position == 0) { newNode->right = head; head->left = newNode; head = newNode; return head; } //point to the first node current = head; for (j = 1; j < position && current != NULL; j++) { current = current->right; } if (current != NULL) { temp = current; newNode->right = temp->right; newNode->left = temp->left; temp->right = newNode; return head; } return NULL; } /* *Remove node at specified position */ node* removeNode(node* head, int position) { int j; node *current, *temp; //if root node not found if (head == NULL) { return NULL; } current = head; if (position == 0) { head = head->right; free(current); return head; } //make next pointer of temp node to NULL temp = current->right; for (j = 1; j < position && temp != NULL; j++) { current = temp; temp = temp->right; } if (current != NULL) { current->right = temp->right; temp->left = NULL; temp->right = NULL; free(temp); return head; } return NULL; } /* * Concatenate two LinkedLists */ node* concatenate(node* p, node* q) { node* r; if (p = NULL) { p = q; } r = p; while (r->right != NULL) { r = r->right; } q->left = r; r->right = q; return p; } /* * Reverse LinkedList */ node* reverse(node* head) { if (head == NULL || head->right == NULL) { return head; } node *p; p = head; while (p->right != NULL) { node *temp = p->right; p->right = p->left; p->left = temp; p = temp; } p->right = p->left; p->left = NULL; return p; } /* * Print LinkedList */ void printLinkedList(node* head) { //if root node not found if (head == NULL) { return; } node* current = head; printf("\n"); //traverse and print data while (current != NULL) { printf("%d", current->data); current = current->right; if (current != NULL) { printf("<->"); } } printf("\n"); head = current; } void main() { //create single node node* head = createSingleNode(5); //append node one after another appendNode(head, 10); appendNode(head, 15); appendNode(head, 20); appendNode(head, 25); printf("\nLinkedList with created nodes"); printLinkedList(head); //create multiple nodes head = createMultipleNodes(); //print nodes printf("\nLinkedList with created nodes"); printLinkedList(head); //create single node node* newNode = createSingleNode(25); //insert new node at position 2 head = insertNode(head, 2, newNode); //print nodes printf("\nLinkedList after inserting new node at position 2"); printLinkedList(head); //remove node from position 2 head = removeNode(head, 2); //print nodes printf("\nLinkedList after removing node from position 2"); printLinkedList(head); //reverse LinkedList head = reverse(head); //print nodes printf("\nLinkedList after reversing"); printLinkedList(head); }

Testing

When you run the above program you will see below output:

LinkedList with created nodes 5<->10<->15<->20<->25 Enter no. of nodes to be created: 5 Enter data for node: 1 Enter data for node: 2 Enter data for node: 3 Enter data for node: 4 Enter data for node: 5 LinkedList with created nodes 1<->2<->3<->4<->5 LinkedList after inserting new node at position 2 1<->2<->25<->3<->4<->5 LinkedList after removing node from position 2 1<->2<->3<->4<->5 LinkedList after reversing 5<->4<->3<->2<->1

In the above output, we initially created few nodes for the doubly or double linked list. Then again we ask the user how many nodes he/she wants to create. Next we perform few operations insertion, deletion and reverse on the double linked list.