Doubly Linked List Program in C

Memory Representation of a Doubly Linked List

A doubly linked list is composed of nodes, where each node contains three parts:

1. Data Field: Stores the actual data of the node.
2. Prev Pointer: Points to the previous node in the list.
3. Next Pointer: Points to the next node in the list.

In memory, these nodes are dynamically allocated and linked together in a way that allows traversal in both directions. The Prev pointer of the first node is set to NULL, while the Next pointer of the last node is also set to NULL.

Here’s a visual representation of a doubly linked list:

NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL

The double linkage ensures easy insertion and deletion at both ends and any position within the list.

Operations on Doubly Linked List

The table below summarizes the common operations performed on a doubly linked list along with their descriptions:

Create a Doubly Linked List in C

To create a doubly linked list in C, we first need to define the structure of a node. Each node in a doubly linked list contains three components: a data element to store the actual value, a pointer to the previous node, and a pointer to the next node.

For example: 

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

In this example, we define a structure named `Node` that represents a node in the doubly linked list. The `data` member is an integer that holds the node's value. The `prev` and `next` members are pointers to the previous and next nodes, respectively, and are of type `struct Node*`.

Representation of Doubly Linked List Node in C:

Let’s see how we can represent a doubly linked list node in C using a structure:

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

Let's understand the components of the `Node` structure:

1. `data`: This member represents the data element stored in the node. In this example, it is an integer (`int`), but it can be of any data type depending on the specific requirements of the doubly linked list.
 

2. `prev`: This member is a pointer to the previous node in the doubly linked list. It is of type `struct Node*`, which means it can store the address of another node of the same structure. By using this pointer, we can traverse the list in the backward direction.
 

3. `next`: This member is a pointer to the next node in the doubly linked list. Similar to `prev`, it is also of type `struct Node*`. It allows us to traverse the list in the forward direction.

By defining the `Node` structure in this way, we create a blueprint for each node in the doubly linked list. We can create multiple instances of this structure to represent different nodes and link them together using the `prev` and `next` pointers.

Creating a Node of Doubly Linked List

To create a new node in a doubly linked list, we need to allocate memory for the node and initialize its members. Let’s see an example of how to create a new node:

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

In this code, we define a function named `createNode` that takes an integer `value` as a parameter and returns a pointer to the newly created node.

Let's go through the steps:

1. We use `malloc()` to dynamically allocate memory for a new node of size `sizeof(struct Node)`. The returned pointer is cast to `struct Node*` to match the type of the node.

2. We assign the `value` parameter to the `data` member of the new node using the arrow operator (`->`).
 

3. We initialize the `prev` and `next` pointers of the new node to `NULL`. This indicates that the node is not yet linked to any other nodes in the doubly linked list.
 

4. Finally, we return the pointer to the newly created node.
 

By using this `createNode` function, we can easily create new nodes with the desired data value whenever we need to add elements to the doubly linked list.

For example, to create a new node with the value 10, we can call the function as follows:

struct Node* myNode = createNode(10);

This will create a new node with the data value 10, and the `myNode` pointer will point to that node.

Shortening the Node Declaration

To make the code more concise and easier to read, we can use a typedef to create an alias for the `struct Node` type. By doing this, we can avoid writing `struct` repeatedly when declaring variables of type `struct Node*`.

Let’s look at an example of how to use typedef to shorten the node declaration:

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

In this code snippet, we use the `typedef` keyword to create an alias named `Node` for the `struct Node` type. Now, instead of writing `struct Node*` everywhere, we can simply use `Node*` to declare pointers to nodes.

With this typedef, we can rewrite the `createNode` function as follows:

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

As you can see, the code becomes cleaner and more readable. We can now use `Node*` instead of `struct Node*` when declaring pointers to nodes.

For example, to create a new node with the value 20, we can write:

Node* myNode = createNode(20);

This creates a new node with the data value 20, and `myNode` is a pointer of type `Node*` pointing to that node.

Chaining/Linking the Nodes of the Doubly Linked List

Once we have created individual nodes, we need to link them together to form a doubly linked list. Each node should be connected to its previous and next nodes using the `prev` and `next` pointers, respectively.

For example: 

void linkNodes(Node* node1, Node* node2) {
    node1->next = node2;
    node2->prev = node1;
}

In this code snippet, we define a function named `linkNodes` that takes two pointers to nodes (`node1` and `node2`) as parameters. The purpose of this function is to establish the links between the two nodes.

Let's understand the mechanism:

1. We set the `next` pointer of `node1` to point to `node2`. This means that `node2` becomes the next node of `node1`.
 

2. We set the `prev` pointer of `node2` to point to `node1`. This means that `node1` becomes the previous node of `node2`.

By linking the nodes in this way, we establish a bidirectional connection between them. Each node now has a reference to its previous and next nodes, allowing for traversal in both directions.

For example, to link three nodes (`node1`, `node2`, and `node3`) together, we can use the `linkNodes` function as follows:

Node* node1 = createNode(10);
Node* node2 = createNode(20);
Node* node3 = createNode(30);

linkNodes(node1, node2);
linkNodes(node2, node3);

After executing this code, `node1` is linked to `node2`, and `node2` is linked to `node3`. The resulting doubly linked list looks like this:

node1 <-> node2 <-> node3

The `prev` pointer of `node1` and the `next` pointer of `node3` remain `NULL` since they are the head and tail of the list, respectively.
 

Note: By linking nodes together using the `linkNodes` function, we can create a doubly linked list of any desired length.

C Program to Create a Doubly Linked List

#include <stdio.h>
#include <stdlib.h>

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


Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}
void linkNodes(Node* node1, Node* node2) {
    node1->next = node2;
    node2->prev = node1;
}
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
int main() {
    Node* head = createNode(10);
    Node* second = createNode(20);
    Node* third = createNode(30);

    linkNodes(head, second);
    linkNodes(second, third);

    printf("Doubly Linked List: ");
    printList(head);

    return 0;
}

You can also try this code with Online C Compiler

Run Code

In this code: 

1. We include the necessary header files: `stdio.h` for input/output operations and `stdlib.h` for memory allocation functions.
 

2. We define the `Node` structure using `typedef` as explained earlier.
 

3. We define the `createNode` function to create a new node with the given value and initialize its `prev` and `next` pointers to `NULL`.
 

4. We define the `linkNodes` function to establish the links between two nodes.
 

5. We define the `printList` function to traverse the doubly linked list and print the data of each node. It starts from the head and moves forward using the `next` pointer until it reaches the end of the list (i.e., `NULL`).
 

6. In the `main` function, we create three nodes (`head`, `second`, and `third`) with the values 10, 20, and 30, respectively.
 

7. We link the nodes together using the `linkNodes` function. `head` is linked to `second`, and `second` is linked to `third`.
 

8. Finally, we print the doubly linked list using the `printList` function, passing the `head` node as the starting point.

When we run this program, the output will be:

Doubly Linked List: 10 20 30

Time and Space Complexity

Time Complexity:

• Creating a new node: O(1)
  Creating a new node takes constant time as it involves allocating memory for a single node and initializing its members.
   
• Inserting a node at the beginning or end: O(1)
  Inserting a node at the beginning or end of a doubly linked list takes constant time because we only need to update a constant number of pointers.
   
• Inserting a node in the middle: O(n)
  Inserting a node in the middle of a doubly linked list requires traversing the list to find the desired position, which takes linear time in the worst case, where n is the number of nodes in the list.
   
• Deleting a node: O(1)
  Deleting a node from a doubly linked list takes constant time because we only need to update the pointers of the previous and next nodes.
   
• Searching for a node: O(n)
  Searching for a node in a doubly linked list requires traversing the list until the desired node is found, which takes linear time in the worst case.

Space Complexity

• The space complexity of a doubly linked list is O(n), where n is the number of nodes in the list.
   
• Each node in the list requires a constant amount of extra space to store the `prev` and `next` pointers, in addition to the data itself.

It's worth noting that the time complexity of inserting or deleting a node in a doubly linked list is generally more efficient than in a singly linked list because we have direct access to the previous node through the `prev` pointer. This eliminates the need to traverse the list to find the previous node.

Note: However, the important factor is that a doubly linked list requires more space compared to a singly linked list due to the additional `prev` pointer in each node.

Frequently Asked Questions

Can a doubly linked list be empty?

Yes, a doubly linked list can be empty, meaning it contains no nodes. In this case, the head pointer would be NULL.

Is it possible to traverse a doubly linked list in both directions?

Yes, a doubly linked list allows traversal in both forward and backward directions using the next and prev pointers, respectively.

How do you insert a node at a specific position in a doubly linked list?

To insert a node at a specific position, you need to traverse the list to find the desired position, create a new node, and update the pointers of the surrounding nodes accordingly.

Conclusion

In this article, we discussed the concept of doubly linked lists in C. We learned how to define a node's structure, create nodes, and link them together to form a doubly linked list. We also discussed the time and space complexity of common operations on doubly linked lists. Lastly, we saw a program to create a doubly linked list.