Menú

Estructura de dades de llistes doblement enllaçades en C ++ amb il·lustració

  • Principal
  • Altres
  • Estructura de dades de llistes doblement enllaçades en C ++ amb il·lustració

doubly linked list data structure c with illustration

Proveu El Nostre Instrument Per Eliminar Problemes

Un tutorial en profunditat sobre una llista doblement enllaçada.

Una llista doblement enllaçada és una variació de la llista enllaçada individualment. Som conscients que la llista enllaçada individualment és una col·lecció de nodes amb cada node amb una part de dades i un punter que apunta al següent node.

Una llista doblement enllaçada també és una col·lecció de nodes. Aquí cada node consta d’una part de dades i dos indicadors. Un punter apunta al node anterior mentre que el segon apunta al node següent.

=> Consulteu aquí els tutorials de formació en profunditat C ++.

LLISTA DOBLEMENT ENLLAÇADA

Què aprendreu:

Doblement enllaçat a C ++

Com a la llista enllaçada individualment, la llista doblement enllaçada també té cap i cua. El punter anterior del capçal s'estableix en NULL, ja que és el primer node. El següent punter del node de cua s'estableix en NULL, ja que és l'últim node.

Al diagrama següent es mostra un disseny bàsic de la llista doblement enllaçada.

Un disseny bàsic de la llista doblement enllaçada

A la figura anterior, veiem que cada node té dos indicadors, un apuntant al node anterior i l’altre apuntant al següent. Només el primer node (cap) té el node anterior establert a nul i l'últim node (cua) té el següent punter a nul.

Com que la llista doblement enllaçada conté dos indicadors, és a dir, anterior i següent, podem recórrer-la cap a les direccions cap endavant i cap enrere. Aquest és el principal avantatge de la llista doblement enllaçada sobre la llista enllaçada individualment.

com afegir elements en una matriu java

Declaració

A la declaració d'estil C, es representa un node de la llista doblement enllaçada de la manera següent:

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

A part de la declaració anterior, també podem representar un node a la llista doblement enllaçada com a classe en C ++. Una llista doblement enllaçada es representa com una classe quan fem servir STL a C ++. També podem implementar una llista doblement enllaçada mitjançant una classe a Java.

Operacions bàsiques

A continuació es detallen algunes de les operacions que podem realitzar en una llista doblement enllaçada.

Inserció

L'operació d'inserció de la llista doblement enllaçada insereix un nou node a la llista enllaçada. En funció de la posició on s’ha d’inserir el nou node, podem fer les següents operacions d’inserció.

  • Inserció frontal - Insereix un nou node com a primer node.
  • Inserció al final - Insereix un nou node al final com a darrer node.
  • Inserció davant un node - Donat un node, insereix un nou node abans d’aquest node.
  • Inserció després d'un node - Donat un node, insereix un nou node després d’aquest node.

Supressió

L'operació de supressió elimina un node d'una posició determinada a la llista doblement enllaçada.

  • Supressió del primer node - Suprimeix el primer node de la llista
  • Supressió de l'últim node - Suprimeix l'últim node de la llista.
  • Supressió d'un node donades les dades - Donades les dades, l'operació fa coincidir les dades amb les dades del node de la llista enllaçada i suprimeix aquest node.

Transversal

El transversal és una tècnica per visitar cada node de la llista enllaçada. En una llista doblement enllaçada, tenim dos tipus de recorreguts, ja que tenim dos indicadors amb direccions diferents a la llista doblement enllaçada.

  • Recorregut cap endavant - La travessia es fa mitjançant el següent punter que es troba en la direcció cap endavant.
  • Recorregut cap enrere - La travessia es fa mitjançant el punter anterior que és la direcció cap enrere.

Revers

Aquesta operació inverteix els nodes de la llista doblement enllaçada de manera que el primer node es converteix en l'últim node mentre que l'últim node es converteix en el primer node.

Cerca

L’operació de cerca a la llista doblement enllaçada s’utilitza per cercar un node concret a la llista enllaçada. Amb aquest propòsit, hem de recórrer la llista fins que es trobin les dades coincidents.

Inserció

Inseriu un node a la part frontal

Inseriu un node a la part frontal

La inserció d’un nou node a la part frontal de la llista es mostra a la part superior. Com es va veure, el nou node N anterior es defineix com a nul. Dirigeix ​​cap al nou node. El següent indicador de N ara apunta a N1 i l'anterior de N1 que abans assenyalava Null ara apunta a N.

Inseriu un node al final

Inseriu un node al final

La inserció del node al final de la llista doblement enllaçada s’aconsegueix assenyalant el següent punter del nou node N a nul. El punter anterior de N apunta a N5. El punter 'següent' de N5 apunta cap a N.

Inseriu el node abans / després del node donat

Inseriu el node abans-després del node donat

Com es mostra al diagrama anterior, quan hem d'afegir un node abans o després d'un node concret, canviem els punters anterior i següent dels nodes abans i després per apuntar adequadament al nou node. A més, els nous indicadors de nodes s’assenyalen adequadament als nodes existents.

El següent programa C ++ mostra tots els mètodes anteriors per inserir nodes a la llista doblement enllaçada.

#include using namespace std; // A doubly linked list node struct Node { int data; struct Node* next; struct Node* prev; }; //inserts node at the front of the list void insert_front(struct Node** head, int new_data) { //allocate memory for New node struct Node* newNode = new Node; //assign data to new node newNode->data = new_data; //new node is head and previous is null, since we are adding at the front newNode->next = (*head); newNode->prev = NULL; //previous of head is new node if ((*head) != NULL) (*head)->prev = newNode; //head points to new node (*head) = newNode; } /* Given a node as prev_node, insert a new node after the given node */ void insert_After(struct Node* prev_node, int new_data) { //check if prev node is null if (prev_node == NULL) { coutnext = prev_node->next; //set next of prev node to newnode prev_node->next = newNode; //now set prev of newnode to prev node newNode->prev = prev_node; //set prev of new node's next to newnode if (newNode->next != NULL) newNode->next->prev = newNode; } //insert a new node at the end of the list void insert_end(struct Node** head, int new_data) { //allocate memory for node struct Node* newNode = new Node; struct Node* last = *head; //set last node value to head //set data for new node newNode->data = new_data; //new node is the last node , so set next of new node to null newNode->next = NULL; //check if list is empty, if yes make new node the head of list if (*head == NULL) { newNode->prev = NULL; *head = newNode; return; } //otherwise traverse the list to go to last node while (last->next != NULL) last = last->next; //set next of last to new node last->next = newNode; //set last to prev of new node newNode->prev = last; return; } // This function prints contents of linked list starting from the given node void displayList(struct Node* node) { struct Node* last; while (node != NULL) { coutnext; } if(node == NULL) cout

Sortida:

La llista doblement enllaçada és la següent:

1020304050NULL

El programa anterior construeix una llista doblement enllaçada inserint els nodes mitjançant tres mètodes d’inserció, és a dir, inserint el node a la part frontal, inserint el node al final i inserint el node després del node donat.

A continuació, demostrem la mateixa operació que una implementació de Java.

// Java Class for Doubly Linked List class Doubly_linkedList { Node head; // list head /* Doubly Linked list Node*/ class Node { int data; Node prev; Node next; //create a new node using constructor Node(int d) { data = d; } } // insert a node at the front of the list public void insert_front(int new_data) { /* 1. allocate node * 2. put in the data */ Node new_Node = new Node(new_data); /* 3. Make next of new node as head and previous as NULL */ new_Node.next = head; new_Node.prev = null; /* 4. change prev of head node to new node */ if (head != null) head.prev = new_Node; /* 5. move the head to point to the new node */ head = new_Node; } //insert a node after the given prev node public void Insert_After(Node prev_Node, int new_data) { //check that prev node is not null if (prev_Node == null) { System.out.println('The previous node is required,it cannot be NULL '); return; } //allocate new node and set it to data Node newNode = new Node(new_data); //set next of newNode as next of prev node newNode.next = prev_Node.next; //set new node to next of prev node prev_Node.next = newNode; //set prev of newNode as prev node newNode.prev = prev_Node; //set prev of new node's next to newnode if (newNode.next != null) newNode.next.prev = newNode; } // Add a node at the end of the list void insert_end(int new_data) { //allocate the node and set the data Node newNode = new Node(new_data); Node last = head; //set last as the head //set next of new node to null since its the last node newNode.next = null; //set new node as head if the list is null if (head == null) { newNode.prev = null; head = newNode; return; } //if list is not null then traverse it till the last node and set last next to last while (last.next != null) last = last.next; last.next = newNode; //set last next to new node newNode.prev = last; //set last as prev of new node } // display the contents of linked list starting from the given node public void displaylist(Node node) { Node last = null; while (node != null) { System.out.print(node.data + ''); last = node; node = node.next; } if(node == null) System.out.print('null'); System.out.println(); } } class Main{ public static void main(String[] args) { /* Start with the empty list */ Doubly_linkedList dll = new Doubly_linkedList(); // Insert 40. dll.insert_end(40); // Insert 20 at the beginning. dll.insert_front(20); // Insert 10 at the beginning. dll.insert_front(10); // Insert 50 at the end. dll.insert_end(50); // Insert 30, after 20. dll.Insert_After(dll.head.next, 30); System.out.println('Doubly linked list created is as follows: '); dll.displaylist(dll.head); } }

Sortida:

La llista doblement enllaçada creada és la següent:

com utilitzar Java per obrir un fitxer jar

1020304050 nul

Supressió

Es pot esborrar un node d'una llista doblement enllaçada des de qualsevol posició, com des de la part frontal, final o de qualsevol altra posició o dades donades.

En suprimir un node de la llista doblement enllaçada, primer reposicionem el punter que apunta cap a aquest node concret de manera que els nodes anterior i posterior no tinguin cap connexió amb el node a suprimir. A continuació, podem eliminar fàcilment el node.

Penseu en la següent llista doblement enllaçada amb tres nodes A, B, C. Considerem que hem de suprimir el node B.

llista doblement enllaçada amb tres nodes A, B, C

Com es mostra a la sèrie anterior del diagrama, hem demostrat la supressió del node B de la llista enllaçada donada. La seqüència d'operació continua sent la mateixa fins i tot si el node és primer o darrer. L’única cura que s’ha de tenir en compte és que, en cas que se suprimeixi el primer node, el punter anterior del segon node es definirà com a nul.

De la mateixa manera, quan se suprimeixi l'últim node, el següent punter del node anterior es definirà com a nul. Si se suprimeixen entre nodes, la seqüència serà la següent.

Abandonem el programa per esborrar un node d’una llista doblement enllaçada. Tingueu en compte que la implementació seguirà les línies de la implementació d’inserció.

Llista inversa doblement enllaçada

Invertir una llista doblement enllaçada és una operació important. En això, simplement intercanviem els indicadors anterior i següent de tots els nodes i també intercanviem els indicadors cap i cua.

A continuació es mostra una llista doblement enllaçada:

Invertiu la llista doblement enllaçada

Després de la implementació de C ++ es mostra la llista doblement enllaçada inversa.

#include using namespace std; //node declaration for doubly linked list struct Node { int data; struct Node *prev, *next; }; Node* newNode(int val) { Node* temp = new Node; temp->data = val; temp->prev = temp->next = nullptr; return temp; } void displayList(Node* head) { while (head->next != nullptr) { cout next; } cout next = *head; (*head)->prev = temp; (*head) = temp; } // reverse the doubly linked list void reverseList(Node** head) { Node* left = *head, * right = *head; // traverse entire list and set right next to right while (right->next != nullptr) right = right->next; //swap left and right data by moving them towards each other till they meet or cross while (left != right && left->prev != right) { // Swap left and right pointer data swap(left->data, right->data); // Advance left pointer left = left->next; // Advance right pointer right = right->prev; } } int main() { Node* headNode = newNode(5); insert(&headNode, 4); insert(&headNode, 3); insert(&headNode, 2); insert(&headNode, 1); cout << 'Original doubly linked list: ' << endl; displayList(headNode); cout << 'Reverse doubly linked list: ' << endl; reverseList(&headNode); displayList(headNode); return 0; }

Sortida:

Llista original doblement enllaçada:

Gener 2 3 4 5

Invertiu la llista doblement enllaçada:

Maig 4 3 2 1

Aquí intercanviem els punteres esquerre i dret i els movem l'un cap a l'altre fins que es troben o es creuen. A continuació, es canvien el primer i l'últim node.

El següent programa és la implementació de Java per invertir una llista doblement enllaçada. En aquest programa també fem ús de l'intercanvi dels nodes esquerre i dret com vam fer al nostre programa anterior.

// Java Program to Reverse a doubly linked List using Data Swapping class Main{ static class Node { int data; Node prev, next; }; static Node newNode(int new_data) { Node temp = new Node(); temp.data = new_data; temp.prev = temp.next = null; return temp; } static void displayList(Node head) { while (head.next != null) { System.out.print(head.data+ ' '); head = head.next; } System.out.println( head.data ); } // Insert a new node at the head of the list static Node insert(Node head, int new_data) { Node temp = newNode(new_data); temp.next = head; (head).prev = temp; (head) = temp; return head; } // Function to reverse the list static Node reverseList(Node head) { Node left = head, right = head; // traverse the list, set right pointer to end of list while (right.next != null) right = right.next; // move left and right pointers and swap their data till they meet or cross each other while (left != right && left.prev != right) { // Swap data of left and right pointer int t = left.data; left.data = right.data; right.data = t; left = left.next; // Advance left pointer right = right.prev; // Advance right pointer } return head; } public static void main(String args[]) { Node headNode = newNode(5); headNode = insert(headNode, 4); headNode = insert(headNode, 3); headNode = insert(headNode, 2); headNode = insert(headNode, 1); System.out.println('Original doubly linked list:'); displayList(headNode); System.out.println('Reversed doubly linked list:'); headNode=reverseList(headNode); displayList(headNode); } }

Sortida:

Llista original doblement enllaçada:

Gener 2 3 4 5

Llista doblement enllaçada invertida:

Maig 4 3 2 1

Avantatges / desavantatges respecte a la llista enllaçada individualment

Analitzem alguns dels avantatges i desavantatges de la llista doblement enllaçada sobre la llista enllaçada individualment.

Avantatges:

  • La llista doblement enllaçada es pot recórrer cap endavant i cap enrere, a diferència de la llista enllaçada individualment que només es pot recórrer en la direcció cap endavant.
  • L'operació de supressió en una llista doblement enllaçada és més eficient en comparació amb la llista individual quan es dóna un node determinat. En una llista enllaçada individualment, ja que necessitem un node anterior per eliminar el node donat, de vegades hem de recórrer la llista per trobar el node anterior. Això arriba al rendiment.
  • L'operació d'inserció es pot fer fàcilment en una llista doblement enllaçada en comparació amb la llista enllaçada individualment.

Desavantatges:

  • Com que la llista doblement enllaçada conté un punter addicional més, és a dir, anterior, l’espai de memòria ocupat per la llista doblement enllaçada és més gran en comparació amb la llista enllaçada individualment.
  • Com que hi ha dos indicadors, és a dir, anterior i següent, totes les operacions realitzades a la llista doblement enllaçada han de tenir cura d’aquests indicadors i mantenir-los, donant lloc a un coll d’ampolla de rendiment.

Aplicacions de la llista doblement enllaçada

Es pot aplicar una llista doblement enllaçada en diversos escenaris i aplicacions de la vida real, tal com es descriu a continuació.

  • Un joc de cartes d’un joc és un exemple clàssic d’una llista doblement enllaçada. Tenint en compte que cada carta d’una baralla té la carta anterior i la següent disposades de manera seqüencial, aquesta baralla de cartes es pot representar fàcilment mitjançant una llista doblement enllaçada.
  • Historial / memòria cau del navegador: la memòria cau del navegador té una col·lecció d’URL i es pot navegar mitjançant els botons endavant i enrere. Un altre bon exemple que es pot representar com una llista doblement enllaçada.
  • L'ús més recent (MRU) també es pot representar com una llista doblement enllaçada.
  • Altres estructures de dades com Stacks, taula de hash, l'arbre binari també es pot construir o programar mitjançant una llista doblement enllaçada.

Conclusió

Una llista doblement enllaçada és una variació de la llista enllaçada individualment. Es diferencia de la llista enllaçada individualment en què cada node conté un punter addicional al node anterior juntament amb el següent.

Aquesta presència d'un punter addicional facilita les operacions d'inserció, eliminació de la llista doblement enllaçada, però al mateix temps requereix memòria addicional per emmagatzemar aquests indicadors addicionals.

Com ja s'ha comentat, la llista doblement enllaçada té diversos usos en escenaris en temps real com ara memòria cau del navegador, MRU, etc. També podem representar altres estructures de dades com arbres, taules de hash, etc. mitjançant una llista doblement enllaçada.

Al nostre següent tutorial, aprendrem més sobre la llista enllaçada circular.

=> Llegiu aquí la popular sèrie de formació C ++.

Lectura recomanada

^