En este tutorial, aprenderá sobre la estructura de datos de listas vinculadas y su implementación en Python, Java, C y C ++.
Una estructura de datos de lista vinculada incluye una serie de nodos conectados. Aquí, cada nodo almacena los datos y la dirección del siguiente nodo. Por ejemplo,
Estructura de datos LinkedList
Tienes que empezar en alguna parte, así que le damos a la dirección del primer nodo un nombre especial llamado HEAD.
Además, el último nodo de la lista vinculada se puede identificar porque su siguiente porción apunta a NULL.
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 LinkedList
Veamos cómo se representa cada nodo de LinkedList. Cada nodo consta de:
- 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 vinculado es la clave para comprenderlo.
Cada nodo de estructura tiene un elemento de datos y un puntero a otro nodo de estructura. Creemos una lista vinculada simple con tres elementos para comprender 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 vinculada simple con tres nodos.
Representación LinkedList
El poder de LinkedList proviene de la capacidad de romper la cadena y volver a unirse a ella. Por ejemplo, si quisieras poner un elemento 4 entre 1 y 2, los pasos serían:
- Cree un nuevo nodo de estructura y asígnele memoria.
- Suma 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 vinculada se puede implementar usando clases como se muestra en los códigos a continuación.
Utilidad de lista vinculada
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 vinculadas son una excelente manera de aprender cómo funcionan los punteros. Al practicar cómo manipular listas vinculadas, puede prepararse para aprender estructuras de datos más avanzadas, como gráficos y árboles.
Implementaciones de listas vinculadas en ejemplos de Python, Java, C y C ++
Python Java C 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 #include // 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 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) ( printf("%d ", head->value); head = head->next; ) )
Complejidad de la lista enlazada
Complejidad del tiempo
| Peor de los casos | Caso promedio | |
|---|---|---|
| Buscar | En) | En) |
| Insertar | O (1) | O (1) |
| Supresión | O (1) | O (1) |
Complejidad espacial: O (n)
Aplicaciones de listas vinculadas
- Asignación de memoria dinámica
- Implementado en pila y cola
- En deshacer la funcionalidad de los softwares
- Tablas hash, gráficos
Lecturas recomendadas
1. Tutoriales
- Operaciones LinkedList (Traverse, Insert, Delete)
- Tipos de LinkedList
- LinkedList de Java
2. Ejemplos
- Obtenga el elemento medio de LinkedList en una sola iteración
- Convierta LinkedList en una matriz y viceversa
- Detectar bucle en una LinkedList
