Lista vinculada en C: ¿Cómo implementar una lista vinculada en C?

Después de las matrices, la segunda estructura de datos más popular es la lista vinculada. Una lista vinculada es una estructura de datos lineal, formada por una cadena de nodos en la que cada nodo contiene un valor y un puntero al siguiente nodo de la cadena. En este artículo, veamos cómo implementar una lista vinculada en C.

¿Qué es la lista vinculada en C?

Una lista vinculada es una estructura de datos lineal. Cada lista enlazada tiene dos partes, la sección de datos y la sección de dirección que contiene la dirección del siguiente elemento de la lista, que se llama nodo.

El tamaño de la lista vinculada no es fijo y los elementos de datos se pueden agregar en cualquier ubicación de la lista. La desventaja es que para llegar a un nodo, debemos atravesar todo el camino desde el primer nodo hasta el nodo que necesitamos. La lista vinculada es como una matriz pero, a diferencia de una matriz, no se almacena secuencialmente en la memoria.

Los tipos más populares de una lista vinculada son:

1. Lista de enlaces individuales
2. Doble lista de enlaces

Ejemplo de lista vinculada

Formato: [datos, dirección]

Cabeza -> [3,1000] -> [43,1001] -> [21,1002]

En el ejemplo, el número 43 está presente en la ubicación 1000 y la dirección está presente en el nodo anterior. Así es como se representa una lista enlazada.

Funciones básicas de listas vinculadas

Hay múltiples funciones que se pueden implementar en la lista vinculada en C. Intentemos comprenderlas con la ayuda de un programa de ejemplo.Primero, creamos una lista, la mostramos, la insertamos en cualquier ubicación, eliminamos una ubicación. El siguiente código le mostrará cómo realizar operaciones en la lista.

#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () estructura nodo {int info estructura nodo * siguiente} estructura nodo * inicio = NULL int main () {int elección while (1) {printf ('n MENU n') printf ('n 1.Crear n') printf ('n 2.Display n') printf ('n 3.Insertar en el principio n ') printf (' n 4.Insertar al final n ') printf (' n 5.Insertar en la posición especificada n ') printf (' n 6.Eliminar desde el principio n ') printf (' n 7.Eliminar desde el final n ') printf (' n 8.Eliminar desde la posición especificada n ') printf (' n 9. Salir n ') printf (' n ----------------- --------------------- n ') printf (' Ingrese su elección: t ') scanf ('% d ', & opción) cambiar (opción) {caso 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Wrong Choice: n') break}} return 0} voi d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nIntroduzca el valor de los datos para el nodo: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void display () {struct node * ptr if (start == NULL) {printf ('nList está vacía: n ') return} else {ptr = start printf (' nLos elementos de la lista son: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nEntra el valor de datos para el nodo: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} pags rintf ('nIntroduzca el valor de los datos para el nodo: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct nodo)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nEntre la posición para que se inserte el nuevo nodo: t') scanf ('% d' , & pos) printf ('nIntroduce el valor de los datos del nodo: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [Manipular con cuidado] n') return}} temp-> next = ptr-> next ptr -> siguiente = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nEl elemento eliminado es:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nEl elemento eliminado es:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > siguiente! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nEl elemento eliminado es:% dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nLa lista está vacía: n') exit (0)} else {printf ('nIntroduce la posición del nodo que se eliminará : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nEl elemento eliminado es:% dt ', ptr-> info) free (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nEl elemento eliminado es: % dt ', ptr-> info) gratis (ptr)}}}

La primera parte de este código es la creación de una estructura. Se crea una estructura de lista vinculada para que pueda contener los datos y la dirección cuando los necesitemos. Esto se hace para darle al compilador una idea de cómo debería ser el nodo.

nodo estructura {int info estructura nodo * siguiente}

En la estructura, tenemos una variable de datos llamada info para contener datos y una variable de puntero para apuntar a la dirección. Hay varias operaciones que se pueden realizar en una lista vinculada, como:

• crear()
• monitor()
• insert_begin ()
• insert_end ()
• ] insert_pos ()
• delete_begin ()
• delete_end ()
• delete_pos ()

Estas funciones son llamadas por la función principal impulsada por menús. En la función principal, tomamos información del usuario en función de la operación que el usuario quiere hacer en el programa. Luego, la entrada se envía a la caja del interruptor y se basa en la entrada del usuario.

Según la entrada que se proporcione, se llamará a la función. A continuación, tenemos diferentes funciones que deben resolverse. Echemos un vistazo a cada una de estas funciones.

Crear función

Primero, hay una función de creación para crear la lista vinculada. Esta es la forma básica en que se crea la lista vinculada. Veamos el código.

void create () {struct node * temp, * ptr printf ('nIntroduce el valor de datos para el nodo: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}

Salida

Primero, se crean dos punteros del tipo nodo, ptr y temp . Tomamos el valor que se necesita agregar en la lista vinculada del usuario y lo almacenamos en la parte de información de la variable temp y asignamos temp de la siguiente que es la parte de la dirección a nulo. Hay un puntero de inicio que sostiene el inicio de la lista. Luego buscamos el comienzo de la lista. Si el inicio de la lista es nulo, asignamos temp al puntero de inicio. De lo contrario, avanzamos hasta el último punto donde se agregaron los datos.

Para ello, asignamos a ptr el valor inicial y recorremos hasta ptr-> siguiente = nulo . Luego asignamos ptr-> siguiente la dirección de temp. De manera similar, se proporciona un código para insertar al principio, insertar al final e insertar en una ubicación específica.

Función de visualización

Aquí está el código para la función de visualización.

diferencia abstracta de clase e interfaz

void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nLos elementos de la lista son: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> siguiente}}}

Salida

En la función de visualización, primero verificamos si la lista está vacía y regresamos si está vacía. En la siguiente parte, asignamos el valor inicial a ptr. Luego ejecutamos un ciclo hasta que ptr sea nulo e imprimimos el elemento de datos para cada nodo, hasta que ptr sea nulo, lo que especifica el final de la lista.

Función de eliminación

Aquí está el fragmento de código para eliminar un nodo de la lista vinculada.

void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nLa lista está vacía: n') exit (0)} else {printf ('nIntroduce la posición del nodo a eliminar: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nEl elemento eliminado es:% dt ', ptr-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe el elemento eliminado es:% dt ', ptr-> info) free (ptr)}}}

Salida

En el proceso de eliminación, primero verifica si la lista está vacía, si es así, existe. Si no está vacío, pide al usuario que elimine el puesto. Una vez que el usuario ingresa al puesto, comprueba si es el primer puesto, en caso afirmativo asigna ptr para iniciar y mueve el puntero de inicio a la siguiente ubicación y elimina ptr. Si el la posición no es cero , luego ejecuta un bucle for desde 0 hasta la posición ingresada por el usuario y almacenada en el pos variable. Hay una declaración if para decidir si la posición ingresada no está presente. Si ptr es igual a nulo , entonces no está presente.

Nosotros asignar ptr a temp en el bucle for, y ptr luego pasa a la siguiente parte. Después de esto, cuando se encuentre la posición. Hacemos que la variable temporal contenga el valor de ptr-> siguiente omitiendo así el ptr. Entonces ptr se elimina. Del mismo modo, se puede hacer para la eliminación del primer y último elemento.

Lista doblemente vinculada

Se llama lista doblemente enlazada porque hay dos punteros , un punto al siguiente nodo y otros puntos al nodo anterior. Las operaciones realizadas en doble enlace son similares a las de una lista enlazada individualmente. Aquí está el código para operaciones básicas.

#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Posición struct Node {int e Posición anterior Posición siguiente} void Insert (int x, Lista l, Posición p) {Posición TmpCell TmpCell = (estructura Nodo *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} void Delete (int x, List l) {Posición p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> p2 anterior = p -> p1 siguiente - > siguiente = p -> siguiente if (p2! = NULL) // si el nodo no es el último nodo p2 -> anterior = p -> anterior} else printf ('¡¡¡El elemento no existe !!! n')} void Mostrar (Lista l) {printf ('Los elementos de la lista son ::') Posición p = l-> siguiente while (p! = NULL) {printf ('% d ->', p-> e) p = p- > siguiente}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('LISTA DOBLE VINCULADA IMPLEMENTACIÓN DE L IST ADTnn ') do {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnIntroduce la opción :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Introduce el elemento a insertar :: ') scanf ('% d', & x) printf ('Ingrese la posición del elemento ::') scanf ('% d', & pos) para (i = 1 isiguiente} Insertar (x, l, p) romper caso 2: p = l printf ('Ingresar el elemento a eliminar ::') scanf ('% d', & x) Eliminar (x, p) romper caso 3: Mostrar (l) romper}} mientras (ch<4) } 

Salida

Entonces, como puede ver, el concepto de operaciones es bastante simple. La lista doblemente enlazada tiene las mismas operaciones que la lista enlazada individualmente en el lenguaje de programación C. La única diferencia es que hay otra variable de dirección que ayuda a recorrer mejor la lista en una lista doblemente enlazada.

Espero que haya entendido cómo realizar operaciones básicas en una lista enlazada simple y doble en C.

Si desea aprender sobre la lista vinculada en Java, aquí tiene una .

Si encuentra alguna pregunta, no dude en hacer todas sus preguntas en la sección de comentarios de 'Lista vinculada en C' y nuestro equipo estará encantado de responder.