Node form

struct DNode {
    int data;
    struct DNode *previous, *next;
};

Insert between neighbours

For a new node between left and right, set new->previous = left and new->next = right. If left exists, set left->next = new; otherwise update head. If right exists, set right->previous = new; otherwise update tail. Both directions must describe the same sequence.

Delete a known node

Link its predecessor’s next to its successor when a predecessor exists, otherwise update head. Link its successor’s previous to its predecessor when a successor exists, otherwise update tail. Only after reconnecting both sides should the removed owned node be freed.

Traversal

Starting from head and following next displays forward order. Starting from tail and following previous displays reverse order. Do not dereference missing boundary neighbours; head->previous and tail->next are normally NULL in this non-circular form.

Complexity and trade-off

Deleting a known node uses O(1) link work because its predecessor is directly available. Searching by key still takes O(n). Nodes require an extra pointer compared with a singly linked representation, and each update must maintain more links. A single-node deletion sets both head and tail to NULL.

Diagram or flowchart

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *previous, *next; };
struct List { struct Node *head, *tail; };
int append(struct List *list, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = NULL; node->previous = list->tail;
    if (list->tail != NULL) { list->tail->next = node; } else { list->head = node; }
    list->tail = node; return 1;
}
void remove_node(struct List *list, struct Node *node)
{
    if (node == NULL) { return; }
    if (node->previous != NULL) { node->previous->next = node->next; } else { list->head = node->next; }
    if (node->next != NULL) { node->next->previous = node->previous; } else { list->tail = node->previous; }
    free(node);
}
void destroy(struct List *list)
{
    while (list->head != NULL) { remove_node(list, list->head); }
}

int main(void)
{
    struct List list = {NULL, NULL};
    for (int i = 10; i <= 30; i += 10) {
        if (!append(&list, i)) { destroy(&list); puts("Allocation failed"); return 1; }
    }
    remove_node(&list, list.head->next);
    for (struct Node *p = list.head; p != NULL; p = p->next) { printf("%d%s", p->data, p->next == NULL ? "\n" : " "); }
    for (struct Node *p = list.tail; p != NULL; p = p->previous) { printf("%d%s", p->data, p->previous == NULL ? "\n" : " "); }
    destroy(&list);
    return 0;
}

10 30
30 10