Linked List en C: Guía Completa con Código y Ejemplos
Las linked list in c program son estructuras de datos lineales que almacenan nodos que contienen datos y un puntero al siguiente nodo. A diferencia de las matrices, las linked list no tienen una ubicación de memoria contigua, lo que les permite crecer dinámicamente. Esto las convierte en una herramienta valiosa para la gestión de datos cuando el tamaño de los datos no es conocido de antemano.
Este artículo te guiará a través de la implementación de una linked list en C, proporcionando un código completo y ejemplos detallados. Aprenderás a crear, insertar, eliminar y buscar elementos en una linked list in c code.
Estructura de la Linked List
El elemento fundamental de una linked list es el nodo. Cada nodo contiene dos elementos:
- Data: El valor de datos que se almacenará en el nodo.
- Next: Un puntero al siguiente nodo en la lista.
c
struct Node {
int data;
struct Node *next;
};
Este código define una estructura llamada Node que contiene un campo de datos entero y un puntero llamado next que apunta al siguiente nodo.
Operaciones Básicas en Linked List
Para trabajar con una linked list, necesitas implementar varias operaciones básicas:
1. Creación de una Linked List
La creación de una linked list comienza con la creación del primer nodo.
c
struct Node *head = NULL; // Inicializa la lista como vacía
La variable head apunta al primer nodo de la lista, que se inicializa como NULL, lo que significa que la lista está vacía.
2. Insertar Elementos
Puedes insertar elementos en una linked list en tres posiciones:
2.1. Insertar al Comienzo (insertatbegin)
c
void insertatbegin(struct Node **head_ref, int new_data) {
struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
Esta función crea un nuevo nodo y lo agrega al inicio de la lista, actualizando el puntero head.
2.2. Insertar al Final (insertatend)
«`c
void insertatend(struct Node **headref, int newdata) {
struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->next = NULL;
if (*headref == NULL) {
*headref = new_node;
return;
}
struct Node *last = *headref;
while (last->next != NULL) {
last = last->next;
}
last->next = newnode;
}
«`
Esta función crea un nuevo nodo y lo agrega al final de la lista, recorriendo la lista hasta encontrar el último nodo.
2.3. Insertar Después de un Nodo Específico (insertafternode)
c
void insertafternode(struct Node *prev_node, int new_data) {
if (prev_node == NULL) {
printf("El nodo anterior no puede ser NULL");
return;
}
struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
Esta función inserta un nuevo nodo después de un nodo específico proporcionado como argumento.
3. Eliminar Elementos
Puedes eliminar elementos de una linked list en tres posiciones:
3.1. Eliminar al Comienzo (deleteatbegin)
c
void deleteatbegin(struct Node **head_ref) {
if (*head_ref == NULL)
return;
struct Node *temp = *head_ref;
*head_ref = (*head_ref)->next;
free(temp);
}
Esta función elimina el primer nodo de la lista, actualizando el puntero head.
3.2. Eliminar al Final (deleteatend)
«`c
void deleteatend(struct Node *head_ref) {
if (head_ref == NULL)
return;
if ((head_ref)->next == NULL) {
free(headref);
*headref = NULL;
return;
}
struct Node *secondlast = *headref;
while (secondlast->next->next != NULL) {
secondlast = secondlast->next;
}
free(secondlast->next);
second_last->next = NULL;
}
«`
Esta función elimina el último nodo de la lista, recorriendo la lista hasta encontrar el penúltimo nodo.
3.3. Eliminar un Nodo Específico (deletenode)
«`c
void deletenode(struct Node **headref, int key) {
struct Node *temp = *headref, *prev = NULL;
if (temp != NULL && temp->data == key) {
*head_ref = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL)
return;
prev->next = temp->next;
free(temp);
}
«`
Esta función elimina un nodo específico de la lista, recorriendo la lista hasta encontrar el nodo con la clave especificada.
4. Buscar un Elemento (searchlist)
c
struct Node *searchlist(struct Node *head, int key) {
struct Node *current = head;
while (current != NULL) {
if (current->data == key)
return current;
current = current->next;
}
return NULL;
}
Esta función busca un elemento específico en la lista y devuelve un puntero al nodo si se encuentra, o NULL si no se encuentra.
Ejemplo de Código en C
Aquí tienes un ejemplo de código en C que implementa las operaciones básicas de una linked list:
«`c
include
include
struct Node {
int data;
struct Node *next;
};
void insertatbegin(struct Node *head_ref, int new_data);
void insertatend(struct Node *headref, int newdata);
void insertafternode(struct Node prev_node, int new_data);
void deleteatbegin(struct Node *headref);
void deleteatend(struct Node **headref);
void deletenode(struct Node **head_ref, int key);
struct Node *searchlist(struct Node *head, int key);
void printlist(struct Node *node);
int main() {
struct Node *head = NULL;
insertatend(&head, 1);
insertatbegin(&head, 2);
insertatend(&head, 3);
insertafternode(head->next, 4);
printf(«Lista enlazada creada: «);
printlist(head);
deleteatbegin(&head);
printf(«Lista enlazada después de eliminar al comienzo: «);
printlist(head);
deletenode(&head, 3);
printf(«Lista enlazada después de eliminar el nodo con valor 3: «);
printlist(head);
if (searchlist(head, 2) != NULL)
printf(«El valor 2 está presente en la lista enlazadan»);
else
printf(«El valor 2 no está presente en la lista enlazadan»);
return 0;
}
void insertatbegin(struct Node **headref, int newdata) {
// … (Código ya mostrado anteriormente)
}
void insertatend(struct Node **headref, int newdata) {
// … (Código ya mostrado anteriormente)
}
void insertafternode(struct Node *prevnode, int newdata) {
// … (Código ya mostrado anteriormente)
}
void deleteatbegin(struct Node **head_ref) {
// … (Código ya mostrado anteriormente)
}
void deleteatend(struct Node **head_ref) {
// … (Código ya mostrado anteriormente)
}
void deletenode(struct Node **head_ref, int key) {
// … (Código ya mostrado anteriormente)
}
struct Node *searchlist(struct Node *head, int key) {
// … (Código ya mostrado anteriormente)
}
void printlist(struct Node *node) {
while (node != NULL) {
printf(«%d «, node->data);
node = node->next;
}
printf(«n»);
}
«`
Este ejemplo crea una linked list y realiza las siguientes operaciones:
- Inserta elementos al inicio y al final.
- Inserta un elemento después de un nodo específico.
- Elimina elementos al inicio y al final.
- Elimina un nodo específico.
- Busca un elemento específico.
Ventajas de las Linked Lists
Las linked list ofrecen las siguientes ventajas:
- Inserción y eliminación eficientes: La inserción y eliminación de elementos en una linked list se realiza en tiempo constante (O(1)).
- Tamaño dinámico: Las linked list pueden crecer o encogerse dinámicamente, sin necesidad de conocer el tamaño de la lista de antemano.
- Eficiencia de memoria: Las linked list no desperdician memoria, ya que solo se alocan los nodos que se necesitan.
Desventajas de las Linked Lists
Las linked list también tienen algunas desventajas:
- Acceso aleatorio lento: El acceso a un elemento específico en una linked list requiere recorrer la lista desde el principio, lo que puede ser lento para listas grandes.
- Uso de memoria adicional: Las linked list requieren memoria adicional para almacenar los punteros a los siguientes nodos.
Usos de las Linked Lists
Las linked list son ampliamente utilizadas en las siguientes aplicaciones:
- Implementación de colas y pilas: Las linked list se utilizan para implementar estructuras de datos como colas y pilas.
- Gestión de memoria: Los sistemas operativos utilizan linked list para gestionar la memoria disponible.
- Procesamiento de texto: Los editores de texto utilizan linked list para almacenar el texto.
- Algoritmos de grafos: Las linked list se utilizan para representar grafos.
Conclusión
Las linked list son una estructura de datos fundamental que ofrece una gran flexibilidad en la gestión de datos. Si necesitas una estructura de datos que pueda crecer dinámicamente y permita inserciones y eliminaciones eficientes, las linked list son una excelente opción. Este artículo te ha proporcionado una guía detallada sobre cómo implementar linked list en C, incluyendo ejemplos de código y explicaciones de las operaciones básicas.