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.