Doubly Linked List Program in C

Problem Description

Write a C program to show all operations in a doubly linked list.

What is a Linked List?

A linked list is a linear data structure in which data is stored in a non-contiguous memory location. Every node contains data and the address of the other node.

What is a Doubly Linked List in C?

A doubly linked list is a kind of linked list in which each node has three fields, one is data, and the addresses of the next and previous nodes. In a doubly linked list, traversing can happen in both forward and backward directions.

Example:

Problem Solution

To perform all the operations of a doubly linked list we have to create nodes dynamically in heap memory and store user data in them. We have to do the subsequent operations in a doubly linked list:

Doubly Linked List in C and its Operations:

Implementation of Doubly Linked List
Traversing the Doubly Linked List
Insertion of a Node at the Beginning of the List
Insertion of a Node at the End of the List
Insertion of a New Node at the Given Position
Deletion of a Node from the Beginning of the List
Deletion of a Node from the End of the List
Deletion of a Node from the Given Position
Search a Node Data in the List
Sorting the Doubly Linked List
Update a Node Data

Doubly Linked List Implementation

Here is source code of the C program to implement the doubly linked list and its operations. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/* 
 * C program to Implement the Doubly Linked List and its Operations
 */
 
#include<stdio.h>
#include<stdlib.h>
 
struct node
{
    struct node* prev;
    int data;
    struct node* next;
};
 
struct node* head = NULL;
 
/* functions prototyping */
void insert_at_beginning(int);
void insert_at_end(int);
void insert_at_position(int, int);
void delete_from_beginning();
void delete_from_position(int);
void delete_from_end();
void print_from_beginning();
void print_from_end(struct node*);
void search_data(int);
void update_node_data(int, int);
void list_sort();
 
/* helper functions */
struct node* create_node(int);
int size_of_list();
int getData();
int getPosition();
void empty_list_message();
void memory_error_message();
void invalid_position_message();
 
int main()
{
    char user_active = 'Y';
    int user_choice;
    int data, position;
 
    while (user_active == 'Y' || user_active == 'y')
    {
 
        printf("\n\n------ Doubly Linked List -------\n");
        printf("\n1. Insert a node at the beginning");
        printf("\n2. Insert a node at the end");
        printf("\n3. Insert a node at the given position");
        printf("\n\n4. Delete a node from the beginning");
        printf("\n5. Delete a node from the end");
        printf("\n6. Delete a node from the given position");
        printf("\n\n7. Print list from the beginning");
        printf("\n8. Print list from the end");
        printf("\n9. Search a node data");
        printf("\n10. Update a node data");
        printf("\n11. Sort the list");
        printf("\n12. Exit");
        printf("\n\n------------------------------\n");
 
        printf("\nEnter your choice: ");
        scanf("%d", &user_choice);
 
        printf("\n------------------------------\n");
        switch(user_choice)
        {
            case 1:
                printf("\nInserting a node at beginning");
                data = getData();
                insert_at_beginning(data);
                break;
 
            case 2:
                printf("\nInserting a node at end");
                data = getData();
                insert_at_end(data);
                break;
 
            case 3: 
                printf("\nInserting a node at the given position");
                data = getData();
                position = getPosition();
                insert_at_position(data, position);
                break;
 
            case 4: 
                printf("\nDeleting a node from beginning\n");
                delete_from_beginning();
                break;
 
            case 5: 
                printf("\nDeleting a node from end\n");
                delete_from_end();
                break;
 
            case 6: 
                printf("\nDelete a node from given position\n");
                position = getPosition();
                delete_from_position(position);
                break;
 
            case 7: 
                printf("\nPrinting the list from beginning\n\n");
                print_from_beginning();
                break;
 
            case 8: 
                printf("\nPrinting the list from end\n\n");
                print_from_end(head);
                printf("NULL\n");
                break;
 
            case 9:
                printf("\nSearching the node data");
                data = getData();
                search_data(data);
                break;
 
            case 10:
                printf("\nUpdating the node data");
                data = getData();
                position = getPosition();
                update_node_data(data, position);
                break;
 
            case 11:
                printf("\nSorting the list\n");
                list_sort();
                break;
 
            case 12:
                printf("\nProgram was terminated\n\n");
                return 0;
 
            default:
                printf("\n\tInvalid Choice\n");
        }
 
        printf("\n...............................\n");
        printf("\nDo you want to continue? (Y/N) : ");
        fflush(stdin);
        scanf(" %c", &user_active);
    }
 
    return 0;    
}
 
/* prints the message when the memory was not allocated */
void memory_error_message() 
{
    printf("\nMemory was not allocated!\n");
}
 
/* prints the message when the position is not valid for operation*/
void invalid_position_message()
{
    printf("\nInvalid position!\n");
}
 
/* prints the message when the linked list is empty */
void empty_list_message()
{
    printf("\nList is Empty!\n");
}
 
/* creates a new node dynamically */
struct node* create_node(int data)
{
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
 
    if (new_node == NULL)
    {
        return NULL;
    }
    else
    {
        new_node->prev = NULL;
        new_node->data = data;
        new_node->next = NULL;
    }
}
 
/* inserts a new node at beginning of the list */
void insert_at_beginning(int data)
{
    struct node* new_node = create_node(data);
 
    if (new_node == NULL)
    {
        memory_error_message();
        return;
    }
    else if(head == NULL)
    {
        head = new_node;
    }
    else
    {
        head->prev = new_node;
        new_node->next = head;
        head = new_node;
    }
    printf("\n* Node with data %d was inserted \n", data);
}
 
/* inserts a new node at the end of the list */
void insert_at_end(int data)
{
    struct node* new_node = create_node(data);
 
    if (new_node == NULL)
    {
        memory_error_message();
        return;
    }
    else if (head == NULL)
    {
        head = new_node;
    }
    else
    {
        struct node* temp = head;
        //traverse to the last node
        while (temp->next != NULL)
        {
            temp = temp = temp->next;
        }
        temp->next = new_node;
        new_node->prev = temp;
    }
    printf("\n* Node with data %d was inserted \n", data);
}
 
/* inserts a new node at the given position */
void insert_at_position(int data, int pos)
{
    struct node* new_node = create_node(data);
    int size = size_of_list();
 
    if (new_node == NULL)
    {
        memory_error_message();  
        return;
    }
    else if (head != NULL && (pos < 1 || pos > size))
    {
        invalid_position_message();
        return;
    }
    else if (head == NULL && pos == 1)
    {
        head = new_node;
    }
    else if (head != NULL && pos == 1)
    {
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    }
    else
    {
 
        struct node* temp = head;
        int count = 1;
 
        //traverse to the before given position
        while (++count < pos)
        {
            temp = temp->next;
        }
 
        temp->next->prev = new_node;
        new_node->next = temp->next;
 
        temp->next = new_node;
        new_node->prev = temp;
    }
    printf("\n* Node with data %d was inserted \n", data);
}
 
/* deletes a node from the beginning of the list */
void delete_from_beginning()
{
    if (head == NULL)
    {
        empty_list_message();
        return;
    }
    struct node* temp = head;
    head = head->next;
    int data = temp->data;
 
    //free the memory from the heap
    free(temp);
 
    printf("\n* Node with data %d was deleted \n", data);
}
 
/* deletes a node from the end of the list */
void delete_from_end()
{
 
    if (head == NULL)
    {
        empty_list_message();
        return;
    }
    struct node* temp = head;
    int data = 0;
 
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
 
    if (temp->prev == NULL)
    {
        head = NULL;
    }
    else
    {
        temp->prev->next = temp->next;
    }
    data = temp->data;
 
    free(temp);
    printf("\n* Node with data %d was deleted \n", data);
}
 
/* deletes a node from the given position */
void delete_from_position(int pos)
{
 
    if (head == NULL)
    {
        empty_list_message();
        return;
    }
    int size = size_of_list();
    struct node* temp = head;
    int data = 0;
 
    if (pos < 1 || pos > size)
    {
        invalid_position_message();
        return;
    }
    else if (pos == 1)
    {
        head = head->next;
        data = head->data;
        free(temp);
        printf("\n* Node with data %d was deleted \n", data);
    }
    else
    {
        int count = 0;
 
        while (++count < pos)
        {
            temp = temp->next;
        }
 
        //update previous node
        temp->prev->next = temp->next;
 
        // if deleting the last node then just update the previous node
        if (pos != size)
        {
            //update next node
            temp->next->prev = temp->prev;
        }
        data = temp->data;
 
        //free memory
        free(temp);
 
        printf("\n* Node with data %d was deleted \n", data);
    }
}
 
/* prints the data of nodes from the beginning of the list */
void print_from_beginning()
{
    struct node* temp = head;
 
    while (temp != NULL)
    {
        printf("%d  ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}
 
/* prints the data of nodes from the end of the list */
void print_from_end(struct node* head)
{
    if (head == NULL)
    {
        return;
    }
 
    print_from_end(head->next);
    printf("%d  ", head->data);
}
 
/* search a data node with the given value */
void search_data(int data)
{
    struct node* temp = head;
    int position = 0;
    int flag = 0;
 
    while (temp != NULL)
    {
        position += 1;
        if (temp->data == data)
        {
            flag = 1;
            break;        
        }
        temp = temp->next;
    }
 
    if (flag == 0)
    {
        printf("\nNode with data %d was not found\n", data);
    }
    else
    {
        printf("\nNode found at %d position\n", position);
    }
}
 
/* updates a node from the given position */
void update_node_data(int data, int pos)
{
    if (head == NULL)
    {
        empty_list_message();
        return;
    }
 
    int size = size_of_list();
 
    if (pos < 1 || pos > size)
    {
        invalid_position_message();
        return;
    }
 
    struct node* temp = head;
    int count  = 1;
 
    while (++count < pos)
    {
        temp = temp->next;
    }
 
    temp->data = data;
 
    printf("\nNode Number %d was Updated!\n", pos);
}
 
/* sort the linked list data using insertion sort */
void list_sort()
{
    if (head == NULL)
    {
       empty_list_message();
       return;
    }
    struct node* temp1 = head;
    struct node* temp2 = head;
    int key = 0;
 
    while (temp1 != NULL)
    {
        key = temp1->data;
        temp2 = temp1;
 
        while (temp2->prev != NULL && temp2->prev->data > key)
        {
            temp2->data = temp2->prev->data;
            temp2 = temp2->prev;
        }
        temp2->data = key;
        temp1 = temp1->next;
    }
 
    printf("\nList was sorted!\n");
}
 
/* getting node data from the user */
int getData()
{
    int data;
    printf("\n\nEnter Data: ");
    scanf("%d", &data);
 
    return data;
}
 
/* getting node position from the user */
int getPosition()
{
    int position;
    printf("\nEnter Position: ");
    scanf("%d", &position);
 
    return position;
}
 
/* finding the size of the list */
int size_of_list()
{
    struct node* temp = head;
    int count = 0;
 
    while (temp != NULL)
    {
        count += 1;
        temp = temp->next;    
    }
 
    return count;
}

Program Functions Explanation

The Program uses many functions to do various kinds of operations. Here we have discussed the main functions with their time and space complexity. Assuming the list size is n, where n is the number of nodes in the doubly linked list.

1. Traversing the Doubly Linked List

Traversing is the process to visit each node at once from start to end. To traverse the doubly linked list, we have to follow the below steps:

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Take a temporary pointer temp and initialise with the head pointer.
Start iterating from start to end.
On every iteration print the data of the node.

Time Complexity: O(n)
To traverse the doubly linked list, we need to move from start to end, which is the size of the list.

Space Complexity: O(1)
Here the temporary variable is used to iterate the list. so the space complexity is O(1).

2. Insertion of a Node at the Beginning of the List

To insert the node at the beginning of the list requires the following steps:

Update the next pointer of the new node to the head node.
Change the previous pointer of the head node to the new node.
Update the head pointer to the node.

Example: Insert the new node with data 34 at the beginning in the given doubly linked list.

Given Doubly Linked and a new node with data 34:

Step 1: Update the next pointer of the new node to the head node.

Step 2: Change the previous pointer of the head node to the new node.

Step 3: Update the head pointer to the new node.

Time Complexity: O(1)
Since no traversing occurred in this operation, it takes constant time to insert the node at the beginning.

Space Complexity: O(1)
A temporary variable is taken so space complexity is constant.

Run Time Testcases

In this case, we are inserting the nodes from the beginning of the doubly linked list.

 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 1
------------------------------
Inserting a node at beginning 
 
Enter Data: 88
 
* Node with data 88 was inserted 
...............................  
 
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 1
------------------------------
Inserting a node at beginning 
 
Enter Data: 34
 
* Node with data 34 was inserted 
...............................  
 
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
34 88
...............................  
 
Do you want to continue? (Y/N) : n

3. Insertion of a Node at the End of the List

Inserting a new node at the end of the doubly linked list needs to follow the below steps:

Traverse the list to the last node.
Update the next pointer of the last node to the new node.
Update the previous pointer of the new node to the last node.

Example: Insert a new node with data 99 at the end of the given doubly linked list.

Given the doubly linked list and a new node with data 99.

Step 1: Traverse the list to the last node.

Step 2: Update the next pointer of the last node to the new node.

Step 3: Update the previous pointer of the new node to the last node.

Time Complexity: O(n)
Since a traversing occurs from start to end node, it takes linear time to perform this operation.

Space Complexity: O(1)
A temporary variable is taken so space complexity is constant.

Run Time Testcases

In this case, we are inserting the nodes from the end of the doubly linked list.

------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
34 88
...............................  
 
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 2
------------------------------
Inserting a node at end
 
Enter Data: 90
 
* Node with data 90 was inserted
...............................  
 
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
34 88 90
...............................  
 
Do you want to continue? (Y/N) : n

4. Insertion of a New Node at the Given Position

To insert a new node at some position we need to do the following steps:

Traverse the list from start to the position K-1, where K is the given position.
Update the previous pointer of the Kth node to the new node.
Update the next pointer of the new node to the Kth node.
Update the next pointer of the K-1th node to the new node.
Update the previous pointer of the new node to the K-1th node.

Example: Add a new node at position 3 with the data 44.

Given a doubly linked list and a new node with data 44.

Step 1: Traverse the list from the start to the K-1th node. (here, K = 3)

Step 2: Update the previous pointer of the Kth node to the new node.

Step 3: Update the next pointer of the new node to the Kth node.

Step 4: Update the next pointer of the K-1th node to the new node.

Step 5: Update the previous pointer of the new node to the K-1th node.

Time Complexity: O(n)
Traversing from the start of the list to the given position. In the worst case, the position may be the last node.

Space Complexity: O(1)
Constant memory space is used to insert the new node at some given position.

Run Time Testcases

In this case, we are inserting the nodes at the particular position in the list.

------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
34 88 90
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 3
------------------------------
Inserting a node at the given position        
 
Enter Data: 67
 
Enter Position: 2
 
* Node with data 67 was inserted
 
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
34 67 88 90
...............................  
Do you want to continue? (Y/N) : y

5. Delete a Node from the Beginning of the List

Delete a node from the beginning requires following the given steps:

Store the head node into some temporary variable.
Update the head pointer to its next node.
Free the memory of the temporary variable.

Example: Delete the node with value 78 from the beginning in the given doubly linked list.

Step 1: Store the head node into some temporary variable temp.

Step 2: Update the head pointer to its next node.

Step 3: Free the memory of the temporary variable and update the prev pointer of the head node by NULL.

Time Complexity: O(1)
Since no traversing occurred in this operation, it takes constant time to delete the node at the beginning.

Space Complexity: O(1)
A temporary variable is taken so space is constant.

Run Time Testcases

In this case, we are deleting the nodes from the beginning of the doubly linked list.

------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
34 67 88 90
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 4
------------------------------
Deleting a node from beginning
 
* Node with data 34 was deleted
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
67 88 90
...............................  
Do you want to continue? (Y/N) : n

6. Delete a Node from the End of the List

To delete the node from the end of the list takes the following steps to complete this operation.

Traverse to the second last node of the list, let’s say K.
Store the K+1th node (last node) into some temporary variable.
Update the next pointer of the Kth node to NULL.
Free the memory of the temporary variable.

Example: delete the node having data 23 from the end of the doubly linked list.

Step 1: Traverse to the second last node of the list, let’s say K.

Step 2: Store the K+1th node (last node) into some temporary variable.

Step 3: Update the next pointer of the Kth node to NULL.

Step 4: Free the memory of the temporary variable lastNode.

Time Complexity: O(n)
Since there is traversing occurring in this operation, it takes linear time to delete the node at the end.

Space Complexity: O(1)
A temporary variable is taken so space is constant.

Run Time Testcases

In this case, we are deleting the nodes from the end of the doubly linked list.

------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
67 88 90
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 5
------------------------------
Deleting a node from end
 
* Node with data 90 was deleted 
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
67 88
...............................  
Do you want to continue? (Y/N) : n

7. Delete a Node from the Given Position

Deleting a node from the given position needs the following steps:

Traverse the list to the given position K.
Update the next pointer of the K-1th node to the K+1th node.
Update the previous pointer of the K+1th node to the K-1th node.
Free the memory of the temporary node which contains the Kth node.

Example: Delete the 2nd node having data 34 in the given doubly linked list.

Step 1: Traverse the list to the given position K.

Step 2: Update the next pointer of the K-1th node to the K+1th node

Step 3: Update the previous pointer of the K+1th node to the K-1th node.

Step 4: Free the memory of the temporary node which contains the Kth node.

Time Complexity: O(n)
Traversing from the start node to the given position takes linear time in the worst case when the position is the end node.

Space Complexity: O(1)
Space is constant because only temporary variables are taken to perform this operation.

------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
67 88 90
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 6
------------------------------
Delete a node from given position
 
Enter Position: 2
* Node with data 88 was Deleted
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
67 90
...............................  
Do you want to continue? (Y/N) : y

8. Search a Node Data in the List

Searching in a linked list is a technique to find out the node that has the desired data. Searching takes the following steps to get that node:

Traverse from the start of the node to the end of the node.
On each iteration check whether the node data is the same as we want.

Example: Search a node with value 34 in the given doubly linked list.

Start traversing from the head of the linked list and match the node data with the search key 34.

23 is not equal to 34 then move temp to the next node.

34 is equal to 34, so node has been found in the linked list then stops the iteration.

Time Complexity: O(n)
There traversing occurred in this operation so it takes linear time to search the node.

Space Complexity: O(1)
A temporary variable is taken so space complexity of doubly linked list is constant.

Run Time Testcases

In this case, we are searching for a node in the list.

------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 8
------------------------------
Printing the list from beginning
 
90 45 67
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 9
------------------------------
Searching the node data
 
Enter Data: 67
 
Found data at 3 position
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 9
------------------------------
Searching the node data
 
Enter Data: 31
 
Node with data 31 was not found
...............................  
Do you want to continue? (Y/N) : n

9. Sorting the Doubly Linked List

Sorting is a method to rearrange the elements in ascending or descending order. Here, we have sorted the linked list using the insertion sort technique. Here we will follow these steps:

Traverse from start to end node.
On every iteration, check whether it is at the right place or not. Traverse back for every element to put it at the correct position and shift every element forward.

Time Complexity: O(n²)
Time complexity of the insertion sort in the worst case is quadratic. In doubly linked list sorting, to place individual elements at the right position needs one another internal traversal.

Space Complexity: O(1)
There are temporary variables taken so the space used by this operation is constant.

Run Time Testcases

In this case, we are sorting the list.

------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
67 54 45 90
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 11
------------------------------
Sorting the list
 
List was sorted!
 
45 54 67 90
...............................  
Do you want to continue? (Y/N) : n

10. Update a Node Data in the Doubly Linked List

Updation is a process to change the current value of the node. To update the value of a node needs to follow these steps:

Reach to that node to which we want to update using list traversal.
Update the node value by the new value.

Example: Update the 3rd node value with 99 in the given linked list.

Step 1: Reach to the given position in the doubly linked list.

Step 2: Update the value of the temp node with the new value 99.

Time Complexity: O(n)
Reaching that node that wants to update takes n time in the worst case. So the time complexity for this operation is linear.

Space Complexity: O(1)
A temporary variable is taken so space is constant.

Run Time Testcases

In this case, we are updating a node data at a particular position.

<pre lang="text" cssfile="hk1_style">
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
67 45 90
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 10
------------------------------
Updating the node data
 
Enter Data: 44
 
Enter Position: 1
 
Node Number 1 was Updated!
...............................  
Do you want to continue? (Y/N) : y
 
------ Doubly Linked List -------
 
1. Insert a node at the beginning
2. Insert a node at the end      
3. Insert a node at the given position
 
4. Delete a node from the beginning   
5. Delete a node from the end
6. Delete a node from the given position
 
7. Print list from the beginning        
8. Print list from the end
9. Search a node data 
10. Update a node data
11. Sort the list     
12. Exit
 
------------------------------
Enter your choice: 7
------------------------------
Printing the list from beginning
 
44 67 45 90
...............................  
Do you want to continue? (Y/N) : n

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

« Prev - C Program Find the Length of Linked List without Recursion

» Next - C Program to Count the Occurrences of Elements in a Linked List without Recursion

Related Posts: