lista_adelante El contenedor proporciona la implementación de lista enlazada individualmente estructura de datos. Almacena datos en una memoria no contigua donde cada elemento apunta al siguiente elemento de la secuencia. Esto hace que la inserción y eliminación sean más rápidas una vez que se conoce la posición del elemento.

Sintaxis

La lista de avance se define como std::lista_adelante plantilla de clase dentro del < lista_adelante > archivo de encabezado.

lista_adelante Florida;

dónde

• T: Tipo de datos de elementos en la lista de reenvío.
• F: Nombre asignado a la lista de reenvíos.

Declaración e inicialización

Una forward_list se puede declarar e inicializar de varias maneras, como se muestra en el siguiente ejemplo:

   #include          using     namespace     std  ;   void     printFL  (  forward_list   <  int  >&     fl  )     {      for     (  auto     i     :     fl  )      cout      < <     i      < <     ' '  ;      cout      < <     'n'  ;   }   int     main  ()     {          // Creating an empty forward_list      forward_list   <  int  >     fl1  ;      // Creating a forward_list with      // default value      forward_list   <  int  >     fl2  (  3       4  );          // Creating a forward_list from an      // initializer list      forward_list   <  int  >     fl3     =     {  1       5       3       4  };          printFL  (  fl2  );      printFL  (  fl3  );      return     0  ;   }   

4 4 4 1 5 3 4  

Ejemplo: En el programa anterior, inicializamos simplemente la lista de reenvío de tres maneras:

• Declaración lista_adelante FL1 crea una lista directa vacía de números enteros.
• Declaración lista_adelante fl2(34) crea una lista directa de tamaño 3 y con cada elemento 4.
• Declaración lista_adelante fl3 = {1 5 3 4} crea una lista directa y se inicializa con los elementos de la lista de inicializadores.

Operaciones básicas

Estas son las operaciones básicas que podemos realizar en una lista directa:

1. Accediendo a los elementos

No se puede acceder a los elementos de la lista directa mediante índices como matrices o vectores. Tenemos que recorrer la lista de forma secuencial desde el inicio hasta la posición deseada para acceder a ella. Esto se puede hacer incrementando comenzar() iterador pero es mejor usarlo próximo() o avance() función.

Sin embargo, se puede acceder fácilmente al primer elemento de la lista mediante frente() método.

Ejemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Access the first element      cout      < <     fl  .  front  ()      < <     endl  ;          // Access third element      auto     it     =     next  (  fl  .  begin  ()     2  );      cout      < <     *  it  ;      return     0  ;   }   

1 3 

Ejemplo: En el programa anterior, el primer elemento se imprime usando frente() método. Para acceder al tercer elemento próximo() se utiliza para mover el iterador dos posiciones desde el principio y *él se utiliza para desreferenciar el iterador.

2. Insertar elementos

Los elementos se pueden insertar en la lista de reenvío usando insertar_después() función. Requiere el iterador después del cual se insertará el elemento. Sin embargo, la inserción rápida en la parte delantera se ve favorecida por empujar_front() método.

Ejemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  5       4  };      // Inserting Element at front      fl  .  push_front  (  1  );          // Insert 3 after the second element      auto     it     =     fl  .  begin  ();      advance  (  it       1  );      fl  .  insert_after  (  it       3  );          for     (  auto     x  :     fl  )     cout      < <     x      < <     ' '  ;      return     0  ;   }   

1 5 3 4  

Explicación: En este programa, el primer elemento de forward_list se inserta al frente usando el empujar_front() función. Luego se crea un iterador y se mueve una posición hacia adelante usando el avance() función. Después de eso el elemento 5 se inserta después del segundo elemento usando el insertar_después() función.

3. Actualización de elementos

El valor de los elementos existentes se puede cambiar simplemente accediendo a ellos y usando operador de asignación para asignar el nuevo valor.

Ejemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Updating first element      fl  .  front  ()     =     111  ;      cout      < <     fl  .  front  ()      < <     endl  ;          // Updating third element      auto     it     =     next  (  fl  .  begin  ()     2  );      *  it     =     333  ;      cout      < <     *  it  ;      return     0  ;   }   

111 333 

4. Encontrar elemento

La lista directa no proporciona ninguna función miembro para buscar un elemento, pero podemos usar la encontrar() algoritmo para encontrar cualquier valor dado.

Ejemplo :

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Finding 3      auto     it     =     find  (  fl  .  begin  ()     fl  .  end  ()     3  );          if     (  it     !=     fl  .  end  ())     cout      < <     *  it  ;      else     cout      < <     'Element not Found'  ;      return     0  ;   }   

3 

5. Atravesando

Se puede recorrer una lista de reenvío usando comenzar() y fin() iteradores con un bucle pero solo podemos avanzar y no retroceder.

Ejemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };          // Traversing using range-based for loop      for  (  auto     i     :     fl  )      cout      < <     i      < <     ' '  ;      cout      < <     endl  ;          return     0  ;   }   

1 5 3 4  

6. Eliminar elementos

En la lista directa podemos eliminar el elemento en la posición dada usando borrar_después() método. Este método lleva el iterador a una posición antes del elemento de destino. La eliminación rápida desde el frente es posible usando pop_front() método.

Ejemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Delete first element      fl  .  pop_front  ();          // Delete third element      auto     it     =     fl  .  begin  ();      advance  (  it       1  );      fl  .  erase_after  (  it  );          for     (  auto     x  :     fl  )     cout      < <     x      < <     ' '  ;      return     0  ;   }   

5 3  

7. Tamaño de la lista de reenvíos

forward_list no tiene una función size() incorporada. Para encontrar su tamaño necesitamos contar manualmente los elementos atravesándolos con un bucle o usando std:: distancia.

   #include          #include         #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     flist  =  {  10    20    30    40  };      //Calculate size by counting elements using std:: distance      int     size  =  distance  (  flist  .  begin  ()  flist  .  end  ());      cout   < <  'Size of forward_list: '   < <  size   < <  endl  ;      return     0  ;   }   

Size of forward_list: 4  

8. vacío()

Se utiliza para comprobar si forward_list está vacío.
Devuelve verdadero si la lista está vacía y falso en caso contrario, lo que permite verificar rápidamente si el contenedor no tiene datos.

   #include          #include         using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     flist  ;      if     (  flist  .  empty  ())     {      cout      < <     'The forward_list is empty.'      < <     endl  ;      }      flist  .  push_front  (  10  );      if     (  !  flist  .  empty  ())     {      cout      < <     'The forward_list is not empty.'      < <     endl  ;      }      return     0  ;   }   

The forward_list is empty. The forward_list is not empty.  

Complejidad del tiempo

La siguiente tabla enumera la complejidad temporal de las operaciones anteriores en la lista directa:

Lista de reenvío vs lista