Lista enlazada
Una lista enlazada es una estructura de datos lineal que incluye una serie de nodos conectados. Aquí, cada nodo almacena el datos y el Dirección del siguiente nodo. Por ejemplo,
Debe comenzar en alguna parte, por lo que le damos a la dirección del primer nodo un nombre especial llamado CABEZA. Además, el último nodo de la lista enlazada se puede identificar porque su siguiente parte apunta a NULO.
Las listas enlazadas pueden ser de varios tipos: individualmente, doblementey lista enlazada circular. En este artículo, nos centraremos en la lista enlazada simple. Para obtener más información sobre otros tipos, visite Tipos de lista vinculada.
Nota: Es posible que haya jugado el juego Treasure Hunt, donde cada pista incluye la información sobre la siguiente pista. Así es como funciona la lista enlazada.
Representación de Lista Vinculada
Veamos cómo se representa cada nodo de la lista enlazada. Cada nodo consiste:
- un elemento de datos
- Una dirección de otro nodo
Envolvemos tanto el elemento de datos como la siguiente referencia de nodo en una estructura como:
struct node
{
int data;
struct node *next;
};
Comprender la estructura de un nodo de lista enlazada es la clave para comprenderlo.
Cada nodo de estructura tiene un elemento de datos y un puntero a otro nodo de estructura. Vamos a crear una lista enlazada simple con tres elementos para entender cómo funciona esto.
/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;
/* Save address of first node in head */
head = one;
Si no entendió ninguna de las líneas anteriores, todo lo que necesita es un repaso de punteros y estructuras.
En solo unos pocos pasos, hemos creado una lista enlazada simple con tres nodos.
El poder de una lista enlazada proviene de la capacidad de romper la cadena y volver a unirla. Por ejemplo, si quisiera poner un elemento 4 entre 1 y 2, los pasos serían:
- Cree un nuevo nodo de estructura y asígnele memoria.
- Agregue su valor de datos como 4
- Apunte su siguiente puntero al nodo de estructura que contiene 2 como valor de datos
- Cambie el siguiente puntero de «1» al nodo que acabamos de crear.
Hacer algo similar en una matriz habría requerido cambiar las posiciones de todos los elementos posteriores.
En python y Java, la lista enlazada se puede implementar usando clases como se muestra en los códigos a continuación.
Utilidad de lista enlazada
Las listas son una de las estructuras de datos más populares y eficientes, con implementación en todos los lenguajes de programación como C, C++, Python, Java y C#.
Aparte de eso, las listas enlazadas son una excelente manera de aprender cómo funcionan los punteros. Al practicar cómo manipular listas enlazadas, puede prepararse para aprender estructuras de datos más avanzadas, como gráficos y árboles.
Ejemplos de implementaciones de listas enlazadas en Python, Java, C y C++
# Linked list implementation in Python
class Node:
# Creating a node
def __init__(self, item):
self.item = item
self.next = None
class LinkedList:
def __init__(self):
self.head = None
if __name__ == '__main__':
linked_list = LinkedList()
# Assign item values
linked_list.head = Node(1)
second = Node(2)
third = Node(3)
# Connect nodes
linked_list.head.next = second
second.next = third
# Print the linked list item
while linked_list.head != None:
print(linked_list.head.item, end=" ")
linked_list.head = linked_list.head.next
// Linked list implementation in Java
class LinkedList {
// Creating a node
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
// Assign value values
linkedList.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
// Connect nodess
linkedList.head.next = second;
second.next = third;
// printing node-value
while (linkedList.head != null) {
System.out.print(linkedList.head.value + " ");
linkedList.head = linkedList.head.next;
}
}
}
// Linked list implementation in C
#include <stdio.h>
#include <stdlib.h>
// Creating a node
struct node {
int value;
struct node *next;
};
// print the linked list value
void printLinkedlist(struct node *p) {
while (p != NULL) {
printf("%d ", p->value);
p = p->next;
}
}
int main() {
// Initialize nodes
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
// Allocate memory
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;
// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;
// printing node-value
head = one;
printLinkedlist(head);
}
// Linked list implementation in C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Creating a node
class Node {
public:
int value;
Node* next;
};
int main() {
Node* head;
Node* one = NULL;
Node* two = NULL;
Node* three = NULL;
// allocate 3 nodes in the heap
one = new Node();
two = new Node();
three = new Node();
// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;
// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;
// print the linked list value
head = one;
while (head != NULL) {
cout << head->value;
head = head->next;
}
}
Complejidad de la lista enlazada
Complejidad del tiempo
Peor de los casos | Caso promedio | |
---|---|---|
Búsqueda | En) | En) |
Insertar | O(1) | O(1) |
Supresión | O(1) | O(1) |
Complejidad espacial: O(n)
Aplicaciones de lista enlazada
- Asignación de memoria dinámica
- Implementado en pila y cola
- En deshacer funcionalidad de software
- Tablas hash, Gráficos
Lecturas recomendadas
1. Tutoriales
- Operaciones de lista enlazada (Poligonal, Insertar, Eliminar)
- Tipos de lista enlazada
- Java LinkedList
2. Ejemplos
- Obtenga el elemento central de la Lista vinculada en una sola iteración
- Convierta la lista enlazada en una matriz y viceversa
- Detectar bucle en una lista enlazada