estructura de datos de lista enlazada

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,

Lista enlazada Estructura de datos

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.

representando una lista enlazada conectando cada nodo con el siguiente nodo usando la dirección del siguiente nodo
Lista enlazada Representación

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++

Pitón
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 <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 casosCaso promedio
BúsquedaEn)En)
InsertarO(1)O(1)
SupresiónO(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

Publicaciones Similares

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *