Lista enlazada individualmente en estructuras de datos

Por: sarah chen sarah chen
Hours Actualizado

⚡ Resumen inteligente

Una lista enlazada simple es una estructura de datos lineal y unidireccional donde cada nodo almacena datos y un único puntero al siguiente nodo, por lo que el recorrido se realiza únicamente de cabeza a cola y la memoria se asigna dinámicamente a medida que se agregan nuevos nodos.

  • 🧩 Estructura del nodo: Cada nodo contiene un campo de datos y un Next puntero al siguiente nodo; el nodo de cola Next El puntero es NULO.
  • 📦 Lista vs. Array: Las listas enlazadas simples son preferibles cuando se desconoce el número de elementos, no se requiere acceso aleatorio y la inserción en mitad de la lista es común.
  • ➕ Inserciones: Se pueden agregar nodos al principio, al final, después de un nodo coincidente o antes de un nodo coincidente mediante reescrituras de punteros siguientes.
  • ➖ Eliminaciones: Al eliminar el nodo inicial, el nodo final o un nodo buscado, se actualizan los punteros vecinos y se libera la memoria liberada para evitar fugas de memoria.
  • 🔁 Recorrido: Solo se admite el recorrido hacia adelante porque no hay un puntero anterior, por lo que no es posible recorrer una lista enlazada simple en sentido inverso.
  • 💻 C++ y Python Code: Las implementaciones completas muestran rutinas de inserción, eliminación, búsqueda y recorrido con resultados ejecutables.
  • 📊 Complejidad: La inserción o eliminación de la cabeza es O(1); la búsqueda y otras inserciones y eliminaciones son O(n); la complejidad espacial es O(n).
Descubre más

Lista individualmente vinculada

¿Qué es una lista enlazada individualmente?

Una lista enlazada simple es una estructura de datos lineal y unidireccional donde los datos se almacenan en los nodos, y cada nodo está conectado mediante un enlace al siguiente nodo. Cada nodo contiene un campo de datos y un enlace al siguiente nodo. Las listas enlazadas simples solo se pueden recorrer en una dirección, mientras que una lista enlazada simple se puede recorrer en una dirección. Lista doblemente vinculada Se puede recorrer en ambas direcciones.

Aquí está la estructura de nodos de una lista enlazada simple:

Estructura de un nodo en una lista enlazada

Estructura de un nodo en una lista enlazada

¿Por qué usar una lista enlazada en lugar de un array?

Varios escenarios favorecen una lista enlazada sobre una Formación:

  • Número desconocido de elementos: Cuando no se conoce el número de elementos necesarios en tiempo de compilación, una lista enlazada asigna memoria dinámicamente a medida que se añaden elementos.
  • Acceso aleatorio: Cuando no se necesita acceso indexado aleatorio, una lista enlazada es una opción adecuada.
  • Inserción en el medio: Insertar un elemento en medio de un array requiere desplazar sus elementos. Una lista enlazada permite la inserción en cualquier posición modificando solo unos pocos punteros.

Operaciones de lista enlazada individualmente

Una lista enlazada simple es ideal para la asignación dinámica de memoria. Admite las operaciones estándar de las listas enlazadas, como la inserción, la eliminación, la búsqueda, la actualización, la fusión de dos listas y el recorrido.

En este artículo se analizan las siguientes operaciones:

  • Insertando en la cabeza
  • Insertando en la cola
  • Insertar después de un nodo
  • Insertar antes de un nodo
  • Eliminar el nodo principal
  • Eliminar el nodo de cola
  • Buscar y eliminar un nodo
  • Atravesando la lista enlazada

Aquí tienes un ejemplo de una lista enlazada con cuatro nodos.

Ejemplo de una lista enlazada individualmente

Ejemplo de una lista enlazada individualmente

Inserción al inicio de una lista enlazada simple.

Esta es una operación sencilla. Generalmente se conoce como agregar un elemento a una lista enlazada simple. Se crea un nuevo nodo y se coloca al principio de la lista.

Para realizar esta operación, se deben cumplir dos condiciones importantes:

  1. Si la lista está vacía, el nodo recién creado se convierte en el nodo principal y su Next El puntero es NULO.
  2. Si la lista no está vacía, el nuevo nodo se convierte en el nodo principal y su Next El puntero apunta al nodo de cabecera anterior.

Aquí está el pseudocódigo para insertar un nodo al principio de una lista enlazada:

function insertAtHead(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  else:
    newNode.next = head
    return newNode

Inserción en la cabeza

Insertando en la cabeza

Inserción al final de una lista enlazada simple.

Insertar un nodo al final de una lista enlazada es similar a insertarlo al principio. Recorra hasta el nodo final y luego apunte su Next Puntero al nuevo nodo. Si el nodo principal es NULL, el nuevo nodo se convierte en el nodo principal.

Paso 1) Atraviese hasta el Next El puntero del nodo actual se convierte en NULL.

Paso 2) Cree un nuevo nodo con el valor especificado.

Paso 3) Asigne el nuevo nodo como el siguiente nodo del nodo de cola.

El pseudocódigo para insertar al final de una lista simple:

function insertAtEnd(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  while head.next is not NULL:
    head = head.next
  head.next = newNode
  newNode.next = NULL

Insertando en la cola

Insertando en la cola

Inserción después de un nodo en una lista enlazada simple.

La inserción después de un nodo consta de dos partes: buscar el nodo objetivo y añadir un nuevo nodo después de él. Recorrer la lista hasta encontrar una coincidencia y, a continuación, insertar el nuevo nodo.

Paso 1) Recorra hasta que el valor del nodo actual sea igual al elemento de búsqueda.

Paso 2) Establecer el nuevo nodo Next puntero al nodo actual Next puntero.

Paso 3) Apuntar el nodo actual Next puntero al nuevo nodo.

Pseudocódigo:

function insertAfter(head, value, searchItem):
  newNode = Node(value)
  while head.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Insertar un nodo después de un nodo en una lista enlazada individualmente

Insertar un nodo después de un nodo en la lista enlazada individualmente

Inserción antes de un nodo en una lista enlazada simple.

Esto es similar a la inserción después de un nodo. Se recorre el árbol hasta que el siguiente nodo coincida con el valor de búsqueda y, a continuación, se inserta el nuevo nodo antes de él.

Paso 1) Recorra hasta que el valor del siguiente nodo sea igual al elemento de búsqueda.

Paso 2) Crea un nuevo nodo y configura su Next puntero al nodo actual Next.

Paso 3) Apuntar el nodo actual Next al nuevo nodo.

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

Insertar un nodo antes de un nodo en una lista enlazada individualmente

Insertar un nodo antes de un nodo en la lista enlazada individualmente

ARTÍCULOS RELACIONADOS

Eliminar el encabezado de la lista enlazada simple.

El puntero al nodo cabeza se proporciona como parámetro. El nodo cabeza se elimina y el siguiente nodo se convierte en el nuevo cabeza. La memoria del nodo eliminado debe liberarse para evitar fugas de memoria.

Paso 1) Asigna el siguiente nodo de la cabeza como la nueva cabeza.

Paso 2) Libera la memoria asignada al nodo principal anterior.

Paso 3) Devuelve el nuevo nodo principal.

function deleteHead(head):
  temp = head
  head = head.next
  free(temp)
  return head

Eliminar el encabezado de una lista vinculada

Eliminar el encabezado de una lista vinculada

Eliminar la cola de la lista enlazada simple

Eliminar el nodo de cola es similar a eliminar el nodo de cabeza. La diferencia es que se requiere recorrer la lista hasta el final. En una lista enlazada simple, el nodo cuyo Next El puntero es NULL, es el nodo de cola.

Paso 1) Recorre el nodo hasta justo antes del nodo final. Guarda el nodo actual.

Paso 2) Libera la memoria del siguiente nodo (la cola).

Paso 3) Establezca el siguiente nodo del nodo actual en NULL.

function deleteTail(head):
  while head.next.next is not NULL:
    head = head.next
  free(head.next)
  head.next = NULL

Eliminar la cola de la lista enlazada individualmente

Eliminar la cola de la lista enlazada individualmente

Buscar y eliminar un nodo de una lista enlazada simple.

Esta función realiza dos tareas: buscar y eliminar. Recorre hasta el final de la lista. Si se encuentra un nodo coincidente, elimínalo y vuelve a enlazar el nodo anterior. Next puntero.

Paso 1) Recorre la lista hasta el final. Comprueba si el nodo actual coincide con el nodo buscado.

Paso 2) Si se encuentra una coincidencia, almacene un puntero al nodo actual.

Paso 3) El Next El nodo anterior se convierte en el siguiente nodo del nodo actual.

Paso 4) Elimine el nodo actual y libere su memoria.

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

Buscar y eliminar un nodo de la lista enlazada individualmente

Buscar y eliminar un nodo de la lista enlazada individualmente

Recorrer una lista enlazada simple

Una lista enlazada simple solo permite recorrerla de principio a fin. No hay ningún puntero al nodo anterior, por lo que no es posible recorrerla en sentido inverso. Cada nodo se visita secuencialmente, imprimiendo su valor hasta llegar a NULL.

Paso 1) Recorre cada nodo hasta llegar a NULL.

Paso 2) Imprime el valor del nodo actual.

function traverse(head):
  while head is not NULL:
    print head.value
    head = head.next

Ejemplo de lista enlazada individualmente en C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head != NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head == NULL){
    insertAtHead(head, value);
    return;
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next != NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = NULL;
  if((*headPtr)->data == searchItem){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  } else {
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
void insertAfter(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->next->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
  Node* tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode != NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head, 5);
  insertAtHead(head, 6);
  insertAtHead(head, 7);
  insertEnd(head, 9);
  traverse(head);
  searchAndDelete(&head, 6);
  traverse(head);
  insertAfter(head, 7, 10);
  insertBefore(head, 9, 11);
  traverse(head);
}

Resultado

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Traversal from head:    7 --> 6 --> 5 --> 9
Deleted Node    6
Traversal from head:    7 --> 5 --> 9
Inserted 10 after node  7
Inserted 11 before node 9
Traversal from head:    7 --> 10 --> 5 --> 11 --> 9

Ejemplo de lista enlazada individualmente en Python

class Node:
  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None
  def insertAtHead(self, value):
    newNode = Node(data=value)
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')
  def searchAndDelete(self, searchItem):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
singlyLinkedList = SinglyLinkedList()
singlyLinkedList.insertAtHead(5)
singlyLinkedList.insertAtHead(6)
singlyLinkedList.insertAtHead(7)
singlyLinkedList.insertAtEnd(9)
singlyLinkedList.traverse()
singlyLinkedList.searchAndDelete(6)
singlyLinkedList.traverse()
singlyLinkedList.insertAfter(7, 10)
singlyLinkedList.insertBefore(9, 11)
singlyLinkedList.traverse()

Resultado

Added 5 at the front.
Added 6 at the front.
Added 7 at the front.
Added 9 at the end.
Traversing from head:   7       6       5       9
Deleted node    6
Traversing from head:   7       5       9
Inserted 10 after node  7
Inserted 11 before node 9
Traversing from head:   7       10      5       11      9

Complejidad de una lista enlazada simple

Existen dos tipos de complejidad: la complejidad temporal y la complejidad espacial. La complejidad temporal en el peor de los casos y en el caso promedio son las mismas para una lista enlazada simple.

Complejidad temporal en el caso de Mejores:

  • La inserción al inicio se puede realizar en O(1). No se requiere recorrer la lista.
  • La búsqueda y eliminación se puede realizar en O(1) si el elemento objetivo está en el nodo de cabeza.

Complejidad temporal en el caso promedio:

  • La inserción dentro de una lista enlazada toma O(n), donde n es el número total de elementos.
  • La búsqueda y eliminación también pueden tomar O(n), porque el elemento objetivo puede residir en cualquier lugar hasta el nodo final.

Complejidad espacial de una lista enlazada simple

Una lista enlazada simple asigna memoria dinámicamente. Para almacenar n elementos, asigna n unidades de memoria. Por lo tanto, la complejidad espacial es O(n).

Aplicaciones de listas enlazadas simples

Las listas enlazadas simples aparecen en muchos lugares donde el recorrido solo hacia adelante y la memoria dinámica resultan útiles:

  • Pilas y colas: Almacenamiento subyacente para pilas LIFO y colas FIFO construidas a partir de nodos.
  • Encadenamiento de tablas hash: Las colisiones se resuelven encadenando las entradas en una lista enlazada simple por cada cubo.
  • Listas de adyacencia: Los grafos dispersos utilizan una lista enlazada simple de vecinos para cada vértice.
  • Tablas de símbolos: Los compiladores e intérpretes encadenan los identificadores en una lista enlazada simple por ámbito.
  • Asignadores de memoria: Asignadores de lista libre track bloques libres como una lista enlazada simple.

Preguntas Frecuentes

Las listas enlazadas simples encadenan muestras de entrenamiento, minilotes y bloques de memoria libre dentro de los marcos de IA, lo que permite colas dinámicas para entradas en tiempo real y canalizaciones de datos sin bloqueo que se adaptan a la demanda del modelo.

Sí. GitHub Copilot y GPT pueden producir una lista enlazada simple completa en C, C++, Java, Python, o JavaScript que incluye inserción, eliminación, reversión, detección de ciclos y pruebas unitarias.

Una lista enlazada simple tiene un puntero "siguiente" y solo recorre los nodos hacia adelante. Una lista enlazada doble tiene punteros "siguiente" y "anterior", y recorre los nodos en ambas direcciones, pero utiliza más memoria por nodo.

Entre sus usos comunes se incluyen implementaciones de pilas y colas, encadenamiento de tablas hash, listas de adyacencia para grafos dispersos, tablas de símbolos en compiladores, asignadores de listas libres e historial de deshacer en editores ligeros.

La inserción o eliminación en la cabeza es O(1). La inserción en la cola, la búsqueda, la inserción en una posición y la eliminación de un nodo específico cuestan O(n) porque se requiere recorrer desde la cabeza.

Las listas enlazadas crecen y se reducen en tiempo de ejecución, insertan o eliminan datos en O(1) una vez que se conoce la posición y nunca necesitan memoria contigua. Los arreglos ofrecen acceso aleatorio en O(1) y una mejor localidad de caché.

Recorre la lista con tres punteros: prev, curr y next. En cada paso, guarda curr.next, apunta curr.next a prev y desplaza prev y curr hacia adelante. Devuelve prev como el nuevo encabezado.

El algoritmo de la tortuga y la liebre de Floyd utiliza dos punteros que se mueven a velocidades diferentes. Si se encuentran, la lista contiene un ciclo. De lo contrario, el puntero rápido llega a NULL y no existe ningún ciclo.

Resumir este post con: