Doubly Linked Lists

A doubly linked list is a data structure in which each element of the list is linked to both the element before it and the element after it. In C, a doubly linked list can be implemented using a structure that contains two pointers, one to the previous element in the list and one to the next element in the list.

Here is an example of a doubly linked list in C:

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

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

struct node *head = NULL;

void insert_at_beginning(int data) {
  struct node *new_node = (struct node*) malloc(sizeof(struct node));
  new_node->data = data;
  new_node->prev = NULL;
  new_node->next = head;
  head = new_node;
}

void insert_at_end(int data) {
  struct node *new_node = (struct node*) malloc(sizeof(struct node));
  new_node->data = data;
  new_node->next = NULL;
  if (head == NULL) {
    new_node->prev = NULL;
    head = new_node;
    return;
  }
  struct node *temp = head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = new_node;
  new_node->prev = temp;
}

void print_list() {
  struct node *temp = head;
  printf("List: ");
  while (temp != NULL) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  printf("\n");
}

int main() {
  insert_at_beginning(1);
  insert_at_end(2);
  insert_at_end(3);
  print_list();
  return 0;
}

In this example, the structure node represents a node in the doubly linked list. Each node contains an int value data, a pointer to the previous node in the list (prev), and a pointer to the next node in the list (next).

The head the pointer points to the first element in the list. The insert_at_beginning function adds a new node to the beginning of the list, and the insert_at_end function adds a new node to the end of the list. The print_list function displays the elements in the list.

This is just one example of how to implement a doubly linked list in C. There are many variations and optimizations that can be made to this basic structure, but the basic idea is the same: each node in the list contains pointers to both the previous node and the next node.