A lista enlazada es un tipo de estructura de datos dinámica lineal que utilizamos para almacenar elementos de datos. Las matrices también son un tipo de estructura de datos lineal donde los elementos de datos se almacenan en bloques de memoria continuos.
A diferencia de las matrices, la lista enlazada no necesita almacenar elementos de datos en regiones o bloques de memoria contiguos.
A lista enlazada está compuesto por elementos conocidos como 'Nodos' que se dividen en dos partes. El primer componente es la parte donde almacenamos los datos reales y el segundo es una parte donde almacenamos el puntero al siguiente nodo. Este tipo de estructura se conoce como ' lista enlazada individualmente .'
Lista enlazada en C++
Este tutorial analizará en profundidad la lista de enlaces individuales.
La estructura de una lista enlazada individualmente se ilustra en el siguiente diagrama.
- Como hemos visto en la parte anterior, el primer nodo de la lista enlazada se conoce como 'cabeza', mientras que el último nodo se llama 'cola'. Debido a que no se especifica ninguna dirección de memoria en el último nodo, el nodo final de la lista vinculada tendrá un puntero siguiente nulo.
- Debido a que cada nodo incluye un puntero al siguiente nodo, no es necesario conservar los elementos de datos de la lista vinculada en ubicaciones contiguas. Los nodos pueden estar dispersos por toda la memoria. Debido a que cada nodo tiene la dirección del siguiente, podemos acceder a los nodos cuando queramos.
- Podemos agregar y eliminar rápidamente elementos de datos de la lista conectada. Como resultado, la lista enlazada puede aumentar o contraerse dinámicamente. La lista vinculada no tiene una cantidad máxima de elementos de datos que puede contener. Como resultado, podemos agregar tantos elementos de datos como queramos a la lista vinculada siempre que haya RAM disponible.
- Debido a que no tenemos que especificar de antemano cuántos elementos necesitamos en la lista vinculada, la lista vinculada ahorra espacio en la memoria además de ser fácil de insertar y eliminar. El único espacio utilizado por una lista enlazada es para almacenar el puntero al siguiente nodo, lo que añade algo de coste.
A continuación, repasaremos las diversas operaciones que se pueden realizar en una lista vinculada.
1) Inserción
La lista enlazada se expande mediante la acción de agregarle. Aunque parezca simple, dada la estructura de la lista enlazada, sabemos que cada vez que se agrega un elemento de datos, debemos cambiar los punteros de siguiente de los nodos anterior y siguiente del nuevo elemento que hemos agregado.
El segundo aspecto a considerar es dónde se insertará el nuevo elemento de datos.
Hay tres lugares donde se puede agregar un elemento de datos a la lista vinculada.
a. Comenzando con la lista enlazada
A continuación se muestra una lista conectada de los números 2->4->6->8->10. El encabezado que apunta al nodo 2 ahora apuntará al nodo 1, y el siguiente puntero del nodo 1 tendrá la dirección de memoria del nodo 2, como se muestra en la siguiente ilustración, si agregamos un nuevo nodo 1 como el primer nodo en la lista. .
Como resultado, la nueva lista vinculada es 1->2->4->6->8->10.
b. Después del nodo dado
En este caso, se nos proporciona un nodo y debemos agregar un nuevo nodo detrás de él. La lista vinculada tendrá el siguiente aspecto si el nodo f se agrega a la lista vinculada a->b->c->d->e después del nodo c:
Por lo tanto, verificamos si el nodo especificado está presente en el diagrama anterior. Si está presente, se crea un nuevo nodo f. Después de eso, apuntamos el siguiente puntero del nodo c al nuevo nodo f. El siguiente puntero del nodo f ahora apunta al nodo d.
C. El último elemento de la lista enlazada
En el tercer caso, se agrega un nuevo nodo al final de la lista vinculada. Tenga en cuenta la lista enlazada a continuación: a->b->c->d->e, con la adición del nodo f al final. Después de agregar el nodo, la lista vinculada aparecerá así.
Como resultado, construimos un nuevo nodo f. El puntero de cola que conduce a nulo apunta a f, y el siguiente puntero del nodo f apunta a nulo. En el lenguaje de programación siguiente, hemos generado los tres tipos de funciones de inserción.
Una lista enlazada se puede declarar como estructura o como clase en C++. Una lista enlazada declarada como estructura es una declaración clásica de estilo C. Una lista enlazada se utiliza como clase en C++ moderno, principalmente cuando se utiliza la biblioteca de plantillas estándar.
La estructura se utilizó en la siguiente aplicación para declarar y generar una lista vinculada. Sus miembros serán datos y un puntero al siguiente elemento.
largo para encadenar java
Programa C++:
#include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -> data = nodeData; newNode1 -> next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -> next; prevNode -> next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -> data = nodeData; newNode1 -> next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -> next != NULL ) last = last -> next; last -> next = newNode1; return; } void displayList ( struct Node *node ) { while ( node != NULL ) { cout <data <'; node="node" -> next; } if ( node== NULL) cout<next, 55 ); cout << 'final linked list: ' endl; displaylist (head); return 0; } < pre> <p> <strong>Output:</strong> </p> <pre> Final linked list: 35-->25-->55-->15-->45-->null </pre> <h3>2) Deletion</h3> <p>Similar to insertion, deleting a node from a linked list requires many points from which the node might be eliminated. We can remove the linked list's first, last, or kth node at random. We must correctly update the next pointer and all other linked list pointers in order to maintain the linked list after deletion.</p> <p>In the following C++ implementation, we have two deletion methods: deleting the list's initial node and deleting the list's last node. We begin by adding nodes to the head of the list. The list's contents are then shown following each addition and deletion.</p> <p> <strong>C++ Program:</strong> </p> <pre> #include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <'; if ( temp="=" null ) cout << 'null' endl; head="deletingFirstNode" (head); 'linked list after deleting node' < next <data cout<<'null'<<endl; last data 'null'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data></pre></next,></data></data> 2) Eliminación
De manera similar a la inserción, eliminar un nodo de una lista vinculada requiere muchos puntos desde los cuales se podría eliminar el nodo. Podemos eliminar el primer, último o késimo nodo de la lista vinculada al azar. Debemos actualizar correctamente el siguiente puntero y todos los demás punteros de la lista vinculada para mantener la lista vinculada después de la eliminación.
En la siguiente implementación de C++, tenemos dos métodos de eliminación: eliminar el nodo inicial de la lista y eliminar el último nodo de la lista. Comenzamos agregando nodos al encabezado de la lista. El contenido de la lista se muestra después de cada adición y eliminación.
Programa C++:
#include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <\'; if ( temp="=" null ) cout << \'null\' endl; head="deletingFirstNode" (head); \'linked list after deleting node\' < next <data cout<<\'null\'<<endl; last data \'null\'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data> Recuento de nodos
Mientras se recorre la lista vinculada, se puede realizar el proceso de contar el número de nodos. En el enfoque anterior, vimos que si necesitábamos insertar/eliminar un nodo o mostrar el contenido de la lista vinculada, teníamos que recorrer la lista vinculada desde el principio.
Configurar un contador e incrementarlo a medida que recorremos cada nodo nos proporcionará la cantidad de nodos en la lista vinculada.
Diferencias entre matriz y lista enlazada:
| Formación | Lista enlazada |
|---|---|
| Las matrices tienen un tamaño definido. | El tamaño de la lista enlazada es variable. |
| Insertar un nuevo elemento es difícil. | La inserción y eliminación son más sencillas. |
| Se permite el acceso de forma aleatoria. | No es posible el acceso aleatorio. |
| Los elementos están relativamente cerca o contiguos. | Los elementos no son contiguos. |
| No se requiere espacio adicional para el siguiente puntero. | El siguiente puntero requiere memoria adicional. |
Funcionalidad
Dado que las listas enlazadas y las matrices son estructuras de datos lineales que contienen objetos, se pueden utilizar de manera similar para la mayoría de las aplicaciones.
Los siguientes son algunos ejemplos de aplicaciones de listas enlazadas:
- Las pilas y colas se pueden implementar mediante listas vinculadas.
- Cuando necesitamos expresar gráficos como listas de adyacencia, podemos usar una lista vinculada para implementarlos.
- También podemos usar una lista vinculada para contener un polinomio matemático.
- En el caso del hash, se emplean listas enlazadas para implementar los depósitos.
- Cuando un programa requiere una asignación de memoria dinámica, podemos utilizar una lista vinculada porque las listas vinculadas son más eficientes en este caso.
Conclusión
Las listas enlazadas son estructuras de datos que se utilizan para contener elementos de datos en forma lineal pero no contigua. Una lista enlazada se compone de nodos con dos componentes cada uno. El primer componente se compone de datos, mientras que la segunda mitad tiene un puntero que almacena la dirección de memoria del siguiente miembro de la lista.
Como señal de que la lista vinculada ha finalizado, el último elemento de la lista tiene su siguiente puntero establecido en NULL. El Jefe es el primer elemento de la lista. La lista vinculada permite una variedad de acciones como inserción, eliminación, recorrido, etc. Se prefieren las listas enlazadas a las matrices para la asignación de memoria dinámica.
Las listas enlazadas son difíciles de imprimir o recorrer porque no podemos acceder a los elementos aleatoriamente como las matrices. En comparación con las matrices, los procedimientos de inserción y eliminación son menos costosos.
En este tutorial, aprendimos todo lo que hay que saber sobre las listas enlazadas lineales. Las listas enlazadas también pueden ser doblemente enlazadas o circulares. En nuestros próximos tutoriales, revisaremos estas listas en detalle.