Lista_de_encaminhamento contêiner fornece a implementação de lista vinculada individualmente estrutura de dados. Ele armazena dados em memória não contígua, onde cada elemento aponta para o próximo elemento da sequência. Isso torna a inserção e a exclusão mais rápidas quando a posição do elemento é conhecida.

declaração if java

Sintaxe

A lista de encaminhamento é definida como std::forward_list modelo de classe dentro do< lista_de_encaminhamento > arquivo de cabeçalho.

lista_de_encaminhamentofl;

onde

• T: Tipo de dados dos elementos na lista de encaminhamento.
• F: Nome atribuído à lista de encaminhamento.

Declaração e inicialização

Um forward_list pode ser declarado e inicializado de várias maneiras, conforme mostrado no exemplo abaixo:

#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 

Exemplo: No programa acima, somos uma lista direta inicializada de três maneiras:

• Declaração lista_de_encaminhamento FL1 cria uma lista direta vazia de inteiros.
• Declaração lista_de_encaminhamento fl2(34) cria uma lista direta de tamanho 3 e com cada elemento sendo 4.
• Declaração lista_de_encaminhamento fl3 = {1 5 3 4} cria uma lista de encaminhamento e inicializa com os elementos da lista de inicializadores.

Operações Básicas

Aqui estão as operações básicas que podemos realizar em uma lista de encaminhamento:

1. Acessando Elementos

Os elementos da lista de encaminhamento não podem ser acessados ​​usando índices como arrays ou vetores. Temos que percorrer a lista sequencialmente desde o início até a posição desejada para acessá-la. Isso pode ser feito incrementando começar() iterador, mas é melhor usar próximo() ou avançar() função.

No entanto, o primeiro elemento da lista pode ser facilmente acessado por frente() método.

Exemplo:

#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

Exemplo: No programa acima, o primeiro elemento é impresso usando frente() método. Para acessar o terceiro elemento próximo() é usado para mover o iterador duas posições desde o início e *isto é usado para desreferenciar o iterador.

2. Inserindo Elementos

Os elementos podem ser inseridos na lista direta usando inserir_depois() função. Requer o iterador após o qual o elemento será inserido. No entanto, a inserção rápida na frente é suportada por push_front() método.

Exemplo:

#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 

Explicação: Neste programa o primeiro elemento da forward_list é inserido na frente usando o push_front() função. Em seguida, um iterador é criado e movido uma posição para frente usando o comando avançar() função. Depois disso o elemento 5 é inserido após o segundo elemento usando o inserir_depois() função.

preconceito e variância

3. Atualizando Elementos

O valor dos elementos existentes pode ser alterado simplesmente acessando-os e usando operador de atribuição para atribuir o novo valor.

Exemplo:

#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. Encontrando Elemento

A lista direta não fornece nenhuma função membro para procurar um elemento, mas podemos usar o encontrar() algoritmo para encontrar qualquer valor fornecido.

Exemplo :

#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. Atravessando

Uma lista de encaminhamento pode ser percorrida usando começar() e fim() iteradores com um loop, mas só podemos avançar e não retroceder.

Exemplo:

#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. Excluindo Elementos

Na lista direta, podemos excluir o elemento na posição determinada usando apagar_depois() método. Este método leva o iterador para uma posição antes do elemento de destino. A exclusão rápida pela frente é possível usando pop_front() método.

classe abstrata vs interface

Exemplo:

#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. Tamanho da lista de encaminhamento

forward_list não possui uma função size() integrada. Para encontrar seu tamanho, precisamos contar manualmente os elementos percorrendo-o com um loop ou usando std::distância.

#include    #include  #include    using namespace std; int main() {  forward_list<int> flist={10203040};  //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. vazio()

É usado para verificar se forward_list está vazio.
Ele retorna verdadeiro se a lista estiver vazia e falso caso contrário, permite verificar rapidamente se o contêiner não possui dados.

#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. 

Complexidade de tempo

A tabela abaixo lista a complexidade de tempo das operações acima na lista de encaminhamento:

Lista de encaminhamento vs lista