A doubly linked list is a type of linked list in which each node is connected to two other nodes instead of just one. This allows for bidirectional traversal of the list.
A doubly linked list is a data structure that consists of a set of nodes that are interconnected by links. Each node contains two fields:
The first and last nodes of a doubly linked list are called the head and tail nodes, respectively. The head node is the first node in the list, and the tail node is the last node in the list.
The next field of the tail node contains a reference to the head node, and the prev field of the head node contains a reference to the tail node. This allows for bidirectional traversal of the list.
Here is an example of a doubly linked list in the C programming language:
struct node {
int data;
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(int data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(int data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(curr_node->data == data) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%d ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
int main() {
insert_node(1);
insert_node(2);
insert_node(3);
insert_node(4);
insert_node(5);
print_list();
delete_node(3);
print_list();
return 0;
}
Implement a doubly linked list in the C programming language.
Implement the following operations on a doubly linked list:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(int data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(int data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(curr_node->data == data) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%d ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
int main() {
insert_node(1);
insert_node(2);
insert_node(3);
insert_node(4);
insert_node(5);
print_list();
delete_node(3);
print_list();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(int data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(int data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(curr_node->data == data) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%d ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
void reverse_list() {
struct node* curr_node = head;
struct node* temp_node = NULL;
while(curr_node != NULL) {
temp_node = curr_node->prev;
curr_node->prev = curr_node->next;
curr_node->next = temp_node;
curr_node = curr_node->prev;
}
if(temp_node != NULL) {
head = temp_node->prev;
}
}
int main() {
insert_node(1);
insert_node(2);
insert_node(3);
insert_node(4);
insert_node(5);
print_list();
delete_node(3);
print_list();
reverse_list();
print_list();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(int data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(int data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(curr_node->data == data) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%d ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
int main() {
int data;
while(1) {
printf("Enter an integer (Enter -1 to exit): ");
scanf("%d", &data);
if(data == -1) {
break;
}
insert_node(data);
}
print_list();
while(1) {
printf("Enter an integer to delete (Enter -1 to exit): ");
scanf("%d", &data);
if(data == -1) {
break;
}
delete_node(data);
}
print_list();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
char data[100];
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
void insert_node(char* data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
strcpy(new_node->data, data);
new_node->next = NULL;
new_node->prev = NULL;
if(head == NULL) {
head = new_node;
tail = new_node;
}
else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
void delete_node(char* data) {
struct node* curr_node = head;
while(curr_node != NULL) {
if(strcmp(curr_node->data, data) == 0) {
if(curr_node == head) {
head = head->next;
head->prev = NULL;
}
else if(curr_node == tail) {
tail = tail->prev;
tail->next = NULL;
}
else {
curr_node->prev->next = curr_node->next;
curr_node->next->prev = curr_node->prev;
}
free(curr_node);
break;
}
curr_node = curr_node->next;
}
}
void print_list() {
struct node* curr_node = head;
while(curr_node != NULL) {
printf("%s ", curr_node->data);
curr_node = curr_node->next;
}
printf("\n");
}
int main() {
char data[100];
while(1) {
printf("Enter a string (Enter -1 to exit): ");
scanf("%s", data);
if(strcmp(data, "-1") == 0) {
break;
}
insert_node(data);
}
print_list();
while(1) {
printf("Enter a string to delete (Enter -1 to exit): ");
scanf("%s", data);
if(strcmp(data, "-1") == 0) {
break;
}
delete_node(data);
}
print_list();
return 0;
}