In this tutorial we will see algorithm and program to insert a given node at Beginning in the doubly linked list, at the End of doubly linked list and at the given location in doubly linked list.

## Insertion in Doubly Linked List Algorithm

### Insertion at the Beginning

**Create a New Node**:- Start by creating a new node. Allocate memory for it and set the
`data`

field with the given value. - Since it’s a new node, initially set both its
`next`

and`prev`

pointers to`NULL`

.

- Start by creating a new node. Allocate memory for it and set the
**Check if List is Empty**:- If the
`head`

(the first node of the list) is`NULL`

, it means the list is empty. - In this case, the new node is the only node in the list, so set
`head`

to this new node.

- If the
**Insert the New Node**:- If the list is not empty, then it already has at least one node.
- Set the
`next`

pointer of the new node to the current`head`

. This step links the new node to the existing list. - Set the
`prev`

pointer of the current head to the new node. This links the old head back to the new node. - Finally, update
`head`

to point to the new node, making it the new first node of the list.

### Insertion at the End

**Create a New Node**:- Similar to the first step above, create a new node and initialize it with the given data.

**Check if List is Empty**:- If the list is empty (
`head`

is`NULL`

), then make the new node the`head`

of the list.

- If the list is empty (
**Find the Last Node and Insert**:- If the list is not empty, traverse it to find the last node. Do this by iterating through the list until you find a node whose
`next`

pointer is`NULL`

. - Once you find the last node, set its
`next`

pointer to the new node. - Set the
`prev`

pointer of the new node to the last node. - The new node’s
`next`

remains`NULL`

since it’s now the last node in the list.

- If the list is not empty, traverse it to find the last node. Do this by iterating through the list until you find a node whose

### Insertion at a Specific Location

**Create a New Node**:- As before, start by creating a new node with the given data.

**Inserting at the Start**:- If the specified location is 1 (the beginning of the list), use the steps for inserting at the beginning.

**Traverse to the Specific Location**:- If the location is other than the start, begin at
`head`

and traverse the list. - Move through the list until you reach the node just before the desired position.
- It’s important to ensure that this position is valid, i.e., it’s not beyond the end of the list.

- If the location is other than the start, begin at
**Insert the New Node**:- Once you’re at the right spot, link the new node into the list.
- Set the
`next`

pointer of the new node to the next node in the list. - Set the
`prev`

pointer of the next node (if it exists) to the new node. - Update the
`next`

pointer of the node before the insertion point to point to the new node. - Finally, set the
`prev`

pointer of the new node to the node before the insertion point.

## C Program to Insert at Beginning, End and Given location in Doubly Linked List

```
#include <stdio.h>
#include <stdlib.h>
// Doubly linked list Structure
struct Node {
int data;
struct Node *next;
struct Node *prev;
};
typedef struct Node Node;
// Create a new node for Doubly Linked List
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
// Insert at the beginning of Doubly Linked List
void insertAtBegin(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
// Insert at the end of Doubly Linked List
void insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
// Insert at a specific location
void insertAtGivenLocation(Node** head, int data, int position) {
Node* newNode = createNode(data);
if (position == 1) {
insertAtBegin(head, data);
return;
}
Node* temp = *head;
for (int i = 1; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position is beyond the length of the list.\n");
return;
}
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next != NULL) {
temp->next->prev = newNode;
}
temp->next = newNode;
}
// Traverse and print the Doubly Linked List
void traverseDoublyLinkedList(Node* head) {
Node* temp = head;
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
Node* head = NULL;
insertAtBegin(&head, 20); // Insertion at beginning
insertAtGivenLocation(&head, 30, 1); // Insertion at position 1
insertAtEnd(&head, 10); // Insertion at the end
insertAtBegin(&head, 50); // Insertion at beginning
insertAtGivenLocation(&head, 60, 2); // Insertion at position 2
insertAtEnd(&head, 40); // Insertion at the end
traverseDoublyLinkedList(head);
return 0;
}
```

**Output**

Doubly Linked List: 50 60 30 20 10 40

### Insertion in Doubly Linked List Program Explanation

#### Node Structure Definition

```
struct Node {
int data;
struct Node *next;
struct Node *prev;
};
typedef struct Node Node;
```

**Purpose**: Defines the structure of each node in the doubly linked list.**Components**:`int data`

: Holds the data value of the node.`struct Node* next`

: A pointer to the next node in the list.`struct Node* prev`

: A pointer to the previous node in the list.

- The
`typedef`

is used to define`Node`

as an alias for`struct Node`

at the beginning. After that you can simply use`Node`

to refer to this structure.

#### createNode Function

```
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
```

**Purpose**: Creates a new node with given data.**Process**:- Allocates memory for a new node.
- Initializes the node’s data with the given value.
- Sets the
`next`

and`prev`

pointers of the node to`NULL`

. - Returns the newly created node.

#### insertAtBegin Function

```
void insertAtBegin(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
```

**Purpose**: Inserts a new node at the beginning of the list.**Process**:- Creates a new node.
- If the list is empty (
`head`

is`NULL`

), the new node becomes the head. - If the list is not empty, adjusts the pointers to insert the new node before the current head.

#### insertEnd Function

```
void insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
```

**Purpose**: Inserts a new node at the end of the list.**Process**:- Creates a new node.
- If the list is empty, the new node becomes the head.
- If the list is not empty, traverses to the last node and adjusts the pointers to add the new node at the end.

#### insertAtGivenLocation Function

```
void insertAtGivenLocation(Node** head, int data, int position) {
Node* newNode = createNode(data);
if (position == 1) {
insertAtBegin(head, data);
return;
}
Node* temp = *head;
for (int i = 1; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position is beyond the length of the list.\n");
return;
}
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next != NULL) {
temp->next->prev = newNode;
}
temp->next = newNode;
}
```

**Purpose**: Inserts a new node at a specified position in the list.**Process**:- Creates a new node.
- If the position is 1, uses
`insertBegin`

to insert at the start. - Otherwise, traverses to the node just before the desired position and adjusts the pointers to insert the new node.

#### traverseDoublyLinkedList Function

```
void traverseDoublyLinkedList(Node* head) {
Node* temp = head;
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
```

**Purpose**: Traverses the list and prints the data of each node.**Process**:- Starts from the head and moves through the list.
- Prints the data of each node until it reaches the end of the list.

#### main Function

```
int main() {
Node* head = NULL;
insertAtBegin(&head, 20); // Insertion at beginning
insertAtGivenLocation(&head, 30, 1); // Insertion at position 1
insertAtEnd(&head, 10); // Insertion at the end
insertAtBegin(&head, 50); // Insertion at beginning
insertAtGivenLocation(&head, 60, 2); // Insertion at position 2
insertAtEnd(&head, 40); // Insertion at the end
traverseDoublyLinkedList(head);
return 0;
}
```

**Purpose**: Demonstrates the functionality of the list.**Process**:- Initializes an empty list.
- Demonstrates insertion at the end, at the beginning, and at a specific position.
- Traverses the list to display its contents.

This tutorial has explained and demonstrated of managing a doubly linked list, from node creation to insertion at various ways and traversal.