Esta página se tradujo automáticamente con la API de traducción de Google Cloud.
Algunas páginas se pueden leer mejor en su totalidad.
Una lista doblemente enlazada es un tipo de lista enlazada en la que cada nodo está conectado a otros dos nodos en lugar de a uno solo. Esto permite el recorrido bidireccional de la lista.
Una lista doblemente enlazada es una estructura de datos que consiste en un conjunto de nodos que están interconectados por enlaces. Cada nodo contiene dos campos:
El primer y el último nodo de una lista doblemente enlazada se denominan nodos cabeza y cola, respectivamente. El nodo principal es el primer nodo de la lista y el nodo final es el último nodo de la lista.
El campo siguiente del nodo final contiene una referencia al nodo principal y el campo anterior del nodo principal contiene una referencia al nodo final. Esto permite el recorrido bidireccional de la lista.
Aquí hay un ejemplo de una lista doblemente enlazada en el lenguaje de programación C:
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;
}
Implementar una lista doblemente enlazada en el lenguaje de programación C.
Implemente las siguientes operaciones en una lista doblemente enlazada:
#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;
}