- La lista enlazada se puede definir como una colección de objetos llamados nodos que se almacenan aleatoriamente en la memoria.
- Un nodo contiene dos campos, es decir, datos almacenados en esa dirección particular y el puntero que contiene la dirección del siguiente nodo en la memoria.
- El último nodo de la lista contiene un puntero al nulo.
Usos de la lista enlazada
- No es necesario que la lista esté presente de forma contigua en la memoria. El nodo puede residir en cualquier lugar de la memoria y vincularse para formar una lista. De esta forma se consigue un aprovechamiento optimizado del espacio.
- El tamaño de la lista está limitado al tamaño de la memoria y no es necesario declararlo con anticipación.
- El nodo vacío no puede estar presente en la lista vinculada.
- Podemos almacenar valores de tipos u objetos primitivos en la lista enlazada individualmente.
¿Por qué utilizar una lista vinculada en lugar de una matriz?
Hasta ahora, usábamos una estructura de datos de matriz para organizar el grupo de elementos que se almacenarán individualmente en la memoria. Sin embargo, Array tiene varias ventajas y desventajas que deben conocerse para poder decidir la estructura de datos que se utilizará en todo el programa.
La matriz contiene las siguientes limitaciones:
- El tamaño de la matriz debe conocerse de antemano antes de utilizarla en el programa.
- Aumentar el tamaño de la matriz es un proceso que requiere tiempo. Es casi imposible ampliar el tamaño de la matriz en tiempo de ejecución.
- Todos los elementos de la matriz deben almacenarse de forma contigua en la memoria. Para insertar cualquier elemento en la matriz es necesario desplazar todos sus predecesores.
La lista vinculada es la estructura de datos que puede superar todas las limitaciones de una matriz. Usar una lista vinculada es útil porque,
desventajas de internet
- Asigna la memoria dinámicamente. Todos los nodos de la lista vinculada se almacenan de forma no contigua en la memoria y se vinculan entre sí con la ayuda de punteros.
- El tamaño ya no es un problema ya que no necesitamos definir su tamaño en el momento de la declaración. La lista crece según la demanda del programa y se limita al espacio de memoria disponible.
Lista enlazada individualmente o cadena unidireccional
La lista enlazada individualmente se puede definir como la colección de un conjunto ordenado de elementos. El número de elementos puede variar según la necesidad del programa. Un nodo en la lista enlazada individualmente consta de dos partes: parte de datos y parte de enlace. La parte de datos del nodo almacena información real que será representada por el nodo, mientras que la parte de enlace del nodo almacena la dirección de su sucesor inmediato.
La cadena unidireccional o la lista enlazada individualmente solo se pueden recorrer en una dirección. En otras palabras, podemos decir que cada nodo contiene solo el siguiente puntero, por lo tanto no podemos recorrer la lista en la dirección inversa.
Considere un ejemplo donde las calificaciones obtenidas por el estudiante en tres materias se almacenan en una lista vinculada como se muestra en la figura.
fuentes para gimp
En la figura anterior, la flecha representa los enlaces. La parte de datos de cada nodo contiene las calificaciones obtenidas por el alumno en las diferentes materias. El último nodo de la lista se identifica mediante el puntero nulo que está presente en la parte de dirección del último nodo. Podemos tener tantos elementos como necesitemos, en la parte de datos de la lista.
Complejidad
| Estructura de datos | Complejidad del tiempo | Compledad espacial | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Promedio | El peor | El peor | |||||||
| Acceso | Buscar | Inserción | Supresión | Acceso | Buscar | Inserción | Supresión | ||
| Lista enlazada individualmente | en) | en) | yo(1) | yo(1) | En) | En) | O(1) | O(1) | En) |
Operaciones en lista enlazada individualmente
Hay varias operaciones que se pueden realizar en una lista enlazada individualmente. A continuación se proporciona una lista de todas estas operaciones.
Creación de nodos
struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); Inserción
La inserción en una lista enlazada individualmente se puede realizar en diferentes posiciones. Según la posición del nuevo nodo que se inserta, la inserción se clasifica en las siguientes categorías.
char tostring java
| SN | Operación | Descripción |
|---|---|---|
| 1 | Inserción al principio | Implica insertar cualquier elemento al principio de la lista. Solo necesitamos algunos ajustes de enlace para que el nuevo nodo encabece la lista. |
| 2 | Inserción al final de la lista. | Implica la inserción al final de la lista enlazada. El nuevo nodo se puede insertar como el único nodo de la lista o como el último. En cada escenario se implementan diferentes lógicas. |
| 3 | Inserción después del nodo especificado | Implica la inserción después del nodo especificado de la lista vinculada. Necesitamos omitir la cantidad deseada de nodos para llegar al nodo después del cual se insertará el nuevo nodo. . |
Eliminación y recorrido
La eliminación de un nodo de una lista enlazada individualmente se puede realizar en diferentes posiciones. Según la posición del nodo que se elimina, la operación se clasifica en las siguientes categorías.
| SN | Operación | Descripción |
|---|---|---|
| 1 | Eliminación al principio | Implica la eliminación de un nodo desde el principio de la lista. Esta es la operación más sencilla de todas. Sólo necesita algunos ajustes en los punteros de los nodos. |
| 2 | Eliminación al final de la lista | Implica eliminar el último nodo de la lista. La lista puede estar vacía o llena. Se implementa una lógica diferente para los diferentes escenarios. |
| 3 | Eliminación después del nodo especificado | Implica eliminar el nodo después del nodo especificado en la lista. debemos omitir la cantidad deseada de nodos para llegar al nodo después del cual se eliminará el nodo. Esto requiere recorrer la lista. |
| 4 | Atravesando | Al recorrer, simplemente visitamos cada nodo de la lista al menos una vez para realizar alguna operación específica en él, por ejemplo, imprimir parte de los datos de cada nodo presente en la lista. |
| 5 | buscando | En la búsqueda, relacionamos cada elemento de la lista con el elemento dado. Si el elemento se encuentra en cualquiera de las ubicaciones, se devuelve la ubicación de ese elemento; de lo contrario, se devuelve nulo. . |
Lista enlazada en C: programa controlado por menú
#include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('
*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
Enter the location of the node after which you want to perform deletion
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } Producción:
*********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9