En el caso de la lista doblemente enlazada simple , si tenemos que realizar la operación de inserción o eliminación al principio de la lista doblemente enlazada, al final de la lista doblemente enlazada, o entre los Nodes inicial y final de cada uno, necesitamos verifique las diferentes condiciones que hacen que el algoritmo sea complejo, por lo que para resolver este problema podemos usar una lista doblemente enlazada junto con los Nodes centinela .
¿Qué es un ganglio centinela?
Los Nodes centinela son Nodes especialmente diseñados que no contienen ni se refieren a ningún dato de la lista doblemente enlazada (esa estructura de datos).
Para simplificar las operaciones de inserción y eliminación en una lista doblemente enlazada, debemos agregar un Node centinela al principio de la lista doblemente enlazada y uno al final de la lista doblemente enlazada, como se muestra en el diagrama a continuación.
Lista doblemente enlazada con ganglios centinela
Como se muestra arriba, cada Node que no sea el Node centinela contiene el puntero al Node anterior y siguiente junto con los datos.
Ventaja del Node centinela:
La ventaja más significativa de usar los ganglios centinela en la lista doblemente enlazada:
- Al agregar los Nodes centinela a la lista doblemente enlazada ahora para la eliminación o inserción al principio, al final o entre los Nodes inicial y final de la lista enlazada, no necesitamos escribir las diferentes condiciones para cada uno.
- Todas estas operaciones se pueden realizar como la eliminación o inserción entre el Node inicial y final de una lista doblemente enlazada.
Estructura de una Lista Doblemente Enlazada usando Nodes centinela:
La estructura de cada Node y la creación del nuevo Node en una lista doblemente enlazada con ganglios centinela es la misma que la lista doblemente enlazada simple, como se muestra a continuación.
C++
// Each node contains the data,
// previous node pointer and
// the next node pointer
struct node {
int data;
struct node* next;
struct node* pre;
};
// To create a node, first define the node pointer
// and than assign the memory required by the node
// and return the pointer
struct node* createnode()
{
struct node* t;
t = (struct node*)malloc(sizeof(struct node));
return (t);
}
Operaciones sobre una lista doblemente enlazada usando Sentinel Nodes:
Las operaciones comunes en una lista doblemente enlazada son:
- Insertar nuevo Node
- Eliminar Node existente
- Mostrar todos los datos de los Nodes
1. Insertar un nuevo Node en una Lista Doblemente Vinculada utilizando Sentinel Nodes
La inserción de un nuevo Node en una lista doblemente enlazada se puede hacer de tres maneras, pero como hemos usado el Node centinela en la lista doblemente enlazada, por lo que no tenemos que escribir un algoritmo diferente para cada caso, tenemos que dar el ubicación del Node después de lo cual tenemos que agregar el nuevo Node a la lista vinculada como se muestra en el código.
- Insertar un nuevo Node al comienzo de la lista doblemente enlazada
En esto, estamos agregando el nuevo Node justo después del Node centinela principal. Básicamente, estamos agregando el nuevo Node al comienzo de la lista doblemente enlazada. Aún así, se comportará como la adición de un Node entre el Node inicial y final de la lista enlazada debido al Node centinela.
Inserción de Node al principio de la lista doblemente enlazada
- Insertar un nuevo Node en una posición dada en la lista enlazada
Como se muestra en el siguiente diagrama, estamos agregando un nuevo Node en el medio de la lista enlazada.
Inserción de Node en una posición dada en la lista doblemente enlazada
- Insertar un nuevo Node al final de la lista doblemente enlazada
En esto, estamos agregando el nuevo Node justo antes del Node centinela de la cola. Básicamente, estamos agregando el nuevo Node al final de la lista doblemente enlazada. Aún así, se comportará como la adición de un Node entre el Node inicial y final de la lista enlazada debido al Node centinela.
Inserción de Node al final de la lista doblemente enlazada
2. Elimine un Node existente en una lista doblemente enlazada usando Sentinel Nodes
La eliminación de un Node existente en una lista doblemente enlazada también se puede hacer de tres maneras. Aún así, como hemos utilizado el Node centinela en la lista doblemente enlazada, para no tener que escribir un algoritmo diferente para cada caso, tenemos que pasar la ubicación del Node que queremos eliminar.
- Eliminar un Node existente al comienzo de la lista doblemente enlazada
En esto, estamos eliminando un Node existente justo después del ganglio centinela principal. Básicamente, estamos eliminando un Node existente al comienzo de la lista doblemente enlazada. Aún así, se comportará como la eliminación de un Node entre el Node inicial y final de la lista enlazada debido al ganglio centinela.
Eliminación del Node inicial en una lista doblemente enlazada
- Eliminar un Node existente en una posición determinada de la lista vinculada
Como se muestra en el diagrama que se muestra a continuación, estamos eliminando un Node existente en una ubicación determinada de la lista vinculada.
Eliminación de un Node en una posición dada en la lista doblemente enlazada
- Eliminar un Node existente al final de la lista doblemente enlazada
En esto, estamos eliminando un Node existente justo antes del ganglio centinela de la cola. Básicamente, estamos eliminando un Node existente al final de la lista doblemente enlazada. Aún así, se comportará como la eliminación de un Node entre el Node inicial y final de la lista enlazada debido al ganglio centinela.
Eliminación del Node final en la lista doblemente enlazada
3. Muestre todos los datos de los Nodes en una lista doblemente enlazada usando Sentinel Nodes
Es lo mismo que la lista simple doblemente enlazada. Tenemos que recorrer todos los Nodes e imprimir los datos almacenados en ellos excepto los Nodes centinela.
Implementación: A continuación se muestra la implementación completa de la lista doblemente enlazada con Nodes centinela y la operación de inserción, eliminación y visualización.
C++
// C++ code to implement doubly-linked list
// using sentinel node
#include <bits/stdc++.h>
using namespace std;
int size = 0;
// Each node contains the data,
// previous node pointer and
// the next node pointer
struct node {
int data;
struct node* next;
struct node* pre;
};
// To create a node, first define the node pointer
// and than assign the memory required by ode
// and return the pointer
struct node* createnode()
{
struct node* t;
t = (struct node*)malloc(sizeof(struct node));
return (t);
}
// Function to display all the nodes
void display(struct node* head,
struct node* tail)
{
head = head->next;
cout << "\nThe linked list is :- ";
while (head != tail) {
cout << head->data << " ";
head = head->next;
}
}
// Function to insert a new node
void insertion(struct node* head,
struct node* tail,
int n, int value)
{
n--;
struct node *temp, *ptr;
ptr = head;
temp = createnode();
temp->data = value;
int i = 0;
// Run's until reach the node after
// which we have to add the new node
while (i < n) {
ptr = ptr->next;
i++;
}
temp->next = ptr->next;
temp->pre = ptr;
ptr->next = temp;
(temp->next)->pre = temp;
// Linked list size is increased by 1
size++;
}
// Function to delete an element
// from the doubly-linked list
void deletion(struct node* head,
struct node* tail, int n)
{
n--;
// If linked list is empty
if (head->next == tail) {
cout << "\nerror : linked list is empty";
return;
}
// If entered position is more
// than the size of the linked list
if (n >= size) {
cout << "\nerror : position is larger"
" than size of linked list";
return;
}
struct node* ptr = head;
struct node* temp;
int i = 0;
// Run's until reach the node whose
// next node have to deleted
while (i < n) {
ptr = ptr->next;
i++;
}
cout << "\nDeleting node at position "
<< n + 1 << " contains valude "
<< (ptr->next)->data;
temp = (ptr->next)->next;
ptr->next = temp;
temp->pre = ptr;
// Size of the linked list decreased by 1
size--;
}
// Driver code
int main()
{
// Here we are creating two sentinel nodes
// (does not contain any data)
struct node* head = createnode();
head->pre = NULL;
struct node* tail = createnode();
tail->pre = head;
tail->next = NULL;
head->next = tail;
int n;
// Declaring start position of goto section
start:
cout << "\n1. Insertion\n2. Deletion\n"
"3. Display\n0. Exit\n";
cin >> n;
switch (n) {
case 1:
// Insertion at the beginning
// of the Doubly linked list
insertion(head, tail, 1, 10);
display(head, tail);
// Insertion at the End
// of the Doubly linked list
insertion(head, tail, size + 1, 14);
display(head, tail);
// Inserting node in between
// the doubly linked list
insertion(head, tail, 2, 8);
display(head, tail);
cout << endl;
goto start;
break;
case 2:
// Deleting the node at location 2
deletion(head, tail,
2);
display(head, tail);
cout << endl;
// Deleting the first node
deletion(head, tail, 1);
display(head, tail);
cout << endl;
// Deleting the last node
deletion(head, tail, size);
display(head, tail);
cout << endl;
goto start;
case 3:
display(head, tail);
cout << endl;
goto start;
default:
break;
}
return 0;
}
Producción:
1.Insertion 2.Deletion 3.Display 0.Exit 1 The linked list is :- 10 The linked list is :- 10 14 The linked list is :- 10 8 14 1.Insertion 2.Deletion 3.Display 0.Exit 3 The linked list is :- 10 8 14 1.Insertion 2.Deletion 3.Display 0.Exit 2 Deleting node at position 2 contains valude 8 The linked list is :- 10 14 Deleting node at position 1 contains valude 10 The linked list is :- 14 Deleting node at position 1 contains valude 14 The linked list is :- 1.Insertion 2.Deletion 3.Display 0.Exit 0
Publicación traducida automáticamente
Artículo escrito por spacetechbytes y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA